Enhanced topic distillation using text, markup tags, and hyperlinks

ABSTRACT

Topic distillation is the analysis of hyperlink graph structure to identify mutually reinforcing authorities (popular pages) and hubs (comprehensive lists of links to authorities). Topic distillation is becoming common in Web search engines, but the best-known algorithms model the Web graph at a coarse grain, with whole pages as single nodes. Such models may lose vital details in the markup tag structure of the pages, and thus lead to a tightly linked irrelevant subgraph winning over a relatively sparse relevant subgraph, a phenomenon called topic drift or contamination. The problem gets especially severe in the face of increasingly complex pages with navigation panels and advertisement links. We present an enhanced topic distillation algorithm which analyzes text, the markup tag trees that constitute HTML pages, and hyperlinks between pages. It thereby identifies subtrees which have high text- and hyperlink-based coherence w.r.t. the query. These subtrees get preferential treatment in the mutual reinforcement process. Using over 50 queries, 28 from earlier topic distillation work, we analyzed over 700,000 pages and obtained quantitative and anecdotal evidence that the new algorithm reduces topic drift.

REFERENCES

• 1: Doug Beeferman , Adam Berger , John Lafferty, Statistical Models for Text Segmentation, Machine Learning, v.34 n.1-3, p.177-210, Feb. 1999 [doi>10.1023/A:1007506220214]
• 2: Krishna Bharat , Monika R. Henzinger, Improved algorithms for topic distillation in a hyperlinked environment, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.104-111, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290972]
• 3: Allan Borodin , Gareth O. Roberts , Jeffrey S. Rosenthal , Panayiotis Tsaparas, Finding authorities and hubs from link structures on the World Wide Web, Proceedings of the 10th international conference on World Wide Web, p.415-429, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372096]
• 4: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 5: C. Buckley, M. Mitra, J. Waltz, and C. Cardie. Using clustering and SuperConcepts within SMART: TREC6. In Proceedings of the Sixth Text Retrieval Conference (TREC6), Gaithersburg, MD, 1998. National Institute of Standards and Technology (NIST). Online at http://www.cs.cornell.edu/home/ cardie/papers/trec6-ipm.ps.
• 6: Soumen Chakrabarti, Integrating the document object model with hyperlinks for enhanced topic distillation and information extraction, Proceedings of the 10th international conference on World Wide Web, p.211-220, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372054]
• 7: Soumen Chakrabarti , Byron E. Dom , S. Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins , David Gibson , Jon Kleinberg, Mining the Web's Link Structure, Computer, v.32 n.8, p.60-67, August 1999 [doi>10.1109/2.781636]
• 8: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 9: David Gibson , Jon M. Kleinberg , Prabhakar Raghavan, Clustering Categorical Data: An Approach Based on Dynamical Systems, Proceedings of the 24rd International Conference on Very Large Data Bases, p.311-322, August 24-27, 1998
• 10: G. H. Golub and C. F. van Loan. Matrix Computations. Johns Hopkins University Press, London, 1989.
• 11: Marti A. Hearst, Multi-paragraph segmentation of expository text, Proceedings of the 32nd annual meeting on Association for Computational Linguistics, p.9-16, June 27-30, 1994, Las Cruces, New Mexico [doi>10.3115/981732.981734]
• 12: D. S. Johnson and K. A. Niemi. On knapsacks, partitions, and a new dynamic programming technique for trees. Mathematics of Operations Research, 8(1):1-14, 1983.
• 13: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 14: A. McCallum. Bow: A toolkit for statistical language modeling, text retrieval, classification and clustering. Software available from http://www.cs.cmu.edu/~mccallum/bow/, 1998.
• 15: Jay M. Ponte , W. Bruce Croft, Text Segmentation by Topic, Proceedings of the First European Conference on Research and Advanced Technology for Digital Libraries, p.113-125, September 01-03, 1997
• 16: Jeffrey C. Reynar , Mitchell P. Marcus, Topic segmentation: algorithms and applications, 1998
• 17: K. Richmond, A. Smith, and E. Amitay. Detecting subject boundaries within text: A language independent statistical approach. In Empirical Methods in Natural Language Processing, volume 2, Providence, RI, 1997. Online at http://www.ics.mq. edu.au/~einat/publications.html.
• 18: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 19: Jacques Savoy, An extended vector-processing scheme for searching information in hypertext systems, Information Processing and Management: an International Journal, v.32 n.2, p.155-170, March 1996 [doi>10.1016/S0306-4573(96)85003-5]
• 20: Amit Singhal , Marcin Kaszkiel, A case study in web search using TREC algorithms, Proceedings of the 10th international conference on World Wide Web, p.708-716, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372186]
• 21: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.7 Natural Language Processing
          Subjects: Text analysis

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

General Terms:
Design, Experimentation, Performance