Skip to Main content Skip to Navigation
New interface
Conference papers

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 metadata

Cited literature [28 references]  Display  Hide  Download
Contributor : Panagiota Katsikouli Connect in order to contact the contributor
Submitted on : Thursday, October 11, 2018 - 11:55:44 AM
Last modification on : Saturday, November 19, 2022 - 4:06:31 AM
Long-term archiving on: : Saturday, January 12, 2019 - 1:21:32 PM


Files produced by the author(s)




Maria Sinziana 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⟩



Record views


Files downloads