Distributed arbitrary segment trees: Providing efficient range query support over public DHT services

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Authors

Colleges, School and Institutes

External organisations

  • University of Warwick

Abstract

In this paper we define a Distributed Arbitrary Segment Tree (DAST), a distributed tree-like structure that layers the range query processing mechanism over public Distributed Hash Table (DHT) services. Compared with traditional segment trees, the arbitrary segment tree used by a DAST reduces the number of key-space segments that need to be maintained, which in turn results in fewer query operations and lower overheads. Moreover, considering that range queries often contain redundant entries that the clients do not need, we introduce the concept of Accuracy of Results (AoR) for range queries. We demonstrate that by adjusting AoR, the DHT operational overhead can be improved. DAST is implemented on a well-known public DHT service (OpenDHT) and validation through experimentation and supporting simulation is performed. The results demonstrate the effectiveness of DAST over exiting methods.

Details

Original languageEnglish
Title of host publication18th Annual IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, PIMRC'07
Publication statusPublished - 2007
Event18th Annual IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, PIMRC'07 - Athens, Greece
Duration: 3 Sep 20077 Sep 2007

Publication series

NameIEEE International Symposium on Personal, Indoor and Mobile Radio Communications, PIMRC

Conference

Conference18th Annual IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, PIMRC'07
Country/TerritoryGreece
CityAthens
Period3/09/077/09/07

ASJC Scopus subject areas