TY - GEN
T1 - LHT
T2 - 28th International Conference on Distributed Computing Systems, ICDCS 2008
AU - Tang, Yuzhe
AU - Zhou, Shuigeng
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=51849166835&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=51849166835&partnerID=8YFLogxK
U2 - 10.1109/ICDCS.2008.61
DO - 10.1109/ICDCS.2008.61
M3 - Conference contribution
AN - SCOPUS:51849166835
SN - 9780769531724
T3 - Proceedings - The 28th International Conference on Distributed Computing Systems, ICDCS 2008
SP - 141
EP - 151
BT - Proceedings - The 28th International Conference on Distributed Computing Systems, ICDCS 2008
Y2 - 17 July 2008 through 20 July 2008
ER -