Home // AP2PS 2011, The Third International Conference on Advances in P2P Systems // View article

SGR-Tree: a Skip Graph based R-Tree for multi-dimensional data indexing in Peer-to-Peer systems

Authors:
Quang Hieu Vu

Keywords: Multi-dimensional data indexing, Peer-to-Peer (P2P)

Abstract:
In this paper, we propose SGR-Tree, an index structure for multi-dimensional data in Peer-to-Peer (P2P) systems. SGR-Tree is an R-Tree index structure constructed on top of a Skip Graph, a P2P overlay network. In SGR-Tree, each Skip Graph node corresponds to an R-Tree leaf node. However, different from R-Tree, SGR-Tree does not employ internal nodes for routing purpose. Instead, at each Skip Graph node, we virtually partition the whole system into non-overlapping regions, each of which is connected to the node via a neighbor node. For each region, the node keeps the minimum hyper-rectangle covering all hyper-rectangles, which are in charged by nodes falling in the region. In this way, when a node issues or receives a query, it simply sends or forwards the query to neighbor nodes whose minimum covering hyper-rectangle intersects with the search region. The main advantage of SGRTree is that it can avoid not only the bottleneck problem at the root node but also the high cost of maintaining internal R-Tree nodes, especially when the index structure is often changed. Nevertheless, we prove that SGR-Tree is still able to process multi-dimensional queries efficiently within a boundary of log N steps, where N is the number of nodes in the system. We have done experiments to validate the practicability and efficiency of SGR-Tree.

Pages: 1 to 6

Copyright: Copyright (c) IARIA, 2011

Publication date: November 20, 2011

Published in: conference

ISBN: 978-1-61208-173-1

Location: Lisbon, Portugal

Dates: from November 20, 2011 to November 25, 2011