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

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

8 Citaten (Scopus)
163 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
TitelProceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS)
RedacteurenSiva Ravada, Erik Hoel, Roberto Tamassia, Shawn Newsam, Goce Trajcevski, Goce Trajcevski
Plaats van productieNew York
UitgeverijAssociation for Computing Machinery, Inc
Aantal pagina's5
ISBN van geprinte versie978-1-4503-5490-5
DOI's
StatusGepubliceerd - 7 nov 2017
Evenement25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2017) - Redondo Beach, Verenigde Staten van Amerika
Duur: 7 nov 201710 nov 2017
Congresnummer: 25
http://sigspatial2017.sigspatial.org/

Congres

Congres25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2017)
Verkorte titelACM GIS 2017
LandVerenigde Staten van Amerika
StadRedondo Beach
Periode7/11/1710/11/17
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'Efficient trajectory queries under the Fréchet distance (GIS Cup)'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Buchin, K. A., Diez, Y., van Diggelen, T. W. T., & Meulemans, W. (2017). Efficient trajectory queries under the Fréchet distance (GIS Cup). In S. Ravada, E. Hoel, R. Tamassia, S. Newsam, G. Trajcevski, & G. Trajcevski (editors), Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS) [101] Association for Computing Machinery, Inc. https://doi.org/10.1145/3139958.3140064