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

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

doi:10.1145/3139958.3140064

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 proceeding › Conference contribution › Academic › peer-review

16 Citations (Scopus)

317 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 language	English
Title of host publication	Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS)
Editors	Siva Ravada, Erik Hoel, Roberto Tamassia, Shawn Newsam, Goce Trajcevski, Goce Trajcevski
Place of Publication	New York
Publisher	Association for Computing Machinery, Inc
Number of pages	5
ISBN (Print)	978-1-4503-5490-5
DOIs	https://doi.org/10.1145/3139958.3140064
Publication status	Published - 7 Nov 2017
Event	25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2017) - Redondo Beach, United States Duration: 7 Nov 2017 → 10 Nov 2017 Conference number: 25 http://sigspatial2017.sigspatial.org/

Conference

Conference	25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2017)
Abbreviated title	ACM GIS 2017
Country/Territory	United States
City	Redondo Beach
Period	7/11/17 → 10/11/17
Internet address	http://sigspatial2017.sigspatial.org/

Keywords

Fréchet distance
Range searching
Trajectories

Access to Document

10.1145/3139958.3140064

authors versionFinal author version , 652 KB

Cite this

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 (Eds.), 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

Buchin, K.A. ; Diez, Y. ; van Diggelen, T.W.T. et al. / Efficient trajectory queries under the Fréchet distance (GIS Cup). Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS). editor / Siva Ravada ; Erik Hoel ; Roberto Tamassia ; Shawn Newsam ; Goce Trajcevski ; Goce Trajcevski. New York : Association for Computing Machinery, Inc, 2017.

@inproceedings{43659976bdf5420d8e5efd82d770e088,

title = "Efficient trajectory queries under the Fr{\'e}chet distance (GIS Cup)",

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{\'e}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.",

keywords = "Fr{\'e}chet distance, Range searching, Trajectories",

author = "K.A. Buchin and Y. Diez and {van Diggelen}, T.W.T. and W. Meulemans",

year = "2017",

month = nov,

day = "7",

doi = "10.1145/3139958.3140064",

language = "English",

isbn = "978-1-4503-5490-5 ",

editor = "Siva Ravada and Erik Hoel and Roberto Tamassia and Shawn Newsam and Goce Trajcevski and Goce Trajcevski",

booktitle = "Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS)",

publisher = "Association for Computing Machinery, Inc",

address = "United States",

note = "25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2017), ACM GIS 2017 ; Conference date: 07-11-2017 Through 10-11-2017",

url = "http://sigspatial2017.sigspatial.org/",

}

Buchin, KA, Diez, Y, van Diggelen, TWT & 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 (eds), Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS)., 101, Association for Computing Machinery, Inc, New York, 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2017), Redondo Beach, California, United States, 7/11/17. https://doi.org/10.1145/3139958.3140064

Efficient trajectory queries under the Fréchet distance (GIS Cup). / Buchin, K.A.; Diez, Y.; van Diggelen, T.W.T. et al.
Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS). ed. / Siva Ravada; Erik Hoel; Roberto Tamassia; Shawn Newsam; Goce Trajcevski; Goce Trajcevski. New York: Association for Computing Machinery, Inc, 2017. 101.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Buchin, K.A.

AU - Diez, Y.

AU - van Diggelen, T.W.T.

AU - Meulemans, W.

N1 - Conference code: 25

PY - 2017/11/7

Y1 - 2017/11/7

N2 - 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.

AB - 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.

KW - Fréchet distance

KW - Range searching

KW - Trajectories

UR - http://www.scopus.com/inward/record.url?scp=85040993242&partnerID=8YFLogxK

U2 - 10.1145/3139958.3140064

DO - 10.1145/3139958.3140064

M3 - Conference contribution

SN - 978-1-4503-5490-5

BT - Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS)

A2 - Ravada, Siva

A2 - Hoel, Erik

A2 - Tamassia, Roberto

A2 - Newsam, Shawn

A2 - Trajcevski, Goce

PB - Association for Computing Machinery, Inc

CY - New York

T2 - 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2017)

Y2 - 7 November 2017 through 10 November 2017

ER -

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

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

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this