On the complexity of range searching among curves

Peyman Afshani, Anne Driemel

TL;DR

This paper tackles the challenge of efficiently searching for similar curves within a large dataset, specifically using the Fréchet distance. The authors establish fundamental lower bounds on the space and query time trade-offs for this problem, demonstrating that increasing the complexity of curves or queries leads to significant performance degradation. They also present novel data structures that achieve these bounds for both discrete and continuous Fréchet distances.

What Problem Does This Paper Address?

Modern tracking technologies generate vast amounts of trajectory data, often represented as sequences of points forming curves. A crucial task is to find curves in a dataset that are similar to a given query curve. The Fréchet distance is a widely accepted metric for measuring curve similarity, offering a more nuanced comparison than simpler distance measures. The core problem addressed here is how to preprocess a collection of curves into a data structure that can efficiently answer queries: "Find all curves in the dataset that are within a Fréchet distance p of this query curve q."

This problem is particularly challenging due to the inherent complexity of the Fréchet distance and the desire to handle curves of varying complexity. The paper also delves into a broader theoretical question concerning "multilevel data structures," which are used in various geometric searching problems. A key question is whether the space and query time of these structures must necessarily grow exponentially with the number of "levels" (representing increasing complexity).

Methods

The paper's contributions lie in both theoretical lower bounds and practical data structure constructions.

Lower Bounds: The authors establish lower bounds using a "multilevel stabbing problem" as a proxy. This involves constructing a challenging input of "t-slabs" (multidimensional rectangular regions) and query points. By analyzing the minimum space required to answer these stabbing queries, they derive lower bounds for the Fréchet distance problem. A key technique is the use of a "pointer machine model" and intricate geometric constructions involving parametric points and colors to represent slabs. They also leverage techniques from orthogonal range searching.

Data Structures: The paper presents data structures for both discrete and continuous Fréchet distances. These structures are built upon recent advancements in "semialgebraic range searching," which deals with geometric objects defined by polynomial inequalities. The core idea is to decompose the Fréchet distance computation into a series of semialgebraic range queries. For the discrete Fréchet distance, this involves analyzing a "free-space matrix." For the continuous Fréchet distance, a more complex "free-space diagram" is used, and high-level predicates are defined to capture reachability. These predicates are then broken down into simpler "low-level predicates" that can be handled by semialgebraic range searching techniques.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithmic constructions rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Exponential Blow-up is (Often) Unavoidable: The paper provides strong evidence that for multilevel data structures, the space and query time must increase significantly (exponentially in some cases) with the complexity of the objects being searched. This answers a long-standing open question in the field.
  • Fréchet Distance Complexity: The paper demonstrates that the complexity of Fréchet distance queries is inherently tied to the complexity of the input and query curves, leading to logarithmic factors in the space/query time trade-off that grow with curve complexity.
  • Bridging Semialgebraic Geometry and Fréchet Distance: A significant contribution is showing how to apply sophisticated semialgebraic range searching techniques to the Fréchet distance problem, which is not directly an algebraic expression. This opens doors for using advanced geometric algorithms in trajectory analysis.
  • Discrete vs. Continuous Fréchet: The paper highlights differences in complexity between the discrete and continuous Fréchet distances, with the continuous version requiring a higher number of "levels" in the data structure.

Key Results

  • Lower Bounds: The paper establishes lower bounds for the multilevel stabbing problem, implying that the space S(n) required for Q(n) query time must satisfy:
  • $S(n) = \Omega\left(\left(\frac{n}{Q(n)}\right)^{2^{\Theta(2t)}} \left(\frac{\log(n/Q(n))}{\log\log n}\right)^{t-1}\right)$

    • $S(n) = \Omega\left(\left(\frac{n}{Q(n)}\right)^{2^{\Theta(t)}} \left(\frac{\log(n/Q(n))}{\log\log n}\right)^{t-1-o(1)}\right)$ These bounds show an exponential dependency on t (curve complexity).
  • Discrete Fréchet Data Structure: Achieves a space/query time trade-off in line with the lower bounds, with O(t) levels.

  • Continuous Fréchet Data Structure: Achieves a space/query time trade-off with O(t²) levels (for d=2).

Limitations and Future Work

  • Continuous Fréchet Levels: The O(t²) levels for the continuous Fréchet distance might be reducible to O(t) by using dualization more selectively. The authors suggest this as a direction for future work, acknowledging the increased technical complexity.
  • Approximate Queries: The paper focuses on exact Fréchet distance queries. Developing efficient data structures for approximate Fréchet distance queries is an open problem, as current lower bound frameworks struggle with approximations.
  • Higher Dimensions: Extending range searching for Fréchet distance to curves in 3D or higher dimensions is an open area, with a suspicion that existing bounds might not directly translate.
  • Related Distance Measures: Investigating range searching for other distance measures like dynamic time warping is also suggested.
  • Semialgebraic Circumvention: The paper poses the question of whether semialgebraic range searching can be avoided for Fréchet queries, which could potentially simplify solutions.

Summary updated

Abstract

Modern tracking technology has made the collection of large numbers of densely sampled trajectories of moving objects widely available. We consider a fundamental problem encountered when analysing such data: Given $n$ polygonal curves $S$ in $\mathbb{R}^d$, preprocess $S$ into a data structure that answers queries with a query curve $q$ and radius $ρ$ for the curves of $S$ that have \Frechet distance at most $ρ$ to $q$. We initiate a comprehensive analysis of the space/query-time trade-off for this data structuring problem. Our lower bounds imply that any data structure in the pointer model model that achieves $Q(n) + O(k)$ query time, where $k$ is the output size, has to use roughly $Ω\left((n/Q(n))^2\right)$ space in the worst case, even if queries are mere points (for the discrete \Frechet distance) or line segments (for the continuous \Frechet distance). More importantly, we show that more complex queries and input curves lead to additional logarithmic factors in the lower bound. Roughly speaking, the number of logarithmic factors added is linear in the number of edges added to the query and input curve complexity. This means that the space/query time trade-off worsens by an exponential factor of input and query complexity. This behaviour addresses an open question in the range searching literature: whether it is possible to avoid the additional logarithmic factors in the space and query time of a multilevel partition tree. We answer this question negatively. On the positive side, we show we can build data structures for the \Frechet distance by using semialgebraic range searching. Our solution for the discrete \Frechet distance is in line with the lower bound, as the number of levels in the data structure is $O(t)$, where $t$ denotes the maximal number of vertices of a curve. For the continuous \Frechet distance, the number of levels increases to $O(t^2)$.
BibTeX
@inproceedings{afshani2018complexity,
  author = {Peyman Afshani and Anne Driemel},
  title = {{On the complexity of range searching among curves}},
  booktitle = {SODA},
  year = {2018},
  doi = {10.1137/1.9781611975031.58},
}

Loading related content...

Figure