Speeding up search in peer-to-peer networks with a multi-way tree structure

ABSTRACT

Peer-to-Peer systems have recently become a popular means to share resources. Effective search is a critical requirement in such systems, and a number of distributed search structures have been proposed in the literature. Most of these structures provide "log time search" capability, where the logarithm is taken base 2. That is, in a system with N nodes, the cost of the search is O(log₂N).In database systems, the importance of large fanout index structures has been well recognized. In P2P search too, the cost could be reduced considerably if this logarithm were taken to a larger base. In this paper, we propose a multi-way tree search structure, which reduces the cost of search to O(log_mN), where m is the fanout. The penalty paid is a larger update cost, but we show how to keep this penalty to be no worse than linear in m. We experimentally explore this tradeoff between search and update cost as a function of m, and suggest how to find a good trade-off point.The multi-way tree structure we propose, BATON*, is derived from the BATON structure that has recently been suggested. In addition to multi-way fanout, BATON* also adds support for multi-attribute queries to BATON.

REFERENCES

• 1: Karl Aberer, P-Grid: A Self-Organizing Access Structure for P2P Information Systems, Proceedings of the 9th International Conference on Cooperative Information Systems, p.179-194, September 05-07, 2001
• 2: [2] F. S. Action. Numerical Methods that Work. Harpercollins College Div, 1970.
• 3: Artur Andrzejak , Zhichen Xu, Scalable, Efficient Range Queries for Grid Information Services, Proceedings of the Second International Conference on Peer-to-Peer Computing, p.33, September 05-07, 2002
• 4: James Aspnes , Gauri Shah, Skip graphs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 5: Ashwin R. Bharambe , Mukesh Agrawal , Srinivasan Seshan, Mercury: supporting scalable multi-attribute range queries, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 6: [6] M. Cai, M. Frank, J. Chen, and P. Szekely. Maan: A multi-attribute addressable network for grid information services. In Proceedings of the 2003 IPTPS, 2003.
• 7: Brent Chun , David Culler , Timothy Roscoe , Andy Bavier , Larry Peterson , Mike Wawrzoniak , Mic Bowman, PlanetLab: an overlay testbed for broad-coverage services, ACM SIGCOMM Computer Communication Review, v.33 n.3, July 2003 [doi>10.1145/956993.956995]
• 8: Adina Crainiceanu , Prakash Linga , Johannes Gehrke , Jayavel Shanmugasundaram, Querying peer-to-peer networks using P-trees, Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004, June 17-18, 2004, Paris, France [doi>10.1145/1017074.1017082]
• 9: [9] A. Gupta, D. Agrawal, and A. El Abbadi. Approximate range selection queries in peer-to-peer systems. In Proceedings of the 1st Biennial Conference on Innovative Data Systems Research, 2003.
• 10: Nicholas J. A. Harvey , Michael B. Jones , Stefan Saroiu , Marvin Theimer , Alec Wolman, SkipNet: a scalable overlay network with practical locality properties, Proceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems, p.9-9, March 26-28, 2003, Seattle, WA
• 11: H. V. Jagadish , Beng Chin Ooi , Quang Hieu Vu, BATON: a balanced tree structure for peer-to-peer networks, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 12: H. V. Jagadish , Beng Chin Ooi , Quang Hieu Vu , Rong Zhang , Aoying Zhou, VBI-Tree: A Peer-to-Peer Framework for Supporting Multi-Dimensional Indexing Schemes, Proceedings of the 22nd International Conference on Data Engineering (ICDE'06), p.34, April 03-07, 2006 [doi>10.1109/ICDE.2006.169]
• 13: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 14: Xin Li , Young Jin Kim , Ramesh Govindan , Wei Hong, Multi-dimensional range queries in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958500]
• 15: [15] C. Y. Liau, W. S. Ng, Y. Shu, K.-L. Tan, and S. Bressan. Efficient range queries and fast lookup services for scalable p2p networks. In Proceedings of the 2nd DBISP2P, pages 78-92, 2004.
• 16: Witold Litwin , Marie-Anna Neimat , Donovan A. Schneider, LH*—a scalable, distributed data structure, ACM Transactions on Database Systems (TODS), v.21 n.4, p.480-525, Dec. 1996 [doi>10.1145/236711.236713]
• 17: BestPeer: A Self-Configurable Peer-to-Peer System, Proceedings of the 18th International Conference on Data Engineering, p.272, February 26-March 01, 2002
• 18: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 19: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 20: O. D. Sahin , A. Gupta , D. Agrawal , A. El Abbadi, A Peer-to-peer Framework for Caching Range Queries, Proceedings of the 20th International Conference on Data Engineering, p.165, March 30-April 02, 2004
• 21: Cristina Schmidt , Manish Parashar, Flexible Information Discovery in Decentralized Distributed Systems, Proceedings of the 12th IEEE International Symposium on High Performance Distributed Computing, p.226, June 22-24, 2003
• 22: [22] B. Y. Zhao, J. D. Kubiatowicz, and A. D. Joseph. Tapestry: An infrastructure for fault-tolerant wide-area location and routing. Technical Report CSD-01-1141, Univ. California, Berkeley, CA, Apr. 2001.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Design

Keywords:
multi-way tree structure, peer-to-peer, system architecture