Distributed Mining of Popular Paths in Road Networks

Panagiota Katsikouli 1, 2 Maria Astefanoaei 1 Rik Sarkar 1
2 AGORA - ALGorithmes et Optimisation pour Réseaux Autonomes
Inria Grenoble - Rhône-Alpes, CITI - CITI Centre of Innovation in Telecommunications and Integration of services
Abstract : We consider the problem of finding large scale mobility patterns. A common challenge in mobility tracking systems is that large quantity of data is spread out spatially and temporally across many tracking sensors. We thus devise a spatial sampling and information exchange protocol that provides probabilistic guarantees on detecting prominent patterns. For this purpose, we define a general notion of significant popular paths that can capture many different types of motion. We design a summary sketch for the data at each tracking node, which can be updated efficiently, and then aggregated across devices to reconstruct the prominent paths in the global data. The algorithm is scalable, even with large number of mobile targets. It uses a hierarchic query system that automatically prioritizes important trajectories – those that are long and popular. We show further that this scheme can in fact give good results by sampling relatively few sensors and targets, and works for streaming spatial data. We prove differential privacy guarantees for the randomized algorithm. Extensive experiments on real GPS data show that the method is efficient and accurate, and is useful in predicting motion of travelers even with small samples.
Type de document :
Communication dans un congrès
DCOSS 2018 - International Conference on Distributed Computing in Sensor Systems, Jun 2018, New York City, United States. IEEE, pp.1-8, 2018
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01768273
Contributeur : Panagiota Katsikouli <>
Soumis le : mardi 17 avril 2018 - 10:12:16
Dernière modification le : mercredi 18 avril 2018 - 14:23:19

Fichier

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

Identifiants

  • HAL Id : hal-01768273, version 1

Collections

Citation

Panagiota Katsikouli, Maria Astefanoaei, Rik Sarkar. Distributed Mining of Popular Paths in Road Networks. DCOSS 2018 - International Conference on Distributed Computing in Sensor Systems, Jun 2018, New York City, United States. IEEE, pp.1-8, 2018. 〈hal-01768273〉

Partager

Métriques

Consultations de la notice

49

Téléchargements de fichiers

34