A Practical Index Structure Supporting Fr\'echet Proximity Queries Among Trajectories

Abstract

We present a scalable approach for range and \(k\) nearest neighbor queries under computationally expensive metrics, like the continuous Fr\'echet distance on trajectory data. Based on clustering for metric indexes, we obtain a dynamic tree structure whose size is linear in the number of trajectories, regardless of the trajectory's individual sizes or the spatial dimension, which allows one to exploit low `intrinsic dimensionality' of data sets for effective search space pruning. Since the distance computation is expensive, generic metric indexing methods are rendered impractical. We present strategies that (i) improve on known upper and lower bound computations, (ii) build cluster trees without any or very few distance calls, and (iii) search using bounds for metric pruning, interval orderings for reduction, and randomized pivoting for reporting the final results. We analyze the efficiency and effectiveness of our methods with extensive experiments on diverse synthetic and real-wo

Stats

• citations6
• S2 citations—
• github stars0
• HF likes0
• heat score6.34
• arxiv keygudmundsson2020a

Related papers

• Exact Trajectory Similarity Search With N-tree: An Efficient Metric Index For Knn And Range Queries (2024)0.00
• Geopth: A Lightweight Approach To Category-based Trajectory Retrieval Via Geometric Prototype Trajectory Hashing (2025)0.00
• Accurate And Fast Retrieval For Complex Non-metric Data Via Neighborhood Graphs (2019)0.00
• Simple Distances For Trajectories Via Landmarks (2018)4.52
• Hd-index: Pushing The Scalability-accuracy Boundary For Approximate Knn Search In High-dimensional Spaces (2018)14.02
• Optimization Of Indexing Based On K-nearest Neighbor Graph For Proximity Search In High-dimensional Data (2018)0.00
• A Scalable Solution To The Nearest Neighbor Search Problem Through Local-search Methods On Neighbor Graphs (2017)3.58
• Fast Approximate Nearest Neighbor Search With A Dynamic Exploration Graph Using Continuous Refinement (2023)0.00