Efficient Early Top-k Query Processing in Overloaded P2P Systems

William Kokou Dedzoe 1 Philippe Lamarre 1 Reza Akbarinia 2 Patrick Valduriez 2, 3
2 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 in P2P systems has focused on efficiently computing the top-k results while reducing network traffic and query response time. However, in overloaded P2P systems (with very high query loads), some peers may take a long time to answer, thus making the user wait a long time to obtain the final top-k result. In this paper, we address this problem, which we reformulate as early top-k query processing in P2P systems. First, to complement response time, we introduce two new metrics, stabilization time and cumulative quality gap, with which we formally define the problem. Then, we propose an efficient algorithm that dynamically adapts to query loads of peers in order to return to the user top-k results as soon as possible, without waiting for the final result. We validated our solution through simulations over a real dataset. The results show that our solution significantly outperforms baseline solutions by returning high quality top-k results to users in much better times.
Type de document :
Communication dans un congrès
DEXA'2011: 22nd International Conference on Database and Expert Systems Applications, Toulouse, France. Springer, pp.140-155, 2011, LNCS
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00607920
Contributeur : Reza Akbarinia <>
Soumis le : lundi 11 juillet 2011 - 16:56:42
Dernière modification le : jeudi 11 janvier 2018 - 16:59:01
Document(s) archivé(s) le : lundi 12 novembre 2012 - 10:45:17

Fichier

2011_-_DEXA_-_Effi_cient_Early...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00607920, version 1

Citation

William Kokou Dedzoe, Philippe Lamarre, Reza Akbarinia, Patrick Valduriez. Efficient Early Top-k Query Processing in Overloaded P2P Systems. DEXA'2011: 22nd International Conference on Database and Expert Systems Applications, Toulouse, France. Springer, pp.140-155, 2011, LNCS. 〈lirmm-00607920〉

Partager

Métriques

Consultations de la notice

504

Téléchargements de fichiers

237