A Peer-to-Peer system is a distributed system whose component nodes participate in similar roles. Every user node (the peer) can exchange and contribute its resources to another one in the system. Similar to the case that peers may dynamically join and leave the system, the data will also be inserted into and removed from the system dynamically. Given a certain range, a range query will find any data item whose value within the range. For example, a range query can find all the Beatle's works between 1961 and 1968 for us. However, once the range data is distributed over a P2P system through the hash function which has been used largely in many P2P systems, the continuity of the range data is not guaranteed to exist. Therefore, finding the scattered data whose value within a certain range costs much in a P2P system. The Distributed Segment Tree method (DST) preserves the local continuity of the range data at each node by using a segment tree and can break any given range into minimum number of node intervals whose union constitutes the whole requested range. The DST method works based on the Distributed Hash Table (DHT) logic; therefore, 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 still may not be balanced. The main reason of these problems is that the DST method applies the DHT logic to the P2P systems. Therefore, in this thesis, 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. In fact, the P2P network topology of an SST is the structure of a segment tree. Unlike a DST, an SST can fully reflect the properties of the original segment tree. 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. The union of data intervals at a level with full nodes is totally the whole data range which the P2P system can support. When searching a data range, the SST method sends as many number of requests as needed. In addition, we add sibling links to preserve the spatial locality and speed up the search efficiency. For the issue of load balance, our SST method also performs better than the DST method. From our simulation, we show that the SST method routes less number of peers to locate the requested range data than the DST method. We also show that the load based on our method is more balanced than that based on the DST method.

We describe a data structure and algorithms based on segment trees. They are used to manage different versions of a document and to reconstruct the version which was valid at a given time in the past or to get the most recent version. Difficulties arise because it is not known when a version will be replaced by a newer one. Thus unbounded time intervals are to be handled. The data structure also supports the retrieval of the history of a document.