The maximum trajectory coverage query in spatial databases

Ali, M, Eusuf, S, Abdullah, K, Choudhury, F, Culpepper, J and Sellis, T 2018, 'The maximum trajectory coverage query in spatial databases', Proceedings of the VLDB Endowment, vol. 12, no. 3, pp. 197-209.


Document type: Journal Article
Collection: Journal Articles

Title The maximum trajectory coverage query in spatial databases
Author(s) Ali, M
Eusuf, S
Abdullah, K
Choudhury, F
Culpepper, J
Sellis, T
Year 2018
Journal name Proceedings of the VLDB Endowment
Volume number 12
Issue number 3
Start page 197
End page 209
Total pages 13
Publisher Association for Computing Machinery
Abstract With the widespread use of GPS-enabled mobile devices, an unprecedented amount of trajectory data has become available from various sources such as Bikely, GPS-wayPoints, and Uber. The rise of smart transportation services and recent break-throughs in autonomous vehicles increase our reliance on trajectory data in a wide variety of applications. Supporting these services in emerging platforms requires more efficient query processing in trajectory databases. In this paper, we propose two new coverage queries for trajectory databases: (i) k Best Facility Trajectory Search (kBFT); and (ii) k Best Coverage Facility Trajectory Search (kBCovFT). We propose a novel index structure, the Trajectory Quadtree (TQtree) that utilizes a quadtree to hierarchically organize trajectories into different nodes, and then applies a z-ordering to further organize the trajectories by spatial locality inside each node. This structure is highly effective in pruning the trajectory search space, which is of independent interest. By exploiting the TQ-tree, we develop a divide-and-conquer approach to efficiently process a kBFT query. To solve the kBCovFT, which is a non-submodular NP-hard problem, we propose a greedy approximation. We evaluate our algorithms through an extensive experimental study on several real datasets, and demonstrate that our algorithms outperform baselines by two to three orders of magnitude.
Subject Data Structures
Database Management
Keyword(s) spatial computing
DOI - identifier 10.14778/3291264.3291266
Copyright notice © the owner/author(s).
ISSN 2150-8097
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 1 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 0 times in Scopus Article
Altmetric details:
Access Statistics: 12 Abstract Views  -  Detailed Statistics
Created: Tue, 26 Mar 2019, 09:36:00 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us