TY - JOUR
T1 - A lightweight multidimensional index for complex queries over DHTs
AU - Tang, Yuzhe
AU - Xu, Jianliang
AU - Zhou, Shuigeng
AU - Lee, Wang Chien
AU - Deng, Dingxiong
AU - Wang, Yue
N1 - Funding Information:
The work of Yuezhe Tang, Shuigeng Zhou, Dingxiong Deng, and Yue Wang were supported by the National Basic Research Program of China under Grant No. 2007CB310806, National Natural Science Foundation of China (NSFC) under Grant No. 60873070, and 863 Program under Grant No. 2009AA01Z135. Shuigeng Zhou was also supported by K.C. Wong Education Foundation-HKBU. Jianliang Xu’s work was supported by the Research Grants Council of Hong Kong under Projects HKBU211307 and HKBU211510. Wang-Chien Lee was supported in part by US National Science Foundation Grant CNS-0626709 and Grant IIS-0534343.
PY - 2011
Y1 - 2011
N2 - In this paper, we study the problem of indexing multidimensional data in P2P networks based on distributed hash tables (DHTs). We advocate the indexing approach that superimposes a multidimensional index tree on top of a DHTa paradigm that keeps the underlying DHT intact while being able to adapt to any DHT substrate. In this context, we identify several index design issues and propose a novel indexing scheme called multidimensional Lightweight Hash Tree (m-LIGHT). First, to preserve data locality, m-LIGHT employs a clever naming mechanism that gracefully maps a tree-based index into the DHT and contributes to high efficiency in both index maintenance and query processing. Second, to tackle the load balancing issue, m-LIGHT leverages a new data-aware splitting strategy that achieves optimal load balance under a fixed index size. We present detailed algorithms for processing complex queries over the m-LIGHT index. We also conduct an extensive performance evaluation of m-LIGHT in comparison with several state-of-the-art indexing schemes. The experimental results show that m-LIGHT substantially reduces index maintenance overhead and improves query performance in terms of both bandwidth consumption and response latency.
AB - In this paper, we study the problem of indexing multidimensional data in P2P networks based on distributed hash tables (DHTs). We advocate the indexing approach that superimposes a multidimensional index tree on top of a DHTa paradigm that keeps the underlying DHT intact while being able to adapt to any DHT substrate. In this context, we identify several index design issues and propose a novel indexing scheme called multidimensional Lightweight Hash Tree (m-LIGHT). First, to preserve data locality, m-LIGHT employs a clever naming mechanism that gracefully maps a tree-based index into the DHT and contributes to high efficiency in both index maintenance and query processing. Second, to tackle the load balancing issue, m-LIGHT leverages a new data-aware splitting strategy that achieves optimal load balance under a fixed index size. We present detailed algorithms for processing complex queries over the m-LIGHT index. We also conduct an extensive performance evaluation of m-LIGHT in comparison with several state-of-the-art indexing schemes. The experimental results show that m-LIGHT substantially reduces index maintenance overhead and improves query performance in terms of both bandwidth consumption and response latency.
UR - https://www.scopus.com/pages/publications/80055031427
UR - https://www.scopus.com/pages/publications/80055031427#tab=citedBy
U2 - 10.1109/TPDS.2011.91
DO - 10.1109/TPDS.2011.91
M3 - Article
AN - SCOPUS:80055031427
SN - 1045-9219
VL - 22
SP - 2046
EP - 2054
JO - IEEE Transactions on Parallel and Distributed Systems
JF - IEEE Transactions on Parallel and Distributed Systems
IS - 12
M1 - 5733347
ER -