ASAP Top-k Query Processing in Unstructured P2P Systems

William Kokou Dedzoe 1 Philippe Lamarre 1, 2 Reza Akbarinia 3 Patrick Valduriez 2, 3
2 ATLAS - Complex data management in distributed systems
UN - Université de Nantes, Inria Rennes – Bretagne Atlantique
3 ZENITH - Scientific Data Management
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Top-k query processing techniques are useful in unstructured peer-to-peer (P2P) systems, to avoid overwhelming users with too many results. However, existing approaches suffer from long waiting times. This is because top-k results are returned only when all queried peers have finished processing the query. As a result, query response time is dominated by the slowest queried peer. In this paper, we address this users' waiting time problem. For this, we revisit top-k query processing in P2P systems by introducing two novel notions in addition to response time: the stabilization time and the cumulative quality gap. Using thèse notions, we formally define the as-soon-as-possible (ASAP) top-k processing problem. Then, we propose a family of algorithms called ASAP to deal with this problem. We validated our solution through implementation and extensive experimentation. The results show that ASAP significantly outperforms baseline algorithms by returning final top-k result to users in much better times.
Type de document :
Communication dans un congrès
IEEE Tenth International Conference on Peer-To-Peer Computing (P2P), Aug 2011, Kyoto, Netherlands. pp.1-10, 2010
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00607926
Contributeur : Reza Akbarinia <>
Soumis le : lundi 11 juillet 2011 - 17:07:57
Dernière modification le : mercredi 21 novembre 2018 - 19:26:08
Document(s) archivé(s) le : mercredi 12 octobre 2011 - 02:27:57

Fichier

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

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

  • HAL Id : lirmm-00607926, version 1

Citation

William Kokou Dedzoe, Philippe Lamarre, Reza Akbarinia, Patrick Valduriez. ASAP Top-k Query Processing in Unstructured P2P Systems. IEEE Tenth International Conference on Peer-To-Peer Computing (P2P), Aug 2011, Kyoto, Netherlands. pp.1-10, 2010. 〈lirmm-00607926〉

Partager

Métriques

Consultations de la notice

798

Téléchargements de fichiers

1749