A graph-theoretic approach to extract storylines from search results

ABSTRACT

We present a graph-theoretic approach to discover storylines from search results. Storylines are windows that offer glimpses into interesting themes latent among the top search results for a query; they are different from, and complementary to, clusters obtained through traditional approaches. Our framework is axiomatically developed and combinatorial in nature, based on generalizations of the maximum induced matching problem on bipartite graphs. The core algorithmic task involved is to mine for signature structures in a robust graph representation of the search results. We present a very fast algorithm for this task based on local search. Experiments show that the collection of storylines extracted through our algorithm offers a concise organization of the wealth of information hidden beyond the first page of search results.

REFERENCES

• 1: 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]
• 2: 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
• 3: J-Y. Cai. On the impossibility of certain ranking functions. International Mathematical Journal, 3(2):119--128, 2003.
• 4: T. Calishain. Clustering with search engines. http://www.llrx.com/features/clusteringsearch.htm.
• 5: S. Chakrabarti, B. Dom, D. Gibson, R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. Spectral filtering for resource discovery. In Proceedings of the ACM SIGIR Workshop on Hypertext Analysis, pages 13--21, 1998.
• 6: Douglass R. Cutting , David R. Karger , Jan O. Pedersen , John W. Tukey, Scatter/Gather: a cluster-based approach to browsing large document collections, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.318-329, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133214]
• 7: S. C. Deerwester, S. T. Dumais, T. K. Landauer, G. W. Fumas, and R. A. Harshman. Indexing by latent semantic analysis. Journal of the American Society for Information Science, 41(6):391--407, 1990.
• 8: Inderjit S. Dhillon , Subramanyam Mallela , Dharmendra S. Modha, Information-theoretic co-clustering, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956764]
• 9: R. Kannan , S. Vempala , A. Veta, On clusterings-good, bad and spectral, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.367, November 12-14, 2000
• 10: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 11: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Trawling the Web for emerging cyber-communities, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1481-1493, May 17, 1999
• 12: L. Stockmeyer and V. Vazirani. NP-Completeness of some generalizations of the maximum matching problem. Information Processing Letters, 15(1):14--19, 1982.
• 13: N. Tishby, F.C. Pereira, and W. Blalek. The information bottleneck method. In Proc. 37th Annual Allerton Conference on Communication, Control, and Computing, pages 368--377, 1999.
• 14: P. Tsaparas. Link Analysis Ranking Algorithms. PhD thesis, University of Toronto, 2003.
• 15: Oren Zamir , Oren Etzioni, Grouper: a dynamic clustering interface to Web search results, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1361-1374, May 17, 1999
• 16: O. Zamir, O. Etzioni, O. Madani, and R. M. Karp. Fast and intuitive clustering of web documents. In Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining, pages 287--290, 1997.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Web-based services

General Terms:
Algorithms, Experimentation, Human Factors, Measurement

Keywords:
clustering, communities, link analysis, search results, storylines