Efficient summarization-aware search for online news articles

ABSTRACT

News portals gather and organize news articles published daily on the Internet. Typically, news articles are clustered into 'events' and each cluster is displayed with a short description of its contents. A particularly interesting choice for describing the contents of a cluster is a machine-generated multi-document summary of the articles in the cluster. Such summaries are informative and help news readers to identify and explore only clusters of interest. Naturally, multi-document clusters and summaries are also valuable to help users navigate the results of keyword-search queries. Unfortunately, current document summarizers are still slow; as a result, search strategies that define document clusters and their multi-document summaries online, in a query-specific manner, are prohibitively expensive. In contrast, search strategies that only return offline, query-independent document clusters are efficient, but might return clusters whose (query-independent) summaries are of little relevance to the queries. In this paper, we present an efficient Hybrid search strategy to address the limitations of fully online and fully offline summarization-aware search approaches. Extensive experiments involving user relevance judgments and real news articles show that the quality of our Hybrid results is high, and that these results are computed in substantially less time than with the fully online strategy. We have implemented our strategy and made it available on the Newsblaster news summarization system, which crawls and summarizes news articles from a variety of web sources on a daily basis.

REFERENCES

• 1: W. W. Cohen. Fast effective rule induction. In ICML'95, 1995.
• 2: J. L. Fleiss, B. Levin, M. C. Paik, J. Fleiss, and B. Levin.Statistical Methods for Rates Proportions. Wiley-Interscience, 2003.
• 3: Vasileios Hatzivassiloglou , Luis Gravano , Ankineedu Maganti, An investigation of linguistic features and clustering algorithms for topical document clustering, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.224-231, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345582]
• 4: Marti A. Hearst, Support Vector Machines, IEEE Intelligent Systems, v.13 n.4, p.18-28, July 1998 [doi>10.1109/5254.708428]
• 5: Marti A. Hearst , Jan O. Pedersen, Reexamining the cluster hypothesis: scatter/gather on retrieval results, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.76-84, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243216]
• 6: Anil Jain , Douglas Zongker, Feature Selection: Evaluation, Application, and Small Sample Performance, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.2, p.153-158, February 1997 [doi>10.1109/34.574797]
• 7: N. Jardine and C. J. van Rijsbergen. The use of hierarchical clustering in information retrieval. Information Storage and Retrieval, 7:217--240, 1971.
• 8: Thorsten Joachims, Making large-scale support vector machine learning practical, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 9: Thorsten Joachims, Learning to Classify Text Using Support Vector Machines: Methods, Theory and Algorithms, Kluwer Academic Publishers, Norwell, MA, 2002
• 10: D. Koller and M. Sahami. Toward optimal feature selection. In ICML'96, 1996.
• 11: A. Leuski and J. Allan. Improving interactive retrieval by combining ranked list and clustering. In RIAO'00, 2000.
• 12: C.-Y. Lin and E. Hovy. Automated multi-document summarization in NeATS. In HLT'02, 2002.
• 13: K. C. Litkowski. Summarization experiments in DUC 2004. In DUC'04, 2001.
• 14: Xiaoyong Liu , W. Bruce Croft, Cluster-based retrieval using language models, 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.1009026]
• 15: J. P. Marques De Sá. Applied Statistics. Springer Verlag, 2003.
• 16: K. R. McKeown et al. Tracking and summarizing news on a daily basis with Columbia's Newsblaster. In HLT'02, 2002.
• 17: Dragomir R. Radev , Sasha Blair-Goldensohn , Zhu Zhang , Revathi Sundara Raghavan, NewsInEssence: a system for domain-independent, real-time news clustering and multi-document summarization, Proceedings of the first international conference on Human language technology research, p.1-4, March 18-21, 2001, San Diego [doi>10.3115/1072133.1072208]
• 18: S. E. Robertson. Overview of the Okapi projects. Journal of Documentation, 53(1):3--7, 1997.
• 19: Anastasios Tombros , Robert Villa , C. J. Van Rijsbergen, The effectiveness of query-specific hierarchic clustering in information retrieval, Information Processing and Management: an International Journal, v.38 n.4, p.559-582, July 2002 [doi>10.1016/S0306-4573(01)00048-6]
• 20: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 21: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 22: Ellen Marie Voorhees, The effectiveness and efficiency of agglomerative hierarchic clustering in document retrieval, Cornell University, Ithaca, NY, 1986
• 23: Oren Zamir , Oren Etzioni, Web document clustering: a feasibility demonstration, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.46-54, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290956]
• 24: Oren Zamir , Oren Etzioni, Grouper: a dynamic clustering interface to Web search results, Proceeding of the eighth international conference on World Wide Web, p.1361-1374, May 1999, Toronto, Canada
• 25: Hua-Jun Zeng , Qi-Cai He , Zheng Chen , Wei-Ying Ma , Jinwen Ma, Learning to cluster web search results, 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.1009030]

INDEX TERMS

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

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

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
clustering, summarization, summarization-aware search