Range Queries Based on a Structured Segment Tree in P2P Systems

摘要

Range queries will find any data item whose value within the range. The Distributed Segment Tree method (DST) is a famous method for range queries in P2P systems. It uses a segment tree to preserve the local continuity of the range data at each node based on the Distributed Hash Table (DHT) logic. It can be applied in any DHT-based P2P system. However, data distribution of the DST method may cause overlapping. When searching a data range, the DST method sends more number of requests than what is really needed. Although the DST method designs the Downward Load Stripping Mechanism, the load on peers may still not be balanced. Therefore, in this paper, we propose a method called Structured Segment Tree (SST) that does not use the DHT logic but embeds the structure of the segment tree into the P2P systems. Each peer in our proposed P2P system represents a node of a segment tree. Data intervals at the same level are continuous and will not overlap with each other. In addition, we add sibling links to preserve the spatial locality and speed up the search efficiency. From our simulation, we have shown that the SST method routes less number of peers to locate the requested range data than the DST method. We have also shown that the load based on our method is more balanced than that based on the DST method.