A dynamic data structure for approximate Proximity queries in trajectory data

M.T. de Berg, J. Gudmundsson, A.D. Mehrabi

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 Citations (Scopus)

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.

Original languageEnglish
Title of host publication SIGSPATIAL'17 Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems
EditorsSiva Ravada, Erik Hoel, Roberto Tamassia, Shawn Newsam, Goce Trajcevski, Goce Trajcevski
Place of PublicationNew York
PublisherAssociation for Computing Machinery, Inc
Number of pages4
ISBN (Print)978-1-4503-5490-5
DOIs
Publication statusPublished - 7 Nov 2017
Event25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2017) - Redondo Beach, United States
Duration: 7 Nov 201710 Nov 2017
Conference number: 25
http://sigspatial2017.sigspatial.org/

Conference

Conference25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2017)
Abbreviated titleACM GIS 2017
Country/TerritoryUnited States
CityRedondo Beach
Period7/11/1710/11/17
Internet address

Keywords

  • And approximate range queries.
  • Approximate nearest-neighbor queries
  • Data structures
  • Fréchet distance
  • Trajectory analysis

Fingerprint

Dive into the research topics of 'A dynamic data structure for approximate Proximity queries in trajectory data'. Together they form a unique fingerprint.

Cite this