Efficient trajectory queries under the Fréchet distance (GIS Cup)

K.A. Buchin, Y. Diez, T.W.T. van Diggelen, W. Meulemans

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

10 Citations (Scopus)
208 Downloads (Pure)

Abstract

Consider a set P of trajectories (polygonal lines in R2), and a query given by a trajectory Q and a threshold &epsis; > 0. To answer the query we wish to find all trajectories P ∈ P such that δF(P, Q) ≤ &epsis;, where δF denotes the Fréchet distance. We present an approach to efficiently answer a large number of queries for the same set P. Key ingredients are (a) precomputing a spatial hash that allows us to quickly find trajectories that have endpoints near Q; (b) precomputing simplifications on all trajectories in P; (c) using the simplifications and optimizations of the decision algorithm to efficiently decide δF(P, Q) ≤ &epsis; for most P ∈ P.
Original languageEnglish
Title of host publicationProceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS)
EditorsSiva Ravada, Erik Hoel, Roberto Tamassia, Shawn Newsam, Goce Trajcevski, Goce Trajcevski
Place of PublicationNew York
PublisherAssociation for Computing Machinery, Inc
Number of pages5
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

  • Fréchet distance
  • Range searching
  • Trajectories

Fingerprint

Dive into the research topics of 'Efficient trajectory queries under the Fréchet distance (GIS Cup)'. Together they form a unique fingerprint.

Cite this