Research Article
A Scalable Index Architecture for Supporting Multi-Dimensional Range Queries in Peer-to-Peer Networks
@INPROCEEDINGS{10.1109/COLCOM.2006.361862, author={Xiaoyu Yang and Yiming Hu}, title={A Scalable Index Architecture for Supporting Multi-Dimensional Range Queries in Peer-to-Peer Networks}, proceedings={2nd International ICST Conference on Collaborative Computing: Networking, Applications and Worksharing}, publisher={IEEE}, proceedings_a={COLLABORATECOM}, year={2007}, month={5}, keywords={Buildings Computer architecture Computer networks Computer science Costs Distributed computing Indexing Large-scale systems Peer to peer computing Scalability}, doi={10.1109/COLCOM.2006.361862} }- Xiaoyu Yang
Yiming Hu
Year: 2007
A Scalable Index Architecture for Supporting Multi-Dimensional Range Queries in Peer-to-Peer Networks
COLLABORATECOM
IEEE
DOI: 10.1109/COLCOM.2006.361862
Abstract
Distributed hash table based peer-to-peer systems are emerging as new paradigms for building large-scale distributed applications, due to their scalability, fault-tolerance and self-organization. However, most existing DHTs are designed for exact-key searching, and the support of multi-dimensional range queries in peer-to-peer networks is still a challenging problem. In this paper, we propose a distributed index architecture called Dak to support range queries on multi-dimensional data. Based on efficient space mapping and query routing mechanisms, Dak can provide a scalable platform to support any number of indexes with different dimensionalities. Significantly, this architecture does not need to generate or maintain any search trees. Instead, it exploits the embedded trees in the underlying distributed hash tables to refine and deliver queries. To deal with skewed data distribution, we also provide load-balancing mechanisms to ensure that no node in the system is unduly loaded.