Scalable Algorithms for Nearest-Neighbor Joins on Big Trajectory Data
Authors:
- 19 October 2015
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 28 (3) , 785-800
Abstract
Trajectory data are prevalent in systems that monitor the locations of moving objects. In a location-based service, for instance, the positions of vehicles are continuously monitored through GPS; the trajectory of each vehicle describes its movement history. We study joins on two sets of trajectories, generated by two sets M and R of moving objects. For each entity in M, a join returns its k nearest neighbors from R. We examine how this query can be evaluated in cloud environments. This problem is not trivial, due to the complexity of the trajectory, and the fact that both the spatial and temporal dimensions of the data have to be handled. To facilitate this operation, we propose a parallel solution framework based on MapReduce. We also develop a novel bounding technique, which enables trajectories to be pruned in parallel. Our approach can be used to parallelize existing single-machine trajectory join algorithms. We also study a variant of the join, which can further improve query efficiency. To evaluate the efficiency and the scalability of our solutions, we have performed extensive experiments on large real and synthetic datasets.Keywords
Funding Information
- RGC
- HKU (17205115)
This publication has 24 references indexed in Scilit:
- Skew-Aware Join Optimization for Array Databases2015
- Efficient multi-way theta-join processing using MapReduceProceedings of the VLDB Endowment, 2012
- Efficient processing of k nearest neighbor joins using MapReduceProceedings of the VLDB Endowment, 2012
- An Efficient Inter Mode Decision Method for MVCProcedia Engineering, 2012
- MapReduceCommunications of the ACM, 2008
- Evolution of the Frequency of Luminous (≥LV⋆) Close Galaxy Pairs at z < 1.2 in the COSMOS Field*The Astrophysical Journal Supplement Series, 2007
- Nearest and reverse nearest neighbor queries for moving objectsThe VLDB Journal, 2006
- The solar neighborhood IV: discovery of the twentieth nearest starThe Astronomical Journal, 1997
- The spatial correlation function of rich clusters of galaxiesThe Astrophysical Journal, 1983
- Symmetric binary B-Trees: Data structure and maintenance algorithmsActa Informatica, 1972