As-Soon-As-Possible Top-k Query Processing in P2P Systems

William Kokou Dedzoe 1, 2 Philippe Lamarre 3 Reza Akbarinia 2 Patrick Valduriez 2
1 LINA - Laboratoire d'Informatique de Nantes Atlantique
2 ZENITH - Scientific Data Management
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
3 BD - Base de Données
LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
Abstract : Top-k query processing techniques provide two main advantages for unstructured peer-to-peer (P2P) systems. First they avoid overwhelming users with too many results. Second they reduce significantly network resources consumption. 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 these notions, we formally define the as-soonas-possible (ASAP) top-k processing problem. Then, we propose a family of algorithms called ASAP to deal with this problem. We validate 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 :
Article dans une revue
Transactions on Large-Scale Data- and Knowledge-Centered Systems, Springer Berlin / Heidelberg, 2013, Part IX, LNCS (7980), pp.1-27. 〈10.1007/978-3-642-40069-8_1〉
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00821929
Contributeur : Reza Akbarinia <>
Soumis le : lundi 13 mai 2013 - 15:23:37
Dernière modification le : jeudi 24 mai 2018 - 15:59:21
Document(s) archivé(s) le : lundi 19 août 2013 - 15:50:39

Fichier

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

Identifiants

Collections

INRIA | UNIV-NANTES | LINA | ZENITH | INSA-LYON | LIRMM | LIRIS | EC-LYON | UNIV-LYON2 | MIPS | UNIV-MONTPELLIER | UNIV-LYON1

Citation

William Kokou Dedzoe, Philippe Lamarre, Reza Akbarinia, Patrick Valduriez. As-Soon-As-Possible Top-k Query Processing in P2P Systems. Transactions on Large-Scale Data- and Knowledge-Centered Systems, Springer Berlin / Heidelberg, 2013, Part IX, LNCS (7980), pp.1-27. 〈10.1007/978-3-642-40069-8_1〉. 〈lirmm-00821929〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

604

Téléchargements de fichiers

367

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD