A local search mechanism for peer-to-peer networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A local search mechanism for peer-to-peer networks

Full text

Pdf (239 KB)

Source

Conference on Information and Knowledge Management archive
Proceedings of the eleventh international conference on Information and knowledge management table of contents

McLean, Virginia, USA

SESSION: XML schemas: integration and translation table of contents

Pages: 300 - 307

Year of Publication: 2002

ISBN:1-58113-492-4

Authors

Vana Kalogeraki	Hewlett-Packard Labs, Palo Alto, CA
Dimitrios Gunopulos	Univ. of California, Riverside
D. Zeinalipour-Yazti	Univ. of California, Riverside

Sponsors

SIGMIS: ACM Special Interest Group on Management Information Systems
ACM: Association for Computing Machinery
SIGIR: ACM Special Interest Group on Information Retrieval

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 124, Citation Count: 40

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/584792.584842 What is a DOI?

ABSTRACT

One important problem in peer-to-peer (P2P) networks is searching and retrieving the correct information. However, existing searching mechanisms in pure peer-to-peer networks are inefficient due to the decentralized nature of such networks. We propose two mechanisms for information retrieval in pure peer-to-peer networks. The first, the modified Breadth-First Search (BFS) mechanism, is an extension of the current Gnuttela protocol, allows searching with keywords, and is designed to minimize the number of messages that are needed to search the network. The second, the Intelligent Search mechanism, uses the past behavior of the P2P network to further improve the scalability of the search procedure. In this algorithm, each peer autonomously decides which of its peers are most likely to answer a given query. The algorithm is entirely distributed, and therefore scales well with the size of the network. We implemented our mechanisms as middleware platforms. To show the advantages of our mechanisms we present experimental results using the middleware implementation.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	L. A. Adamic, R. M. Lukose, A. R. Puniyani and B. A. Huberman. Search in power-law networks. Phys. Rev. E, 64 46135 (2001).
	2	J. Breese, D. Heckerman, and C. Kadie. Empirical Analysis of Predictive Algorithms for Collaborative Filtering. Proc. of the Fourteenth Annual Conference on Uncertainty in Artificial Intelligence (UAI-98). San Francisco, CA, pp. 43--52
	3	J. Callan, A.L. Powell, J.C. French, and M. Connell. The effects of query-based sampling on automatic database selection algorithms. Technical Report IR-181, Center for Intelligent Information Retrieval, Department of Computer Science, University of Massachusetts.
	4	Soumen Chakrabarti , Sandeep Srivastava , Mallela Subramanyam , Mitul Tiwari, Using Memex to archive and mine community Web browsing experience, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.669-684, June 2000
	5	Clip2. www.clip2.net
	6	Arturo Crespo , Hector Garcia-Molina, Routing Indices For Peer-to-Peer Systems, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.23, July 02-05, 2002
	7	Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
	8	Freenet, http://freenet.sourceforge.net
	9	James C. French , Allison L. Powell , Jamie Callan , Charles L. Viles , Travis Emmitt , Kevin J. Prey , Yun Mou, Comparing the performance of database selection algorithms, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.238-245, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312684]
	10	Gnutella, http://gnutella.wego.com.
	11	Luis Gravano , Hector Garcia-Molina, Generalizing GlOSS to Vector-Space Databases and Broker Hierarchies, Proceedings of the 21th International Conference on Very Large Data Bases, p.78-89, September 11-15, 1995
	12	Kazaa, http://www.kazaa.com
	13	H. Lieberman, N. Van Dyke, and A. Vivacqua. Let's Browse: A Collaborative Web Browsing Agent. MIT Media Lab Tech Report.
	14	Z. Lu and K. S. McKinley. The Effect of Collection Organization and Query Locality on Information Retrieval System Performance and Design. Book chapter in Advances in Information Retrieval, Kluwer, New York, 2000. Bruce Croft, Editor.
	15	Sergey Melnik , Sriram Raghavan , Beverly Yang , Hector Garcia-Molina, Building a distributed full-text index for the Web, Proceedings of the 10th international conference on World Wide Web, p.396-406, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372095]
	16	Napster, http://www.napster.com.
	17	Allison L. Powell , James C. French , Jamie Callan , Margaret Connell , Charles L. Viles, The impact of database selection on distributed searching, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.232-239, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345584]
	18	REUTERS-21578 dataset. http://www.research.att.com/~lewis
	19	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
	20	Beverly Yang , Hector Garcia-Molina, Comparing Hybrid Peer-to-Peer Systems, Proceedings of the 27th International Conference on Very Large Data Bases, p.561-570, September 11-14, 2001
	21	Beverly Yang , Hector Garcia-Molina, Improving Search in Peer-to-Peer Networks, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.5, July 02-05, 2002
	22	Zonghuan Wu , Weiyi Meng , Clement Yu , Zhuogang Li, Towards a highly-scalable and effective metasearch engine, Proceedings of the 10th international conference on World Wide Web, p.386-395, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372093]
	23	Jinxi Xu , Jamie Callan, Effective retrieval with distributed collections, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.112-120, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290974]
	24	H. Zhang, A. Goel, R. Govindan. Using the Small-World Model to Improve Freenet Performance. Proc. of IEEE Infocom, 2002.

CITED BY 40

	D. Zeinalipour-Yazti , Vana Kalogeraki , Dimitrios Gunopulos, Exploiting locality for scalable information retrieval in peer-to-peer networks, Information Systems, v.30 n.4, p.277-298, June 2005
	Jie Lu , Jamie Callan, Content-based retrieval in hybrid peer-to-peer networks, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA
	Hans Friedrich Witschel , Thomas Böhme, Evaluating profiling and query expansion methods for P2P information retrieval, Proceedings of the 2005 ACM workshop on Information retrieval in peer-to-peer networks, November 04-04, 2005, Bremen, Germany
	M. Elena Renda , Jamie Callan, The robustness of content-based search in hierarchical peer to peer networks, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
	Brian F. Cooper, Guiding queries to information sources with InfoBeacons, Proceedings of the 5th ACM/IFIP/USENIX international conference on Middleware, October 18-22, 2004, Toronto, Canada
	Demetrios Zeinalipour-Yazti , Vana Kalogeraki , Dimitrios Gunopulos, Information Retrieval Techniques for Peer-to-Peer Networks, Computing in Science and Engineering, v.6 n.4, p.20-26, July 2004
	Brian F. Cooper, A content model for evaluating peer-to-peer searching techniques, Proceedings of the 5th ACM/IFIP/USENIX international conference on Middleware, October 18-22, 2004, Toronto, Canada
	Brian F. Cooper , Hector Garcia-Molina, Ad Hoc, self-supervising peer-to-peer search networks, ACM Transactions on Information Systems (TOIS), v.23 n.2, p.169-200, April 2005
	Stephanos Androutsellis-Theotokis , Diomidis Spinellis, A survey of peer-to-peer content distribution technologies, ACM Computing Surveys (CSUR), v.36 n.4, p.335-371, December 2004
	An-Hsun Cheng , Yuh-Jzer Joung, Probabilistic file indexing and searching in unstructured peer-to-peer networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.1, p.106-127, 16 January 2006
	Hailong Cai , Jun Wang, Foreseer: a novel, locality-aware peer-to-peer system architecture for keyword searches, Proceedings of the 5th ACM/IFIP/USENIX international conference on Middleware, October 18-22, 2004, Toronto, Canada
	Dimitrios Tsoumakos , Nick Roussopoulos, Analysis and comparison of P2P search methods, Proceedings of the 1st international conference on Scalable information systems, p.25-es, May 30-June 01, 2006, Hong Kong
	Kin Wah Kwong , Danny H. Tsang, A congestion-aware search protocol for heterogeneous peer-to-peer networks, The Journal of Supercomputing, v.36 n.3, p.265-282, June 2006
	Brian F. Cooper , Hector Garcia-Molina, SIL: a model for analyzing scalable peer-to-peer search networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.13, p.2380-2400, 15 September 2006
	R. Akavipat , L.-S. Wu , F. Menczer , A.G. Maguitman, Emerging semantic communities in peer web search, Proceedings of the international workshop on Information retrieval in peer-to-peer networks, November 11-11, 2006, Arlington, Virginia, USA
	Demetrios Zeinalipour-Yazti , Vana Kalogeraki, Structuring topologically aware overlay networks using domain names, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.16, p.3064-3082, 14 November 2006
	Nabhendra Bisnik , Alhussein A. Abouzeid, Optimizing random walk search algorithms in P2P networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.51 n.6, p.1499-1514, April, 2007
	John Risson , Tim Moors, Survey of research towards robust peer-to-peer networks: search methods, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.17, p.3485-3521, 5 December 2006
	V. Kalogeraki , D. Zeinalipour-Yazti , D. Gunopulos , A. Delis, Distributed middleware architectures for scalable media services, Journal of Network and Computer Applications, v.30 n.1, p.209-243, January 2007
	Xiuqi Li , Jie Wu, A hybrid searching scheme in unstructured P2P networks, International Journal of Parallel, Emergent and Distributed Systems, v.22 n.1, p.15-38, January 2007
	James Z. Wang , Matti Vanninen, Self-configuration protocols for P2P networks, Web Intelligence and Agent System, v.4 n.1, p.61-76, January 2006
	Luca Gatani , Giuseppe Lo Re, An efficient adaptive strategy for searching in peer-to-peer networks, Multiagent and Grid Systems, v.1 n.3, p.209-224, August 2005
	Haizheng Zhang , W. Bruce Croft , Brian Levine , Victor Lesser, A Multi-Agent Approach for Peer-to-Peer Based Information Retrieval System, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.456-463, July 19-23, 2004, New York, New York
	Hans F. Witschel, Ranking information resources in peer-to-peer text retrieval: an experimental study, Proceeding of the 2008 ACM workshop on Large-Scale distributed systems for information retrieval, October 30-30, 2008, Napa Valley, California, USA
	Selim Ciraci , İbrahim Körpeoglu , Özgür Ulusoy, Reducing query overhead through route learning in unstructured peer-to-peer network, Journal of Network and Computer Applications, v.32 n.3, p.550-567, May, 2009
	Yi-Chang Lin , Long-Sheng Li, NEMO based P2P file discovery scheme, Proceedings of the 4th international conference on mobile technology, applications, and systems and the 1st international symposium on Computer human interaction in mobile technology, September 10-12, 2007, Singapore
	Yi-Chang Lin , Long-Sheng Li , Chia-Chu Haung, A P2P file discovery scheme in NEMO, Proceedings of the 2007 international conference on Wireless communications and mobile computing, August 12-16, 2007, Honolulu, Hawaii, USA
	Jianming Lv , Xueqi Cheng, CTO: concept tree based semantic overlay for pure peer-to-peer information retrieval, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal
	Vladimir Vishnevsky , Alexander Safonov , Mikhail Yakimov , Eunsoo Shim , Alexander D. Gelman, Scalable blind search and broadcasting over Distributed Hash Tables, Computer Communications, v.31 n.2, p.292-303, February, 2008
	Ioannis Karydis , Alexandros Nanopoulos , Apostolos N. Papadopoulos , Yannis Manolopoulos, Evaluation of similarity searching methods for music data in P2P networks, International Journal of Business Intelligence and Data Mining, v.1 n.2, p.210-228, December 2005
	Vassilios V. Dimakopoulos , Evaggelia Pitoura, On the Performance of Flooding-Based Resource Discovery, IEEE Transactions on Parallel and Distributed Systems, v.17 n.11, p.1242-1252, November 2006
	Igor Mekterovic , Mirta Baranovic , Kresimir Krizanovic, A protocol for self-organizing peer-to-peer network supporting content-based search, WSEAS Transactions on Information Science and Applications, v.5 n.5, p.674-684, May 2008
	Elena Meshkova , Janne Riihijärvi , Marina Petrova , Petri Mähönen, A survey on resource discovery mechanisms, peer-to-peer and service discovery frameworks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.52 n.11, p.2097-2128, August, 2008
	Sangeetha Seshadri , Brian F. Cooper, Routing Queries through a Peer-to-Peer InfoBeacons Network Using Information Retrieval Techniques, IEEE Transactions on Parallel and Distributed Systems, v.18 n.12, p.1754-1765, December 2007
	Demetrios Zeinalipour-Yazti , Vana Kalogeraki , Dimitrios Gunopulos, pFusion: A P2P Architecture for Internet-Scale Content-Based Search and Retrieval, IEEE Transactions on Parallel and Distributed Systems, v.18 n.6, p.804-817, June 2007
	Hailong Cai , Jun Wang, Exploiting Geographical and Temporal Locality to Boost Search Efficiency in Peer-to-Peer Systems, IEEE Transactions on Parallel and Distributed Systems, v.17 n.10, p.1189-1203, October 2006
	Brian F. Cooper, Trading off resources between overlapping overlays, Proceedings of the ACM/IFIP/USENIX 2006 International Conference on Middleware, November 01-01, 2006, Melbourne, Australia
	Brian F. Cooper, An optimal overlay topology for routing peer-to-peer searches, Proceedings of the ACM/IFIP/USENIX 2005 International Conference on Middleware, p.82-101, November 01-01, 2005, Grenoble, France
	Stephen J. H. Yang , Jia Zhang , Leon Lin , Jeffrey J. P. Tsai, Improving peer-to-peer search performance through intelligent social search, Expert Systems with Applications: An International Journal, v.36 n.7, p.10312-10324, September, 2009
	Sumeth Lerthirunwong , Naoya Maruyama , Satoshi Matsuoka, Adaptive Resource Indexing Technique for Unstructured Peer-to-Peer Networks, Proceedings of the 2009 9th IEEE/ACM International Symposium on Cluster Computing and the Grid, p.172-179, May 18-21, 2009