An Efficient Mechanism for Processing Top-k Queries in DHTs

Reza Akbarinia 1 Esther Pacitti 2 Patrick Valduriez 1, 3
1 ATLAS - Complex data management in distributed systems
UN - Université de Nantes, Inria Rennes – Bretagne 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
Abstract : We consider the problem of top-k query processing in Distributed Hash Tables (DHTs). The most efficient approaches for top-k query processing in centralized and distributed systems are based on the Threshold Algorithm (TA) which is applicable for queries where the scoring function is monotone. However, the specific interface of DHTs, i.e. data storage and retrieval based on keys, makes it hard to develop TA-style top-k query processing algorithms. In this paper, we propose an efficient mechanism for top-k query processing in DHTs. It is widely applicable to many different DHT implementations. Although our algorithm is TA-style, it is much more general since it supports a large set of non monotone scoring functions including linear functions. In fact, it is the first TA-style algorithm that supports linear scoring functions. We prove analytically the correctness of our algorithm. We have validated our algorithm through a combination of implementation and simulation. The results show very good performance, in terms of communication cost and response time.
Type de document :
Communication dans un congrès
BDA: Bases de Données Avancées, Oct 2006, Lille, France. 2006
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00482363
Contributeur : Reza Akbarinia <>
Soumis le : dimanche 17 juillet 2016 - 09:54:32
Dernière modification le : vendredi 12 janvier 2018 - 01:53:27

Fichier

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

Identifiants

  • HAL Id : inria-00482363, version 1

Citation

Reza Akbarinia, Esther Pacitti, Patrick Valduriez. An Efficient Mechanism for Processing Top-k Queries in DHTs. BDA: Bases de Données Avancées, Oct 2006, Lille, France. 2006. 〈inria-00482363〉

Partager

Métriques

Consultations de la notice

399

Téléchargements de fichiers

37