{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,26]],"date-time":"2025-09-26T00:16:34Z","timestamp":1758845794197,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2011,3,1]],"date-time":"2011-03-01T00:00:00Z","timestamp":1298937600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N0001408WR40063","N0001406WR20137"],"award-info":[{"award-number":["N0001408WR40063","N0001406WR20137"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004863","name":"New York State Foundation for Science, Technology and Innovation","doi-asserted-by":"publisher","award":["C050061"],"award-info":[{"award-number":["C050061"]}],"id":[{"id":"10.13039\/100004863","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["F49620-02-1-0233FA9550-10-1-0202"],"award-info":[{"award-number":["F49620-02-1-0233FA9550-10-1-0202"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["133481"],"award-info":[{"award-number":["133481"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Internet Technol."],"published-print":{"date-parts":[[2011,3]]},"abstract":"<jats:p>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 make them appealing to a wide range of applications.<\/jats:p>\n          <jats:p>This article introduces P-Ring, a new peer-to-peer index structure. P-Ring is fully distributed, fault tolerant, and provides load balancing and logarithmic search performance while supporting both equality and range queries. Our theoretical analysis as well as experimental results, obtained both in a simulated environment and on PlanetLab, show the performance of our system.<\/jats:p>","DOI":"10.1145\/1944339.1944343","type":"journal-article","created":{"date-parts":[[2011,4,1]],"date-time":"2011-04-01T15:54:25Z","timestamp":1301673265000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Load Balancing and Range Queries in P2P Systems Using P-Ring"],"prefix":"10.1145","volume":"10","author":[{"given":"Adina","family":"Crainiceanu","sequence":"first","affiliation":[{"name":"United States Naval Academy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prakash","family":"Linga","sequence":"additional","affiliation":[{"name":"Moka5"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ashwin","family":"Machanavajjhala","sequence":"additional","affiliation":[{"name":"Yahoo! Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johannes","family":"Gehrke","sequence":"additional","affiliation":[{"name":"Cornell University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jayavel","family":"Shanmugasundaram","sequence":"additional","affiliation":[{"name":"Google Inc."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/646747.701489"},{"volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Aspnes J.","key":"e_1_2_1_2_1","unstructured":"Aspnes , J. and Shah , G . 2003. Skip graphs . In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Aspnes, J. and Shah, G. 2003. Skip graphs. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1030194.1015507"},{"volume-title":"Proceedings of the 4th International Workshop on Grid Computing.","author":"Cai M.","key":"e_1_2_1_4_1","unstructured":"Cai , M. , Frank , M. , Chen , J. , and Szekely , P . 2003. Maan: A multi-attribute addressable network for grid information services . In Proceedings of the 4th International Workshop on Grid Computing. Cai, M., Frank, M., Chen, J., and Szekely, P. 2003. Maan: A multi-attribute addressable network for grid information services. In Proceedings of the 4th International Workshop on Grid Computing."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1017074.1017082"},{"volume-title":"Proceedings of the World Wide Web Conference (WWW) (poster).","author":"Crainiceanu A.","key":"e_1_2_1_6_1","unstructured":"Crainiceanu , A. , Linga , P. , Machanavajjhala , A. , Gehrke , J. , and Shanmugasundaram , J . 2004b. An indexing framework for peer-to-peer systems . In Proceedings of the World Wide Web Conference (WWW) (poster). Crainiceanu, A., Linga, P., Machanavajjhala, A., Gehrke, J., and Shanmugasundaram, J. 2004b. An indexing framework for peer-to-peer systems. In Proceedings of the World Wide Web Conference (WWW) (poster)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247507"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/502034.502054"},{"volume-title":"Proceedings of the International Workshop on Databases, Information Systems and Peer-to-Peer Computing (DBISP2P).","author":"Daskos A.","key":"e_1_2_1_9_1","unstructured":"Daskos , A. , Ghandeharizadeh , S. , and An , X . 2003. Peper: A distributed range addressing space for p2p systems . In Proceedings of the International Workshop on Databases, Information Systems and Peer-to-Peer Computing (DBISP2P). Daskos, A., Ghandeharizadeh, S., and An, X. 2003. Peper: A distributed range addressing space for p2p systems. In Proceedings of the International Workshop on Databases, Information Systems and Peer-to-Peer Computing (DBISP2P)."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/P2P.2005.31"},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB).","author":"Ganesan P.","key":"e_1_2_1_11_1","unstructured":"Ganesan , P. , Bawa , M. , and Garcia-Molina , H . 2004. Online balancing of range-partitioned data with applications to peer-to-peer systems . In Proceedings of the International Conference on Very Large Databases (VLDB). Ganesan, P., Bawa, M., and Garcia-Molina, H. 2004. Online balancing of range-partitioned data with applications to peer-to-peer systems. In Proceedings of the International Conference on Very Large Databases (VLDB)."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the Conference on Innovative Data Systems Research (CIDR).","author":"Gupta A.","year":"2003","unstructured":"Gupta , A. , Agrawal , D. , and El Abbadi , A. 2003 . Approximate range selection queries in peer-to-peer systems . In Proceedings of the Conference on Innovative Data Systems Research (CIDR). Gupta, A., Agrawal, D., and El Abbadi, A. 2003. Approximate range selection queries in peer-to-peer systems. In Proceedings of the Conference on Innovative Data Systems Research (CIDR)."},{"volume-title":"Proceedings of the USENIX Symposium on Internet Technologies and Systems (USITS).","author":"Harvey N.","key":"e_1_2_1_13_1","unstructured":"Harvey , N. , Jones , M. , Saroiu , S. , Theimer , M. , and Wolman , A . 2003. Skipnet: A scalable overlay network with practical locality properties . In Proceedings of the USENIX Symposium on Internet Technologies and Systems (USITS). Harvey, N., Jones, M., Saroiu, S., Theimer, M., and Wolman, A. 2003. Skipnet: A scalable overlay network with practical locality properties. In Proceedings of the USENIX Symposium on Internet Technologies and Systems (USITS)."},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB).","author":"Jagadish H.","key":"e_1_2_1_14_1","unstructured":"Jagadish , H. , Ooi , B. C. , and Vu , Q. H . 2005. Baton: A balanced tree structure for peer-to-peer networks . In Proceedings of the International Conference on Very Large Databases (VLDB). Jagadish, H., Ooi, B. C., and Vu, Q. H. 2005. Baton: A balanced tree structure for peer-to-peer networks. In Proceedings of the International Conference on Very Large Databases (VLDB)."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142475"},{"key":"e_1_2_1_16_1","unstructured":"JBI. 2011. http:\/\/www.rl.af.mil\/programs\/jbi\/. JBI . 2011. http:\/\/www.rl.af.mil\/programs\/jbi\/."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/379437.379449"},{"volume-title":"Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom).","author":"Li J.","key":"e_1_2_1_18_1","unstructured":"Li , J. , Stribling , J. , Morris , R. , Kaashoek , M. F. , and Gil , T. M . 2005. A performance vs. cost framework for evaluating dht design tradeoffs under churn . In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom). Li, J., Stribling, J., Morris, R., Kaashoek, M. F., and Gil, T. M. 2005. A performance vs. cost framework for evaluating dht design tradeoffs under churn. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom)."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066195"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170084"},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB).","author":"Litwin W.","key":"e_1_2_1_21_1","unstructured":"Litwin , W. , Neimat , M.-A. , and Schneider , D. A . 1994. Rp*: A family of order preserving scalable distributed data structures . In Proceedings of the International Conference on Very Large Databases (VLDB). Litwin, W., Neimat, M.-A., and Schneider, D. A. 1994. Rp*: A family of order preserving scalable distributed data structures. In Proceedings of the International Conference on Very Large Databases (VLDB)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/382006.383201"},{"key":"e_1_2_1_23_1","unstructured":"Planet Lab. 2011. Planet Lab homepage. www.planet-lab.org. Planet Lab . 2011. Planet Lab homepage. www.planet-lab.org."},{"key":"e_1_2_1_24_1","unstructured":"Ramakrishnan R. and Gehrke J. 2003. Database Management Systems. McGraw Hill. Ramakrishnan R. and Gehrke J. 2003. Database Management Systems . McGraw Hill."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/383059.383072"},{"volume-title":"Proceedings of the USENIX Annual Tech Conference.","author":"Rhea S.","key":"e_1_2_1_26_1","unstructured":"Rhea , S. , Geels , D. , Roscoe , T. , and Kubiatowicz , J . 2004. Handling churn in a dht . In Proceedings of the USENIX Annual Tech Conference. Rhea, S., Geels, D., Roscoe, T., and Kubiatowicz, J. 2004. Handling churn in a dht. In Proceedings of the USENIX Annual Tech Conference."},{"volume-title":"Proceedings of the International ACM\/IFIP\/USENIX Middleware Conference (Middleware).","author":"Rowstron A.","key":"e_1_2_1_27_1","unstructured":"Rowstron , A. and Druschel , P . 2001. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems . In Proceedings of the International ACM\/IFIP\/USENIX Middleware Conference (Middleware). Rowstron, A. and Druschel, P. 2001. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In Proceedings of the International ACM\/IFIP\/USENIX Middleware Conference (Middleware)."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/977401.978125"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/383059.383071"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/894116"}],"container-title":["ACM Transactions on Internet Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1944339.1944343","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1944339.1944343","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:59:30Z","timestamp":1750244370000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1944339.1944343"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,3]]}},"alternative-id":["10.1145\/1944339.1944343"],"URL":"https:\/\/doi.org\/10.1145\/1944339.1944343","relation":{},"ISSN":["1533-5399","1557-6051"],"issn-type":[{"type":"print","value":"1533-5399"},{"type":"electronic","value":"1557-6051"}],"subject":[],"published":{"date-parts":[[2011,3]]},"assertion":[{"value":"2010-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}