Answering Complex Queries in Peer-to-Peer Systems

Crainiceanu, Adina

Answering Complex Queries in Peer-to-Peer Systems

Abstract

Peer-to-peer (P2P) systems provide a robust, scalable and decentralized way to share and publish data. However, most existing P2P systems only support equality or keyword search queries. We believe that future P2P applications, such as digital libraries, resource discovery on a grid, or military applications, will require more complex query functionality, as users will publish semantically rich data. Towards the goal of supporting complex queries in P2P systems, this dissertation focuses on developing index structures that allow fast access to distributed data. We introduce first a general modular indexing framework that identifies and separates the different functional components of a P2P index structure. One of the benefits of such a framework is that it allows \eat{tailoring the index structure to the needs of the different applications, with different requirements. Another benefit is that it allows }reusing the existing algorithms for different components rather than implementing everything anew. We can thus concentrate on creating algorithms that provide new functionality. We introduce P-Tree, a distributed fault-tolerant index structure. P-Trees support range queries in addition to equality queries in P2P systems in which each user (peer) publishes a small number of data items. We describe algorithms to maintain a P-Tree under insertions and deletions of data items/peers, and evaluate its performance using both a simulation and a real distributed implementation. Our results show the efficacy of our approach. We introduce then P-Ring, a novel index structure based on our framework, that supports both equality and range queries, is fault-tolerant, efficiently supports large sets of data items per peer (as opposed to P-Tree), and provides guaranteed logarithmic search performance in a stable system. In a thorough Wide Area Network experimental study we evaluate the performance of P-Ring and \eat{ we quantify the performance trade-offs of the different system components. We also }compare P-Ring with three other P2P index structures, Chord, Skip Graphs, and Online Balancing, implemented in the context of our indexing framework. Our performance results indicate that P-Ring outperforms Skip Graphs in terms of both query and maintenance cost. P-Ring offers a better load balance than Online Balancing, at a lower cost. P-Ring outperforms Chord in terms of search performance and supports a larger class of queries, with a low overhead.

Date Issued

2006-02-08T13:52:12Z

Keywords

peer-to-peer systems; range index; databases; complex queries

Types

dissertation or thesis