Emerging semantic communities in peer web search

ABSTRACT

Peer network systems are becoming an increasingly important development in Web search technology. Many studies show that peer search systems perform better when a query is sent to a group of peers semantically similar to the query. This suggests that semantic communities should form so that a query can quickly propagate to many appropriate peers. For the network to be functional, its dynamic communication topology must match the semantic clustering of peers. We introduce two criteria to evaluate a peer search network based on the concept of semantic locality: first, the "small-world" topology of the network; second, we use topical semantic similarity to monitor the quality of a peer's neighbors over time by looking at whether a peer chooses semantically appropriate neighbors to route its queries. We present several simulation experiments conducted with different peer search algorithms on our peer Web search system, 6S. The results suggest that 6S, despite its use of an unstructured overlay network; can effectively foster the spontaneous formation of semantic communities through local peer interactions alone.

REFERENCES

• 1: R. Akavipat , L-S. Wu , F. Menczer, Small world peer networks in distributed web search, Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters, May 19-21, 2004, New York, NY, USA [doi>10.1145/1013367.1013493]
• 2: Einat Amitay , David Carmel , Ronny Lempel , Aya Soffer, Scaling IR-system evaluation using term relevance sets, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1008997]
• 3: 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 [doi>10.1145/1041680.1041681]
• 4: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 5: Mayank Bawa , Roberto J. Bayardo, Jr. , Sridhar Rajagopalan , Eugene J. Shekita, Make it fresh, make it quick: searching a network of personal webservers, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775234]
• 6: H. Chu and M. Rosenthal. Search engines for the World Wide Web: A comparative study and evaluation methodology. In Annual Conference Proceedings (ASIS'96), pages 127--135, October 1996.
• 7: A. Clauset and C. Moore. How do networks become navigable? Technical report, arXiv.org:cond-mat/0309415, 2004.
• 8: A. Crespo and H. Garcia-Molina. Semantic overlay networks for P2P systems. Technical report, Computer Science Department, Stanford University, 2002.
• 9: S. Deerwester, S. Dumais, F. GW, T. Landauer, and R. Harshman. Indexing by Latent Semantic Analysis. Journal of the American Society for Information Science, 41:391--407, 1990.
• 10: M. Girvan and M. Newman. Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA, 99:8271--8276, 2002.
• 11: Sam Joseph, NeuroGrid: Semantically Routing Queries in Peer-to-Peer Networks, Revised Papers from the NETWORKING 2002 Workshops on Web Engineering and Peer-to-Peer Computing, p.202-214, May 19-24, 2002
• 12: Vana Kalogeraki , Dimitrios Gunopulos , D. Zeinalipour-Yazti, A local search mechanism for peer-to-peer networks, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584842]
• 13: M. Khambatti, K. Ryu, and P. Dasgupta. Efficient discovery of implicitly formed P2P communities. International Journal of Parallel and Distributed Systems and Networks, 5(4), 2002.
• 14: I. A. Klampanos, V. Poznański, J. M. Jose, and P. Dickman. A suite of testbeds for the realistic evaluation of peer-to-peer information retrieval systems. Lecture Notes in Computer Science, 3408:38--51, 2005.
• 15: D. Leake, A. Maguitman, and T. Reichherzer. Exploiting rich context: An incremental approach to context-based web search. In International and Interdisciplinary Conference on Modeling and Using Context, CONTEXT'05, pages 254--267, Paris, France, July 2005. Springer.
• 16: Dekang Lin, An Information-Theoretic Definition of Similarity, Proceedings of the Fifteenth International Conference on Machine Learning, p.296-304, July 24-27, 1998
• 17: 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 [doi>10.1145/956863.956903]
• 18: J. Lu and J. Callan. Federated search of text digital libraries in hierarchical peer-to-peer networks. In Proc. 27th European Conference on Information Retrieval (ECIR), 2005.
• 19: Ana G. Maguitman , Filippo Menczer , Heather Roinestad , Alessandro Vespignani, Algorithmic detection of semantic similarity, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060765]
• 20: Ana G. Maguitman , Filippo Menczer , Heather Roinestad , Alessandro Vespignani, Algorithmic detection of semantic similarity, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060765]
• 21: Ana G. Maguitman , Filippo Menczer , Heather Roinestad , Alessandro Vespignani, Algorithmic detection of semantic similarity, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060765]
• 22: G. Pant, P. Srinivasan, and F. Menczer. Crawling the Web. In M. Levene and A. Poulovassilis, editors, Web Dynamics. Springer, 2004.
• 23: J. Pujol, R. Sangüesa, and J. Bermúdez. Porqpine: A distributed and collaborative search engine. In Proc. 12th Intl. World Wide Web Conference, 2003.
• 24: F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, and D. Parisi. Defining and identifying communities in networks. Proc. Nat. Acad. Sci. USA, 101(9):2658--2663, 2004.
• 25: P. Resnik. Using information content to evaluate semantic similarity in a taxonomy. In IJCAI, pages 448--453, 1995.
• 26: Tefko Saracevic, Evaluation of evaluation in information retrieval, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.138-146, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215351]
• 27: K. Sripanidkulchai, B. Maggs, and H. Zhang. Efficient content location using interest-based locality in peer-to-peer systems. In Proc. INFOCOM Conference, 2004.
• 28: C. Suel, J.-W. Wu, J. Zhang, A. Delis, M. Kharrazi, X. Long, and K. Shanmugasundaram. ODISSEA: A Peer-to-Peer architecture for scalable Web search and information retrieval. In International Workshop on the Web and Databases (WebDB), 2003.
• 29: Chunqiang Tang , Zhichen Xu , Sandhya Dwarkadas, Peer-to-peer information retrieval using self-organizing semantic overlay networks, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863976]
• 30: Dimitrios Tsoumakos , Nick Roussopoulos, Adaptive Probabilistic Search for Peer-to-Peer Networks, Proceedings of the 3rd International Conference on Peer-to-Peer Computing, p.102, September 01-03, 2003
• 31: Exploiting Semantic Proximity in Peer-to-Peer Content Searching, Proceedings of the 10th IEEE International Workshop on Future Trends of Distributed Computing Systems (FTDCS'04), p.238-243, May 26-28, 2004
• 32: S. Waterhouse. JXTA Search: Distributed search for distributed networks. Technical report, Sun Microsystems Inc., 2001.
• 33: D. Watts and S. Strogatz. Collective dynamics of "small-world" networks. Nature, 393:440--442, 1998.
• 34: L. Wishard. Precision among Internet search engines: An earth sciences case study. Issues in Science and Technology Librarianship, Spring 1998.
• 35: L.-S. Wu, R. Akavipat, and F. Menczer. 6S: Distributing crawling and searching across Web peers. In Proceedings of the IASTED International Conference on Web technologies, Applications, and Services, Calgary, Canada, July 2005.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software

General Terms:
Algorithms, Experimentation, Performance

Keywords:
coverage, global coherence, peer search, semantic locality, small-world networks, topical semantic similarity