Mark de Berg
ABSTRACT
Let S be a set of n polygonal trajectories in the plane and k be a fixed constant. We present a data structure to store S so that, given a k-vertex query trajectory Q, we can answer the following queries approximately:
• Nearest neighbor query: given a query trajectory Q, report the trajectory in S with minimum Fréchet distance to Q.
• Top-j query: given a query trajectory Q and a positive integer j, report the j trajectories in S with minimum Fréchet distance to Q.
• Range reporting query: given a query trajectory Q and a number δmax, report all trajectories in S with Fréchet distance at most δmax to Q.
• Similarity query: given a query trajectory Q and a trajectory τ ∈ S, report the Fréchet distance between Q and τ.
Our data structure answers these queries approximately with an additive error that is at most ϵ · reach(Q) for a given fixed constant ϵ > 0, where reach(Q) is the maximum distance between the start vertex of Q and any other vertex of Q. Furthermore, our query procedures ignore trajectories whose Fréchet distance to the query Q is very large. That is, if no trajectory is close to the query trajectory then no answer might be returned. The data structure uses O(n/ϵ2k) space and answers each of the queries above in time O(1 + #answers). Our data structure is the first one that can answer all these queries with provable error guarantees. Moreover, it is fully dynamic: inserting and deleting a trajectory with m vertices takes O(1/ϵ2k (m + log(1/ϵ))) and O(1/ϵ2k) amortized time, respectively. Finally, we empirically evaluate our data structure.
- Helmut Alt and Michael Godau. 1995. Computing the Fréchetdistance between two polygonal curves. International Journal of Computational Geometry and Applications 5 (1995), 75--91.Google Scholar
Cross Ref
- Mark de Berg, Atlas F. Cook, and Joachim Gudmundsson. 2013. Fast Fréchet queries. Computational Geometry: Theory and Applications 46 (2013), 747--755. Google ScholarDigital Library
- Mark de Berg and Ali D. Mehrabi. 2016. Straight-Path Queries in Trajectory Data. Journal of Discrete Algorithms 36 (2016), 27--38. Google ScholarDigital Library
- Sotiris Brakatsoulas, Dieter Pfoser, Randall Salas, and Carola Wenk. 2008. On Map-Matching Vehicle Tracking Data. In Proceedings of 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 288--297.Google Scholar
- Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Maarten Löffler, and Jun Luo. 2008. Detecting Commuting Patterns by Clustering Subtrajectories. In Proceedings of 19th Annual International Symposium on Algorithms and Computation. Google ScholarDigital Library
- Declan Butler. 2006. Virtual globes: The Web-Wide World. Nature 439 (2006), 776--778.Google Scholar
- Lili Cao and John Krumm. 2009. From GPS Traces to a Routable Road Map. In Proceedings of 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 3--12. Google ScholarDigital Library
- K. Karthik E. Sriraghavendra and C. Bhattacharyya. 2007. Fréchet Distance Based Approach for Searching Online Handwriting Documents. In Proceedings of 9th International Conference on Document Analysis and Recognition. 461--465. Google ScholarDigital Library
- Eliezer Gurarie, Russel D. Andrews, and Kristin L. Laidre. 2009. A Novel Method for Identifying Behavioural Changes in Animal Movement Data. Ecology Letters 12, 5 (2009), 395--408.Google ScholarCross Ref
- Benjamin Krogh, Nikos Pelekis, Yannis Theodoridis, and Kristian Torp. 2014. Path-based Queries on Trajectory Data. In Proceedings of 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 341--350. Google ScholarDigital Library
- Sam Kwong, K. S. Tang Q. H. He, K. F. Man, and C. W. Chau. 1998. Parallel Genetic-based Hybrid Pattern Matching Algorithm for Isolated Word Recognition. International Journal of Pattern Recognition and Artificial Intelligence 12, 5 (1998), 573--594.Google ScholarCross Ref
- Bin Lin and Jianwen Su. 2005. Shapes Based Trajectory Queries for Moving Objects. In Proceedings of the 13th Annual ACM International Workshop on Geographic Information Systems. 21--30. Google ScholarDigital Library
- Ali D. Mehrabi. 2017. Data Structures for Analyzing Geometric Data. PhD Thesis, TU Eindhoven.Google Scholar
- Rasmus Pagh and Flemming F. Rodler. 2001. Cuckoo Hashing. In Proceedings of 9th European Symposium on Algorithms. 121--133. Google ScholarDigital Library
- Choon-Bo Shim, Jae-Woo Chang, and Young-Chang Kim. 2005. Trajectory-Based Video Retrieval for Multimedia Information Systems. In Proceedings of 3th International Conference on Advances in Information Systems. 372--282. Google ScholarDigital Library
- Carola Wenk, Randall Salas, and Dieter Pfoser. 2006. Addressing the Need for Map-Matching Speed: Localizing Global Curve-Matching Algorithms. In Proceedings of 18th International Conference on Scientific and Statistical Database Management. 879--888. Google ScholarDigital Library
Index Terms
- A Dynamic Data Structure for Approximate Proximity Queries in Trajectory Data
Recommendations
Efficient trajectory queries under the Fréchet distance (GIS Cup)
SIGSPATIAL '17: Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information SystemsConsider a set P of trajectories (polygonal lines in R2), and a query given by a trajectory Q and a threshold ϵ > 0. To answer the query we wish to find all trajectories P ∈ P such that δF(P, Q) ≤ ϵ, where δF denotes the Fréchet distance. We present an ...
Translation Invariant Fréchet Distance Queries
AbstractThe Fréchet distance is a popular similarity measure between curves. For some applications, it is desirable to match the curves under translation before computing the Fréchet distance between them. This variant is called the Translation Invariant ...
A truly dynamic data structure for top-k queries on uncertain data
SSDBM'11: Proceedings of the 23rd international conference on Scientific and statistical database managementTop-k queries allow end-users to focus on the most important (top-k) (answers amongst those which satisfy the query. In traditional databases, a user defined score function assigns a score value to each tuple and a top-k query returns k tuples with the ...
Comments