Proceedings

Web Page Clustering Using Heuristic Search in the Web Graph

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 2280-2284.

© 2007 International Joint Conferences on Artificial Intelligence

Abstract

Effective representation of Web search results remains an open problem in the Information Retrieval community. For ambiguous queries, a traditional approach is to organize search results into groups (clusters), one for each meaning of the query. These groups are usually constructed according to the topical similarity of the retrieved documents, but it is possible for documents to be totally dissimilar and still correspond to the same meaning of the query. To overcome this problem, we exploit the thematic locality of the Web---relevant Web pages are often located close to each other in the Web graph of hyperlinks. We estimate the level of relevance between each pair of retrieved pages by the length of a path between them. The path is constructed using multi-agent beam search: each agent starts with one Web page and attempts to meet as many other agents as possible with some bounded resources. We test the system on two types of queries: ambiguous English words and people names. The Web appears to be tightly connected; about 70\% of the agents meet with each other after only three iterations of exhaustive breadth-first search. However, when heuristics are applied, the search becomes more focused and the obtained results are substantially more accurate. Combined with a content-driven Web page clustering technique, our heuristic search system significantly improves the clustering results.

  1. [Bekkerman and McCallum, 2005] R. Bekkerman and A. McCal- lum. Disambiguating Web appearances of people in a social net- work. In Proceedings of WWW, pages 463-470, 2005.
  2. [Davidov and Markovitch, 2002] D. Davidov and S. Markovitch. Multiple-goal search algorithms and their application to Web crawling. In Proceedings of AAAI, pages 713-718, 2002.
  3. [Davison, 2000] B. D. Davison. Topical locality in the Web. In Proceedings of SIGIR, pages 272-279, 2000.
  4. [Dean and Ghemawat, 2004] J. Dean and S. Ghemawat. Mapre- duce: simplified data processing on large clusters. In Proceedings of Operating System Design and Implementation, 2004.
  5. [Dean and Henzinger, 1999] J. Dean and M. R. Henzinger. Find- ing related pages in the World Wide Web. Computer Networks, 31:1467-1479, 1999.
  6. [Eiron and McCurley, 2003] N. Eiron and K. McCurley. Analysis of anchor text for Web search. In Proceedings of SIGIR, pages 459-460, 2003.
  7. [Gibson et al., 1998] D. Gibson, J. Kleinberg, and P. Raghavan. In- ferring Web communities from link topology. In Proceedings of the 9th ACM conference on Hypertext and Hypermedia, 1998.
  8. [He et al., 2002] X. He, H. Zha, C. H. Q. Ding, and H. D. Simon. Web document clustering using hyperlink structures. Computa- tional Statistics & Data Analysis, 41:19-45, 2002.
  9. [Hearst and Pedersen, 1996] M. A. Hearst and J. O. Pedersen. Re- examining the cluster hypothesis: Scatter/gather on retrieval re- sults. In Proceedings of SIGIR, pages 76-84, 1996.
  10. [Kleinberg et al., 1999] J. M. Kleinberg, R. Kumar, P. Raghavan, S. Rajagopalan, and A. S. Tomkins. The Web as a graph: Mea- surements, models and methods. LNCS, 1627, 1999.
  11. [Leuski and Allan, 2004] A. Leuski and J. Allan. Interactive in- formation retrieval using clustering and spatial proximity. User Modeling and User-Adapted Interaction, 14:259-288, 2004.
  12. [McCallum and Li, 2003] A. McCallum and W. Li. Early results for named entity recognition with conditional random fields, feature induction and Web-enhanced lexicons. In Proc. of CoNLL, 2003.
  13. [Pakhomov et al., 2005] S. Pakhomov, T. Pedersen, and C. Chute. Abbreviation and acronym disambiguation in clinical discourse. In Proceedings of the Annual Symposium of the American Med- ical Informatics Association, 2005.
  14. [Pearl, 1984] J. Pearl. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 1984.
  15. [van Rijsbergen, 1971] C. J. van Rijsbergen. An algorithm for in- formation structuring and retrieval. Computer Journal, 14:407- 412, 1971.
  16. [Zamir and Etzioni, 1998] O. Zamir and O. Etzioni. Web document clustering: a feasibility demonstration. In Proc. of SIGIR, 1998.
  17. [Zeng et al., 2004] H.U. Zeng, Q.C. He, Z. Chen, W.Y. Ma, and J. Ma. Learning to cluster Web search results. In Proceedings of SIGIR, 2004.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards