Best Position Algorithms for Top-k Queries

Abstract : The general problem of answering top-k queries can be modeled using lists of data items sorted by their local scores. The most efficient algorithm proposed so far for answering top-k queries over sorted lists is the Threshold Algorithm (TA). However, TA may still incur a lot of useless accesses to the lists. In this paper, we propose two new algorithms which stop much sooner. First, we propose the best position algorithm (BPA) which executes top-k queries more efficiently than TA. For any database instance (i.e. set of sorted lists), we prove that BPA stops as early as TA, and that its execution cost is never higher than TA. We show that the position at which BPA stops can be (m-1) times lower than that of TA, where m is the number of lists. We also show that the execution cost of our algorithm can be (m-1) times lower than that of TA. Second, we propose the BPA2 algorithm which is much more efficient than BPA. We show that the number of accesses to the lists done by BPA2 can be about (m-1) times lower than that of BPA. Our performance evaluation shows that over our test databases, BPA and BPA2 achieve significant performance gains in comparison with TA.
Type de document :
Communication dans un congrès
ACM. International Conference on Very Large Data Bases (VLDB), Aug 2007, Vienna, Austria. ACM, pp.495-506, 2007
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00378836
Contributeur : Reza Akbarinia <>
Soumis le : lundi 15 février 2010 - 16:20:54
Dernière modification le : mercredi 11 avril 2018 - 01:57:11
Document(s) archivé(s) le : jeudi 10 juin 2010 - 18:32:01

Fichier

VLDB07-_Best_Position_Algorith...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00378836, version 1

Collections

Citation

Reza Akbarinia, Esther Pacitti, Patrick Valduriez. Best Position Algorithms for Top-k Queries. ACM. International Conference on Very Large Data Bases (VLDB), Aug 2007, Vienna, Austria. ACM, pp.495-506, 2007. 〈inria-00378836〉

Partager

Métriques

Consultations de la notice

444

Téléchargements de fichiers

292