Unweaving a web of documents

ABSTRACT

We develop an algorithmic framework to decompose a collection of time-stamped text documents into semantically coherent threads. Our formulation leads to a graph decomposition problem on directed acyclic graphs, for which we obtain three algorithms --- an exact algorithm that is based on minimum cost flow and two more efficient algorithms based on maximum matching and dynamic programming that solve specific versions of the graph decomposition problem. Applications of our algorithms include superior summarization of news search results, improved browsing paradigms for large collections of text-intensive corpora, and integration of time-stamped documents from a variety of sources. Experimental results based on over 250,000 news articles from a major newspaper over a period of four years demonstrate that our algorithms efficiently identify robust threads of varying lengths and time-spans.

REFERENCES

• 1: Gagan Aggarwal , Mayur Datar , Sridhar Rajagopalan , Matthias Ruhl, On the Streaming Model Augmented with a Sorting Primitive, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.540-549, October 17-19, 2004 [doi>10.1109/FOCS.2004.48]
• 2: Rakesh Agrawal , Sridhar Rajagopalan , Ramakrishnan Srikant , Yirong Xu, Mining newsgroups using networks arising from social behavior, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775227]
• 3: James Allan, Automatic hypertext construction, Cornell University, Ithaca, NY, 1996
• 4: J. Allan, J. Carbonell, G. Doddington, J. Yamron, and Y. Yang. Topic detection and tracking pilot study: Final report. DARPA Broadcast News Transcription and Understanding Workshop, 1998.
• 5: James Allan , Rahul Gupta , Vikas Khandelwal, Temporal summaries of new topics, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.10-18, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383954]
• 6: William James Blustein , Sylvia Osborn, Hypertext versions of journal articles: computer-aided linking and realistic human-based evaluation, 1999
• 7: T. Dalamagas. NHS: A tool for the automatic construction of news hypertext, 1998.
• 8: T. Dalamagas and M. D. Dunlop. Automatic construction of news hypertext. In HIM, pages 265--278, 1997.
• 9: Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
• 10: Gary William Flake , Steve Lawrence , C. Lee Giles, Efficient identification of Web communities, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.150-160, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347121]
• 11: M. Garey and D. Johnson. Computers and Intractability. Freeman, 1979.
• 12: A. Goldberg , R. Tarjan, Solving minimum-cost flow problems by successive approximation, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.7-18, January 1987, New York, New York, United States [doi>10.1145/28395.28397]
• 13: S. J. Green. Automatically generating hypertext in newspaper articles by computing semantic relatedness. In Joint Conf. on New Methods in Lang. and Comp. Nat. Lang. Learning, pages 101--110, 1998.
• 14: Monika Henzinger , Bay-Wei Chang , Brian Milch , Sergey Brin, Query-free news search, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775154]
• 15: J. E. Hopcroft and R. M. Karp. An n5/2 algorithm for maximum matchings in bipartite graphs. SICOMP, 24(2):225--231, 1973.
• 16: Jon Kleinberg, Bursty and hierarchical structure in streams, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775061]
• 17: Ravi Kumar , Uma Mahadevan , D. Sivakumar, A graph-theoretic approach to extract storylines from search results, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014078]
• 18: 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
• 19: J.-J. Pan. Path Partition and Its Variation in Graphs. PhD thesis, National Chiao Tung U., 2004.
• 20: A. F. Smeaton and P. J. Morrissey. Experiments on the automatic construction of hypertexts from texts. The New Review of Hypermedia and Multimedia, 1:23--39, 1995.
• 21: David A. Smith, Detecting events with date and place information in unstructured text, Proceedings of the 2nd ACM/IEEE-CS joint conference on Digital libraries, July 14-18, 2002, Portland, Oregon, USA [doi>10.1145/544220.544260]
• 22: Russell Swan , James Allan, Automatic generation of overview timelines, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.49-56, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345546]
• 23: Éva Tardos, A strongly polynomial minimum cost circulation algorithm, Combinatorica, v.5 n.3, p.247-255, 1985 [doi>10.1007/BF02579369]
• 24: Naohiko Uramoto , Koichi Takeda, A method for relating multiple newspaper articles by using graphs, and its application to Webcasting, Proceedings of the 36th annual meeting on Association for Computational Linguistics, p.1307-1313, August 10-14, 1998, Montreal, Quebec, Canada
• 25: Yiming Yang , Tom Pierce , Jaime Carbonell, A study of retrospective and on-line event detection, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.28-36, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290953]

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
graph algorithms, graph decomposition, news threads