P2P framework for supporting multi-dimensional range query

How to efficiently support multi-dimensional range search is one of the research hotspots in the traditional data management area. The design and implementation of multi-dimensional range query processing in large-scale distributed systems, however, remains to be a great challenge. VBI-tree is a peer-to-peer indexing framework based on a balanced tree structure overlay and it can support any kind of multi-dimensional hierarchical tree structures such as R-tree, X-tree, and M-tree to be implemented in peer-to-peer computing environment. VBI-tree designs the search algorithms which can start from any position or any node instead of the root node used in the centralized hierarchical tree structures, thus successfully avoiding the performance bottleneck problem introduced by the root node. Specifically, in a network with N nodes, it guarantees that queries can be answered within O(log N) hops. It takes network restructuring based on AVL-tree rotation method as the load balancing strategy, which can balance work load efficiently. Additionally, a succinct structure of VBI*-tree is provided by setting up special ancestor-descendant links when facing a large number of data operations, which can improve the indexing performance. By using such new links, it is ensured that the related area checking to the queries will happen among the nodes of the same level to the greatest extent instead of sending checking requests directly to high level nodes, thereby reducing the load of high level nodes and also system updating cost. Experimental results validate the efficiency and effectiveness of the proposed approach.