LHT: A low-maintenance indexing scheme over DHTs

Yuzhe Tang, Shuigeng Zhou

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

13 Scopus citations

Abstract

DHT is a widely-used building block in P2P systems, and complex queries are gaming popularity in P2P applications. To support efficient query processing over DHTs, effective indexing structures are essential. Recently, a number of indexing schemes have been proposed. However, these schemes have focused on improving query efficiency, and as a trade-off, sacrificed maintenance efficiency - an important performance measure in the P2P context, where frequent data updating and high peer dynamism are typically incurred. In this paper, we propose LHT, a Low maintenance Hash Tree, for efficient data indexing over DHTs. LHT employs a novel naming function and a tree summarization strategy to gracefully distribute its index structure. It is adaptable to any DHT substrates, and is easy to be implemented and deployed. Experiments show that in comparison with the state-of-the-art indexing technique, LHT saves up to 75% (at least 50%) maintenance cost, and achieves better performance for exact-match queries and range queries.

Original languageEnglish (US)
Title of host publicationProceedings - The 28th International Conference on Distributed Computing Systems, ICDCS 2008
Pages141-151
Number of pages11
DOIs
StatePublished - Sep 22 2008
Externally publishedYes
Event28th International Conference on Distributed Computing Systems, ICDCS 2008 - Beijing, China
Duration: Jul 17 2008Jul 20 2008

Publication series

NameProceedings - The 28th International Conference on Distributed Computing Systems, ICDCS 2008

Other

Other28th International Conference on Distributed Computing Systems, ICDCS 2008
CountryChina
CityBeijing
Period7/17/087/20/08

ASJC Scopus subject areas

  • Hardware and Architecture
  • Software

Fingerprint Dive into the research topics of 'LHT: A low-maintenance indexing scheme over DHTs'. Together they form a unique fingerprint.

Cite this