Multi-resolution sketches and locality sensitive hashing for fast trajectory processing

Abstract : Searching for similar GPS trajectories is a fundamental problem that faces challenges of large data volume and intrinsic complexity of trajectory comparison. In this paper, we present a suite of sketches for trajectory data that drastically reduce the computation costs associated with near neighbor search, distance estimation, clustering and classification, and subtrajectory detection. Apart from summarizing the dataset, our sketches have two uses. First, we obtain simple provable locality sensitive hash families for both the Hausdorff and Fréchet distance measures, useful in near neighbour queries. Second, we build a data structure called MRTS (Multi Resolution Trajectory Sketch), which contains sketches of varying degrees of detail. The MRTS is a user-friendly, compact representation of the dataset that allows to efficiently answer various other types of queries. Moreover, MRTS can be used in a dynamic setting with fast insertions of trajectories into the database. Experiments on real data show effective locality sensitive hashing substantially improves near neighbor search time. Distances defined on the skteches show good correlation with Fréchet and Hausdorff distances.
Complete list of metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/hal-01893304
Contributor : Panagiota Katsikouli <>
Submitted on : Thursday, October 11, 2018 - 11:55:44 AM
Last modification on : Tuesday, November 19, 2019 - 11:34:09 AM
Long-term archiving on: Saturday, January 12, 2019 - 1:21:32 PM

File

sigspatial2018.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Maria Astefanoaei, Paul Cesaretti, Panagiota Katsikouli, Mayank Goswami, Rik Sarkar. Multi-resolution sketches and locality sensitive hashing for fast trajectory processing. SIGSPATIAL 2018 - International Conference on Advances in Geographic Information Systems, Nov 2018, Seattle, United States. ⟨10.1145/3274895.3274943⟩. ⟨hal-01893304⟩

Share

Metrics

Record views

117

Files downloads

501