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

https://hal.inria.fr/inria-00482363
Contributor : Reza Akbarinia <>
Submitted on : Sunday, July 17, 2016 - 9:54:32 AM
Last modification on : Monday, November 30, 2020 - 11:04:12 AM

File

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

Identifiers

  • HAL Id : inria-00482363, version 1

Collections

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

Share

Metrics

Record views

506

Files downloads

86