Carnegie Mellon University
Browse
file.pdf (2.88 MB)

Efficient support for range queries in DHT-based systems

Download (2.88 MB)
journal contribution
posted on 1994-01-01, 00:00 authored by Gao, Peter Alfons. Steenkiste
Abstract: "In recent years, Distributed Hash Tables (DHTs) have been proposed as a fundamental building block for Internet-scale distributed applications. Important functionalities such as searching has been added to the DHT's basic look up capability. However, supporting range queries efficiently remains a difficult problem. In this paper, we describe an efficient algorithm that decomposes a range query with length R[subscript q] into O(log R[subscript q]) sub-queries that are resolved by separate nodes corresponding to each sub-query. Our system utilizes a novel logical tree data structure, the Range Search Tree (RST), which automatically groups registrations based on their values explicitly. Coupled with a dynamic load balancing mechanism, our system can handle both point and range queries efficiently regardless of the distribution of the registrations and queries. Our algorithm is fully distributed and we avoid conventional bottleneck problems encountered by tree-based systems. Extensive simulation results validate the effectiveness of the system."

History

Date

1994-01-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC