Best Position Algorithms for Efficient Top-k Query Processing

Reza Akbarinia 1 Esther Pacitti 1 Patrick Valduriez 1, 2
1 ZENITH - Scientific Data Management
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : The general problem of answering top-k queries can be modeled using lists of data items sorted by their local scores. The main 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 algorithms that are much more efficient than TA. First, we propose the best position algorithm (BPA). 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 there are databases over which BPA executes top-k queries O(m) times faster 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. We evaluated the performance of our algorithms through extensive experimental tests. The results show that over our test databases, BPA and BPA2 achieve significant performance gains in comparison with TA.
Type de document :
Article dans une revue
Information Systems, Elsevier, 2011, 36 (6), pp.973-989
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00607882
Contributeur : Reza Akbarinia <>
Soumis le : lundi 11 juillet 2011 - 16:14:22
Dernière modification le : jeudi 24 mai 2018 - 15:59:21
Document(s) archivé(s) le : mercredi 12 octobre 2011 - 02:25:17

Fichier

2011_-_InfoSys_-_Best_Position...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00607882, version 1

Collections

Citation

Reza Akbarinia, Esther Pacitti, Patrick Valduriez. Best Position Algorithms for Efficient Top-k Query Processing. Information Systems, Elsevier, 2011, 36 (6), pp.973-989. 〈lirmm-00607882〉

Partager

Métriques

Consultations de la notice

797

Téléchargements de fichiers

335