While there are software systems that simplify trajectory streams on the fly, few curve simplification algorithms with quality guarantees fit the streaming requirements. We present streaming algorithms for two such problems under the Fréchet distance d_F in ℝ^d for some constant d ≥ 2. Consider a polygonal curve τ in ℝ^d in a stream. We present a streaming algorithm that, for any ε ∈ (0,1) and δ > 0, produces a curve σ such that d_F(σ,τ[v₁,v_i]) ≤ (1+ε)δ and |σ| ≤ 2 opt-2, where τ[v₁,v_i] is the prefix in the stream so far, and opt = min{|σ'|: d_F(σ',τ[v₁,v_i]) ≤ δ}. Let α = 2(d-1)⌊d/2⌋² + d. The working storage is O(ε^{-α}). Each vertex is processed in O(ε^{-α} log 1/ε) time for d ∈ {2,3} and O(ε^{-α}) time for d ≥ 4 . Thus, the whole τ can be simplified in O(ε^{-α}|τ| log 1/ε) time. Ignoring polynomial factors in 1/ε, this running time is a factor |τ| faster than the best static algorithm that offers the same guarantees. We present another streaming algorithm that, for any integer k ≥ 2 and any ε ∈ (0,1/17), maintains a curve σ such that |σ| ≤ 2k-2 and d_F(σ,τ[v₁,v_i]) ≤ (1+ε) ⋅ min{d_F(σ',τ[v₁,v_i]): |σ'| ≤ k}, where τ[v₁,v_i] is the prefix in the stream so far. The working storage is O((kε^{-1}+ε^{-(α+1)})log 1/(ε)). Each vertex is processed in O(kε^{-(α+1)}log²1/(ε)) time for d ∈ {2,3} and O(kε^{-(α+1)} log 1/ε) time for d ≥ 4.

Let m and n be the numbers of vertices of two polygonal curves in ℝd for any fixed d such that m ≤ n. Since it was known in 1995 how to compute the Fréchet distance of these two curves in O (mn log(mn )) time, it has been an open problem whether the running time can be reduced to o (n2) when m = Ω(n ). In the mean time, several well-known quadratic time barriers in computational geometry have been overcome: 3SUM, some 3SUM-hard problems, and the computation of some distances between two polygonal curves, including discrete Fréchet distance, dynamic time warping, and geometric edit distance. It is curious that the quadratic time barrier for Fréchet distance still stands. We present an algorithm to compute the Fréchet distance in O (mn (log log n )2+μ log n/ log1+μ m ) expected time for some constant μ ∈ (0,1). It is the first algorithm that returns the Fréchet distance in o (mn ) time when m = Ω(nε ) for any fixed ε ∈ (0,1].

Let τ and σ be two polygonal curves in →., d for any fixed d. Suppose that τ and σ have n and m vertices, respectively, and m≤ n. While conditional lower bounds prevent approximating the Fréchet distance between τ and σ within a factor of 3 in strongly subquadratic time, the current best approximation algorithm attains a ratio of nc in strongly subquadratic time, for some constant cϵ(0,1). We present a randomized algorithm with running time O(nm0.99log(n/ϵ)) that approximates the Fréchet distance within a factor of 7+ϵ, with a success probability at least 1-1/n6. We also adapt our techniques to develop a randomized algorithm that approximates the discrete Fréchet distance within a factor of 7+ϵ in strongly subquadratic time. They are the first algorithms to approximate the Fréchet distance and the discrete Fréchet distance within constant factors in strongly subquadratic time.

In this paper, we delve into the problem of using monetary incentives to encourage players to shift from an initial Nash equilibrium to a more favorable one within a game. Our main focus revolves around computing the minimum reward required to facilitate this equilibrium transition. The game involves a single row player who possesses m strategies and k column players, each endowed with n strategies. Our findings reveal that determining whether the minimum reward is zero is NP-complete, and computing the minimum reward becomes APX-hard. Nonetheless, we bring some positive news, as this problem can be efficiently handled if either k or n is a fixed constant. Furthermore, we have devised an approximation algorithm with an additive error that runs in polynomial time. Lastly, we explore a specific case wherein the utility functions exhibit single-peaked characteristics, and we successfully demonstrate that the optimal reward can be computed in polynomial time.

We study several polygonal curve problems under the Fréchet distance via algebraic geometric methods. Let 𝕏dm and 𝕏dk be the spaces of all polygonal curves of m and k vertices in ℝd, respectively. We assume that k ≤ m. Let be the set of ranges in 𝕏dm for all possible metric balls of polygonal curves in 𝕏dk under the Fréchet distance. We prove a nearly optimal bound of O(dk log(km)) on the VC dimension of the range space (𝕏dm, ), improving on the previous O(d2k2 log(dkm)) upper bound and approaching the current Ω(dk log k) lower bound. Our upper bound also holds for the weak Fréchet distance. We also obtain exact solutions that are hitherto unknown for the curve simplification, range searching, nearest neighbor search, and distance oracle problems.

Due to the fast developments of 5G and IoT technologies, Inter-Datacenter (Inter-DC) networks are facing unprecedented pressure to duplicate large volumes of geographically distributed user data in a real-time manner. Meanwhile, with the expansion of Inter-DC networks scale, link/node failures also become increasingly frequent, negatively affecting the data transmission efficiency. Therefore, link failure recovery methods become of utmost importance. Many works investigated fast failure recovery, yet none of them consider the deployment overhead of such recovery schemes. While in this paper, we found that the side-effect of deploying recovery strategies and the future availability of the recovered transmissions are also crucial for fast recovery. So we propose a fast and low-redundancy failure recovery framework, FLAIR, which consists of a fast recovery strategy FRAVaR and a redundancy removal algorithm ROSE. FRAVaR takes full consideration of deployment overhead by minimizing shuffle traffic. On its base, ROSE regularly eliminates the cumulative rerouting redundancy by removing unnecessary routing updates. The experiment results on 4 realistic network topologies show that FLAIR successfully reduces up to 48.2% deployment overhead compared with the state-of-the-art solutions, and thus reduces up to 70.2% recovery speed and improves up to 36% network utilization.

We propose $κ$-approximate nearest neighbor (ANN) data structures for $n$ polygonal curves under the Fréchet distance in $\mathbb{R}^d$, where $κ\in \{1+\varepsilon,3+\varepsilon\}$ and $d \geq 2$. We assume that every input curve has at most $m$ vertices, every query curve has at most $k$ vertices, $k \ll m$, and $k$ is given for preprocessing. The query times are $\tilde{O}(k(mn)^{0.5+\varepsilon}/\varepsilon^d+ k(d/\varepsilon)^{O(dk)})$ for $(1+\varepsilon)$-ANN and $\tilde{O}(k(mn)^{0.5+\varepsilon}/\varepsilon^d)$ for $(3+\varepsilon)$-ANN. The space and expected preprocessing time are $\tilde{O}(k(mnd^d/\varepsilon^d)^{O(k+1/\varepsilon^2)})$ in both cases. In two and three dimensions, we improve the query times to $O(1/\varepsilon)^{O(k)} \cdot \tilde{O}(k)$ for $(1+\varepsilon)$-ANN and $\tilde{O}(k)$ for $(3+\varepsilon)$-ANN. The space and expected preprocessing time improve to $O(mn/\varepsilon)^{O(k)} \cdot \tilde{O}(k)$ in both cases. For ease of presentation, we treat factors in our bounds that depend purely on $d$ as~$O(1)$. The hidden polylog factors in the big-$\tilde{O}$ notation have powers dependent on $d$.

We present new approximation results on curve simplification and clustering under Fréchet distance. Let T = {ti : i ∈ [n]} be polygonal curves in ℝd of m vertices each. Let ℓ be any integer from [m]. We study a generalized curve simplification problem: given error bounds δi > 0 for i ∈ [n], find a curve σ of at most ℓ vertices such that dF (σ, ti) ≤ δi for i ∈ [n]. We present an algorithm that returns a null output or a curve σ of at most ℓ vertices such that dF(σ,τi) < δi + εδmax for i ∈ [n], where δmax = maxi∈[n] δi. If the output is null, there is no curve of at most ℓ vertices within a Frechet distance of δi from τi for i ∈ [n]. The running time is Õ (nO(ℓ) · mO(ℓ2) · (dℓ/ε)O(dℓ). This algorithm yields the first polynomial-time bicriteria approximation scheme to simplify a curve τ to another curve σ, where the vertices of σ can be anywhere in ℝd, so that dF(σ,τ) ≤ (1 + ε)δ and |σ| ≤ (1 + α) · min{|c|: dF(c,τ) ≤ δ} for any given δ > 0 and any fixed α,ε ∈ (0,1). The running time is Õ(mO(1/α) · (d/(αε))O(d/α)). By combining our technique with some previous results in the literature, we obtain an approximation algorithm for (k,ℓ)-median clustering. Given T, it computes a set Σ of k curves, each of ℓ vertices, such that is within a factor 1 + ε of the optimum with probability at least 1 — μ for any given μ, ε ∈ (0,1). The running time is † The full version of the paper can be accessed at https://arxiv.org/abs/2207.07809

Along with the development of 5G and IoT technologies in recent years, Inter Data Center (Inter-DC) network is facing an explosive growth of geographically distributed user data, which needs to be duplicated among DCs in a real-time manner. Transmission-based applications require high availability that is going beyond 99.99%. However, with the expansion of Inter-DC network scale, link failures are also growing, which seriously affects data transmission efficiency, so fast link failure recovery is then urgently needed. Many previous works have been done to achieve fast failure recovery, but most of them ignore two key points, 1) the cost of deploying recovery strategies, and 2) the side-effect of re-transmission to network availability. These two factors make the existing failure recovery process too slow to be practical in real-time online industrial environments. To achieve realistic fast recovery from Inter-DC network failures, we propose a failure recovery framework FRAVaR, which achieves high network availability with very little deployment overhead. Particularly, FRAVaR reduces the deployment overhead by a novel incremental routing strategy to isolate link failures. In other words, it only needs to shuffle a tiny amount of traffic within a small failure isolation domain. On this base, FRAVaR further adopts a risk assessment theory named Value-at-Risk (VaR) to control flow re-transmission. We implement a prototype of FRAVaR and conduct a series of experiments on 4 real InterDC network topologies (ATT North America, IBM, GlobalCenter, AGIS). Experiment results show that FRAVaR outperforms state-of-the-art solutions on the recovery speed by 70.2%.1

Edge computing systems typically handle a wide variety of applications that exhibit diverse degrees of sensitivity to job latency. Therefore, a multitude of utility functions of the job response time need to be considered by the underlying job dispatching and scheduling mechanism. Nonetheless, previous studies in edge computing mainly focused on optimizing a single utility function across all jobs, e.g., linear, sigmoid, or the hard deadline. In this paper, we design online job dispatching and scheduling strategies in which different jobs can be categorized by different non-increasing utility functions. Our goal is to maximize the total utility of all scheduled jobs. We first prove that no online deterministic algorithm could achieve a competitive ratio better than the lower bound$\Omega \left({\frac {1}{\sqrt {\epsilon }}}\right)$under the$(1+\epsilon)$-speed augmentation model. We proceed to propose an online algorithm, named asO4A, for handling jobs with heterogeneous utilities. We prove thatO4Ais$O\left({\frac {1}{\epsilon ^{2}}}\right)$-competitive. We also design its distributed version, i.e.,DO4A. We implementO4AandDO4Aon an edge computing testbed running deep learning inference jobs. With the production trace from Google Cluster, our experimental and large-scale simulation results indicate thatO4Acan increase the total utility by up to 50% compared with state-of-the-art methods. Besides, the performance loss ofDO4Ais only 2% compared withO4Awith a small communication overhead involved. Moreover, both of our algorithms are robust to estimation errors in job processing time and transmission delay.

Edge computing systems typically handle a wide variety of applications that exhibit diverse degrees of sensitivity to job latency. Therefore, a multitude of utility functions of the job response time need to be considered by the underlying job dispatching and scheduling mechanism. Nonetheless, previous works in edge computing mainly focused on either one kind of utility function (e.g., linear, sigmoid, or the hard deadline) or different kinds of utilities separately. In this paper, we investigate online job dispatching and scheduling strategies under the setting of coexistence of heterogeneous utilities, i.e., various coexisting jobs can employ different non-increasing utility functions. The goal is to maximize the total utility over all jobs in an edge system. Besides heterogeneous utilities, we here adopt a practical online model where the unrelated machine model and the upload and download delay are considered. We proceed to propose an online algorithm, O4A, to dispatch and schedule jobs with heterogeneous utilities. Our theoretical analysis shows that O4A is O(1/ɛ2)-competitive under the (1 + ɛ)-speed augmentation model, where ɛ is a small positive constant. We implement O4A on an edge computing testbed running deep learning inference jobs. With the production trace from Google Cluster, our experimental and large-scale simulation results indicate that O4A can increase the total utility by up to 39.42% compared with state-of-the-art utility-agnostic methods. Moreover, O4A is robust to estimation errors in job processing time and transmission delay.