Answering Complex Queries in Peer-to-Peer Systems

Other Titles
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.
Journal / Series
Volume & Issue
Date Issued
peer-to-peer systems; range index; databases; complex queries
Effective Date
Expiration Date
Union Local
Number of Workers
Committee Chair
Committee Co-Chair
Committee Member
Degree Discipline
Degree Name
Degree Level
Related Version
Related DOI
Related To
Related Part
Based on Related Item
Has Other Format(s)
Part of Related Item
Related To
Related Publication(s)
Link(s) to Related Publication(s)
Link(s) to Reference(s)
Previously Published As
Government Document
Other Identifiers
Rights URI
dissertation or thesis
Accessibility Feature
Accessibility Hazard
Accessibility Summary
Link(s) to Catalog Record