P-ring: an efficient and robust P2P range index structure

ABSTRACT

Peer-to-peer systems have emerged as a robust, scalable and decentralized way to share and publish data. In this paper, we propose P-Ring, a new P2P index structure that supports both equality and range queries. P-Ring is fault-tolerant, provides logarithmic search performance even for highly skewed data distributions and efficiently supports large sets of data items per peer. We experimentally evaluate P-Ring using both simulations and a real distributed deployment on PlanetLab, and we compare its performance with Skip Graphs, Online Balancing and Chord.

REFERENCES

• 1: PlanetLab website, www.planet-lab.org.
• 2: K. Aberer. P-grid: A self-organizing access structure for p2p information systems. In CoopIS, 2001.
• 3: J. Aspnes and G. Shah. Skip graphs. In SODA, 2003.
• 4: Ashwin R. Bharambe , Mukesh Agrawal , Srinivasan Seshan, Mercury: supporting scalable multi-attribute range queries, ACM SIGCOMM Computer Communication Review, v.34 n.4, October 2004
• 5: A. Crainiceanu, P. Linga, J. Gehrke, andJ. Shanmugasundaram. Querying peer-to-peer networksusing p--trees. In WebDB, 2004.
• 6: A. Crainiceanu, P. Linga, A. Machanavajjhala, J. Gehrke,and J. Shanmugasundaram. An indexing framework for peer-to-peer systems. In WWW (poster), 2004.
• 7: A. Crainiceanu, P. Linga, A. Machanavajjhala, J. Gehrke, and J. Shanmugasundaram. P-ring: An index structure for peer-to-peer systems. Technical report, Cornell University, http://www.cs.cornell.edu/database/Pepper/Pepper.htm,2004.
• 8: F. Dabek, M. F. Kaashoek, D. Karger, R. Morris, and I. Stoica. Wide-area cooperative storage with CFS. In SOSP, 2001.
• 9: A. Daskos, S. Ghandeharizadeh, and X. An. Peper: A distributed range addressing space for p2p systems. In DBISP2P, 2003.
• 10: A. Datta, M. Hauswirth, R. John, R. Schmidt, and K. Aberer. Range-queries in trie-structured overlays. In P2P Comp. 05.
• 11: P. Ganesan, M. Bawa, and H. Garcia-Molina. Online balancing of range-partitioned data with applications to peer-to-peer systems. In VLDB, 2004.
• 12: A. Gupta, D. Agrawal, and A. El Abbadi. Approximate range selection queries in peer-to-peer systems. In CIDR, 2003.
• 13: H. Jagadish, B. C. Ooi, K. L. Tan, Q. H. Vu, and R. Zhang. Speeding up search in peer-to-peer networks with a multi-way tree structure. In SIGMOD, 2006.
• 14: H. Jagadish, B. C. Ooi, and Q. H. Vu. Baton: A balanced tree structure for peer-to-peer networks. In VLDB, 2005.
• 15: P. Linga, A. Crainiceanu, J. Gehrke, and J. Shanmugasundaram. Guaranteeing correctness and availability in p2p range indices. In SIGMOD, 2005.
• 16: W. Litwin, M. A. Neimat, and D. A. Schneider. Lh* - linear hashing for distributed files. In SIGMOD, 1993.
• 17: W. Litwin, M. A. Neimat, and D. A. Schneider. Rp*: A family of order preserving scalable distributed data structures. In VLDB, 1994.
• 18: D. B. Lomet. Replicated indexes for distributed data. In PDIS, 1996.
• 19: S. Ratnasamy et al. A scalable content-addressable network. In SIGCOMM, 2001.
• 20: Sean Rhea , Dennis Geels , Timothy Roscoe , John Kubiatowicz, Handling churn in a DHT, Proceedings of the USENIX Annual Technical Conference 2004 on USENIX Annual Technical Conference, p.10-10, June 27-July 02, 2004, Boston, MA
• 21: A. Rowstron and P. Druschel. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In Middleware, 2001.
• 22: O. D. Sahin, A. Gupta, D. Agrawal, and A. El Abbadi. A p2p framework for caching range queries. In ICDE, 2004.
• 23: I. Stoica et al. Chord: A scalable peer-to-peer lookup service for internet applications. In SIGCOMM, 2001.
• 24: B. Y. Zhao, J. Kubiatowicz, and A. Joseph. Tapestry: an infrastructure for fault-tolerant wide-area location and routing. In Technical Report, U.C.Berkeley, 2001.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

General Terms:
Algorithms, Management, Performance

Keywords:
load balancing, peer-to-peer systems, range queries