Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

An Efficient Mechanism for Processing Top-k Queries in DHTs

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download
Contributor : Reza Akbarinia Connect in order to contact the contributor
Submitted on : Sunday, July 17, 2016 - 9:54:32 AM
Last modification on : Wednesday, April 27, 2022 - 4:11:37 AM


An Efficient.pdf
Files produced by the author(s)


  • HAL Id : inria-00482363, version 1



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. ⟨inria-00482363⟩



Record views


Files downloads