More Web Proxy on the site http://driver.im/

Article

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

Authors:

Adina Crainiceanu,

Ashwin Machanavajjhala,

Johannes Gehrke,

Jayavel ShanmugasundaramAuthors Info & Claims

SIGMOD '07: Proceedings of the 2007 ACM SIGMOD international conference on Management of data

Pages 223 - 234

https://doi.org/10.1145/1247480.1247507

Published: 11 June 2007 Publication History

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.

Digital Library

[3]

J. Aspnes and G. Shah. Skip graphs. In SODA, 2003.

Digital Library

[4]

A. R. Bharambe, M. Agrawal, and S. Seshan. Mercury: supporting scalable multi-attribute range queries. SIGCOMM Comput. Commun. Rev., 34(4), 2004.

Digital Library

[5]

A. Crainiceanu, P. Linga, J. Gehrke, andJ. Shanmugasundaram. Querying peer-to-peer networksusing p--trees. In WebDB, 2004.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[14]

H. Jagadish, B. C. Ooi, and Q. H. Vu. Baton: A balanced tree structure for peer-to-peer networks. In VLDB, 2005.

Digital Library

[15]

P. Linga, A. Crainiceanu, J. Gehrke, and J. Shanmugasundaram. Guaranteeing correctness and availability in p2p range indices. In SIGMOD, 2005.

Digital Library

[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.

Digital Library

[18]

D. B. Lomet. Replicated indexes for distributed data. In PDIS, 1996.

Digital Library

[19]

S. Ratnasamy et al. A scalable content-addressable network. In SIGCOMM, 2001.

Digital Library

[20]

S. Rhea, D. Geels, T. Roscoe, and J. Kubiatowicz. Handling churn in a dht. In USENIX Annual Tech Conference, 2004.

Digital Library

[21]

A. Rowstron and P. Druschel. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In Middleware, 2001.

Digital Library

[22]

O. D. Sahin, A. Gupta, D. Agrawal, and A. El Abbadi. A p2p framework for caching range queries. In ICDE, 2004.

Digital Library

[23]

I. Stoica et al. Chord: A scalable peer-to-peer lookup service for internet applications. In SIGCOMM, 2001.

Digital Library

[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.

Digital Library

Cited By

Fan ZYe BWang ZZhong ZGuo JWu YLi HYang TTu YLiu ZCui B(2024)Enabling space-time efficient range queries with REncoderThe VLDB Journal10.1007/s00778-024-00873-w33:6(1837-1859)Online publication date: 7-Aug-2024
https://doi.org/10.1007/s00778-024-00873-w
Malhotra ADhurandher SGupta M(2021)Data storage and range queries in ubiquitous mobile data cloudJournal of Ambient Intelligence and Humanized Computing10.1007/s12652-021-03576-014:6(7231-7245)Online publication date: 3-Nov-2021
https://doi.org/10.1007/s12652-021-03576-0
Yang KDing XZhang YChen LZheng BGao Y(2019)Distributed Similarity Queries in Metric SpacesData Science and Engineering10.1007/s41019-019-0095-7Online publication date: 28-Jun-2019
https://doi.org/10.1007/s41019-019-0095-7
Show More Cited By

Index Terms

P-ring: an efficient and robust P2P range index structure
1. Information systems
  1. Data management systems
    1. Data structures
      1. Data access methods
    2. Database management system engines
      1. Parallel and distributed DBMSs

Recommendations

Load Balancing and Range Queries in P2P Systems Using P-Ring

In peer-to-peer (P2P) systems, computers from around the globe share data and can participate in distributed computation. P2P became famous, and infamous, due to file-sharing systems like Napster. However, the scalability and robustness of these systems ...
An Efficient Hybrid Peer-to-Peer System for Distributed Data Sharing

Peer-to-peer overlay networks are widely used in distributed systems. Based on whether a regular topology is maintained among peers, peer-to-peer networks can be divided into two categories: structured peer-to-peer networks in which peers are connected ...
Query workload-aware overlay construction using histograms
CIKM '05: Proceedings of the 14th ACM international conference on Information and knowledge management

Peer-to-peer(p2p) systems over an efficient means of data sharing among a dynamically changing set of a large number of a tonomous nodes.Each node in a p2p system is connected with a small number of other nodes thus creating an overlay network of nodes. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '07: Proceedings of the 2007 ACM SIGMOD international conference on Management of data

June 2007

1210 pages

ISBN:9781595936868

DOI:10.1145/1247480

General Chairs:
Lizhu Zhou
Tsinghua University, China
,
Tok Wang Ling
National University of Singapore, Singapore
,
Program Chair:
Beng Chin Ooi
National University of Singapore, Singapore

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SIGMOD/PODS07

Sponsor:

SIGMOD/PODS07: International Conference on Management of Data

June 11 - 14, 2007

Beijing, China

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

50
Total Citations
View Citations
45
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fan ZYe BWang ZZhong ZGuo JWu YLi HYang TTu YLiu ZCui B(2024)Enabling space-time efficient range queries with REncoderThe VLDB Journal10.1007/s00778-024-00873-w33:6(1837-1859)Online publication date: 7-Aug-2024
https://doi.org/10.1007/s00778-024-00873-w
Malhotra ADhurandher SGupta M(2021)Data storage and range queries in ubiquitous mobile data cloudJournal of Ambient Intelligence and Humanized Computing10.1007/s12652-021-03576-014:6(7231-7245)Online publication date: 3-Nov-2021
https://doi.org/10.1007/s12652-021-03576-0
Yang KDing XZhang YChen LZheng BGao Y(2019)Distributed Similarity Queries in Metric SpacesData Science and Engineering10.1007/s41019-019-0095-7Online publication date: 28-Jun-2019
https://doi.org/10.1007/s41019-019-0095-7
Zhu YXu QShi HSamsudin J(2017)An efficient distributed search solution for federated cloudDistributed and Parallel Databases10.1007/s10619-017-7201-535:3-4(411-433)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.1007/s10619-017-7201-5
Kumar SMadria SLinderman M(2017)M-GridDistributed and Parallel Databases10.1007/s10619-017-7194-035:1(55-81)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1007/s10619-017-7194-0
Hidalgo NArantes LSens PBonnaire X(2016)ECHOJournal of Parallel and Distributed Computing10.1016/j.jpdc.2015.10.00788:C(31-45)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1016/j.jpdc.2015.10.007
Rahman MUddin MShahriar NRahman M(2015)Sponge: A searchable P2P mobile app store using DHTs2015 International Conference on Networking Systems and Security (NSysS)10.1109/NSysS.2015.7043531(1-6)Online publication date: Jan-2015
https://doi.org/10.1109/NSysS.2015.7043531
Crainiceanu ALemire D(2015)BloofiInformation Systems10.1016/j.is.2015.01.00254:C(311-324)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1016/j.is.2015.01.002
Ghanem SIsmail MOmar S(2014)VITAL: Structured and clustered super-peer network for similarity searchPeer-to-Peer Networking and Applications10.1007/s12083-014-0304-08:6(965-991)Online publication date: 5-Aug-2014
https://doi.org/10.1007/s12083-014-0304-0
Basu AFleming SStanier JNaicken SWakeman IGurbani V(2013)The state of peer-to-peer network simulatorsACM Computing Surveys10.1145/2501654.250166045:4(1-25)Online publication date: 30-Aug-2013
https://dl.acm.org/doi/10.1145/2501654.2501660
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents