REPOSE: Distributed top-k trajectory similarity search with local reference point tries

Bolong Zheng, Lianggui Weng, Xi Zhao, Kai Zeng, Xiaofang Zhou, Christian S. Jensen

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

8 Citationer (Scopus)

Abstract

Trajectory similarity computation is a fundamental component in a variety of real-world applications, such as ridesharing, road planning, and transportation optimization. Recent advances in mobile devices have enabled an unprecedented increase in the amount of available trajectory data such that efficient query processing can no longer be supported by a single machine. As a result, means of performing distributed in-memory trajectory similarity search are called for. However, existing distributed proposals either suffer from computing resource waste or are unable to support the range of similarity measures that are being used. We propose a distributed in-memory management framework called REPOSE for processing top-k trajectory similarity queries on Spark. We develop a reference point trie (RP-Trie) index to organize trajectory data for local search. In addition, we design a novel heterogeneous global partitioning strategy to eliminate load imbalance in distributed settings. We report on extensive experiments with real-world data that offer insight into the performance of the solution, and show that the solution is capable of outperforming the state-of-the-art proposals.

OriginalsprogEngelsk
TitelProceedings - 2021 IEEE 37th International Conference on Data Engineering, ICDE 2021
Antal sider12
ForlagIEEE Computer Society Press
Publikationsdatoapr. 2021
Sider708-719
Artikelnummer9458807
ISBN (Trykt)978-1-7281-9185-0
ISBN (Elektronisk)978-1-7281-9184-3
DOI
StatusUdgivet - apr. 2021
Begivenhed37th IEEE International Conference on Data Engineering, ICDE 2021 - Virtual, Chania, Grækenland
Varighed: 19 apr. 202122 apr. 2021

Konference

Konference37th IEEE International Conference on Data Engineering, ICDE 2021
Land/OmrådeGrækenland
ByVirtual, Chania
Periode19/04/202122/04/2021
NavnProceedings - International Conference on Data Engineering
ISSN1084-4627

Fingeraftryk

Dyk ned i forskningsemnerne om 'REPOSE: Distributed top-k trajectory similarity search with local reference point tries'. Sammen danner de et unikt fingeraftryk.

Citationsformater