Concepedia

VBI-Tree: A Peer-to-Peer Framework for Supporting Multi-Dimensional Indexing Schemes

H. V. Jagadish, Beng Chin Ooi, Quang Hieu Vu, Rong Zhang, Aoying Zhou

2006 · 149 citations · 17 references

TL;DR

Multi‑dimensional data indexing has been extensively studied in centralized databases, but little work has addressed it in peer‑to‑peer systems. The paper proposes a peer‑to‑peer framework using a balanced tree overlay to support various multidimensional tree structures for mapping and query processing. The framework employs a balanced tree overlay and incorporates a load‑balancing strategy that distributes workload evenly across nodes. Experiments show that the framework answers point and range queries in O(log N) hops and demonstrates practical feasibility.

Abstract

Multi-dimensional data indexing has received much attention in a centralized database. However, not so much work has been done on this topic in the context of Peerto- Peer systems. In this paper, we propose a new Peer-to- Peer framework based on a balanced tree structure overlay, which can support extensible centralized mapping methods and query processing based on a variety of multidimensional tree structures, including R-Tree, X-Tree, SSTree, and M-Tree. Specifically, in a network with N nodes, our framework guarantees that point queries and range queries can be answered within O(logN) hops. We also provide an effective load balancing strategy to allow nodes to balance their work load efficiently. An experimental assessment validates the practicality of our proposal.