TY - JOUR
T1 - LIGHT
T2 - A query-efficient yet low-maintenance indexing scheme over DHTs
AU - Tang, Yuzhe
AU - Zhou, Shuigeng
AU - Xu, Jianliang
N1 - Funding Information:
The authors would like to thank the anonymous reviewers. This work was supported by the National Natural Science Foundation of China under Grant Nos. 60573183, 90612007, and 60873070, and Shanghai Leading Academic Discipline Project No. B114. Shuigeng Zhou’s work was also supported by K.C. Wong Education Foundation-HKBU. Jianliang Xu’s work was supported by grants from the Research Grants Council, Hong Kong SAR, China (Project Nos. HKBU211307 and HKBU210808).
PY - 2010/1
Y1 - 2010/1
N2 - DHT is a widely used building block for scalable P2P systems. However, as uniform hashing employed in DHTs destroys data locality, it is not a trivial task to support complex queries (e.g., range queries and k-nearest-neighbor queries) in DHT-based P2P systems. In order to support efficient processing of such complex queries, a popular solution is to build indexes on top of the DHT. Unfortunately, existing over-DHT indexing schemes suffer from either query inefficiency or high maintenance cost. In this paper, we propose LIGhtweight Hash Tree (LIGHT)a query-efficient yet low-maintenance indexing scheme. LIGHT employs a novel naming mechanism and a tree summarization strategy for graceful distribution of its index structure. We show through analysis that it can support various complex queries with near-optimal performance. Extensive experimental results also demonstrate that, compared with state of the art over-DHT indexing schemes, LIGHT saves 50-75 percent of index maintenance cost and substantially improves query performance in terms of both response time and bandwidth consumption. In addition, LIGHT is designed over generic DHTs and hence can be easily implemented and deployed in any DHT-based P2P system.
AB - DHT is a widely used building block for scalable P2P systems. However, as uniform hashing employed in DHTs destroys data locality, it is not a trivial task to support complex queries (e.g., range queries and k-nearest-neighbor queries) in DHT-based P2P systems. In order to support efficient processing of such complex queries, a popular solution is to build indexes on top of the DHT. Unfortunately, existing over-DHT indexing schemes suffer from either query inefficiency or high maintenance cost. In this paper, we propose LIGhtweight Hash Tree (LIGHT)a query-efficient yet low-maintenance indexing scheme. LIGHT employs a novel naming mechanism and a tree summarization strategy for graceful distribution of its index structure. We show through analysis that it can support various complex queries with near-optimal performance. Extensive experimental results also demonstrate that, compared with state of the art over-DHT indexing schemes, LIGHT saves 50-75 percent of index maintenance cost and substantially improves query performance in terms of both response time and bandwidth consumption. In addition, LIGHT is designed over generic DHTs and hence can be easily implemented and deployed in any DHT-based P2P system.
KW - Complex queries.
KW - Distributed hash tables
KW - Indexing
UR - http://www.scopus.com/inward/record.url?scp=72949107124&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=72949107124&partnerID=8YFLogxK
U2 - 10.1109/TKDE.2009.47
DO - 10.1109/TKDE.2009.47
M3 - Article
AN - SCOPUS:72949107124
SN - 1041-4347
VL - 22
SP - 59
EP - 75
JO - IEEE Transactions on Knowledge and Data Engineering
JF - IEEE Transactions on Knowledge and Data Engineering
IS - 1
M1 - 4782960
ER -