Scalable Algorithms for Nearest-Neighbor Joins on Big Trajectory Data

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.
Type de document :
Article dans une revue
IEEE Transactions on Knowledge and Data Engineering, Institute of Electrical and Electronics Engineers, 2016, 28 (3), 〈10.1109/TKDE.2015.2492561〉
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01272212
Contributeur : Silviu Maniu <>
Soumis le : mercredi 10 février 2016 - 13:44:13
Dernière modification le : mardi 24 avril 2018 - 13:54:31
Document(s) archivé(s) le : samedi 12 novembre 2016 - 16:59:28

Fichier

knnJoin.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Yixiang Fang, Reynold Cheng, Wenbin Tang, Silviu Maniu, Xuan Yang. Scalable Algorithms for Nearest-Neighbor Joins on Big Trajectory Data. IEEE Transactions on Knowledge and Data Engineering, Institute of Electrical and Electronics Engineers, 2016, 28 (3), 〈10.1109/TKDE.2015.2492561〉. 〈hal-01272212〉

Partager

Métriques

Consultations de la notice

172

Téléchargements de fichiers

109