Multi-document summarization system and method

• US 7,366,711 B1
• Filed: 02/18/2000
• Issued: 04/29/2008
• Est. Priority Date: 02/19/1999
• Status: Expired due to Fees

• Current Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Original Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Inventors: Barzilay, Regina, McKeown, Kathleen R.
• Primary Examiner(s): Corrielus; Jean M.
• Application Number:
  US09/913,745
• Time in Patent Office: 2,993 Days
• Field of Search: 707/3, 707/4, 707/5, 707/6, 707/10, 707/101, 704/9, 715/526, 715/530, 715/540, 715/531
• US Class Current: 1/1
• CPC Class Codes: G06F 16/345 Summarisation for human users
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A summary for a collection of related documents can be generated by extracting phrases from the documents which include common focus elements. Phrase intersection analysis is then performed on the extracted phrases to generate a phrase intersection table, where identical or equivalent phrases are identified. Temporal processing on the phrases in the phrase intersection table is performed to remove ambiguous time references and to sort the phrases in a temporal sequence. Sentence generation is then used to combine the phrases in the phrase intersection table into a coherent summary.

Claims

1. A method for generating a summary of a plurality of related documents available in computer readable media in a collection comprising:

extracting phrases having focus elements from the plurality of documents;

performing phrase intersection analysis on the extracted phrases to generate a phrase intersection table;

performing temporal processing by applying a timestamp to the phrases in the phrase intersection table and ordering the phrases based on the timestamps; and

generating a summary of the plurality of related documents available in computer readable media by performing sentence generation using the phrases in the phrase intersection table which have been subject to said temporal processing.

2. The method of generating a summary as defined by claim 1, wherein the phrase intersection analysis comprises:

representing the phrases in tree structures having root nodes and children nodes;

selecting those tree structures with verb root nodes;

comparing the selected root nodes to the other root nodes to identify identical nodes;

applying paraphrasing rules to non-identical root nodes to determine if non identical nodes are equivalent; and

evaluating the children nodes of those tree structures where the parent nodes are identical or equivalent.

3. The method of claim 2, wherein the tree structure is a DSYNT tree structure.

4. The method of claim 2, wherein the paraphrasing rules are selected from the group consisting of ordering of sentence components, main clause versus a relative clause, different syntactic categories, change in grammatical features, omission of an empty head, transformation of one part of speech to another, and semantically related words.

5. The method of claim 1, wherein the temporal processing further includes:

wherein the time stamp applied to the phrases in the phrase intersection table is based on a first occurrence of the phrase in the collection;

substituting date certain references for ambiguous temporal references;

and

inserting a temporal marker if a temporal gap between phrases exceeds a threshold value.

6. The method of claim 1, further comprising a phrase divergence processing operation.

7. The method of claim 1, wherein the sentence generation includes mapping phrases to an input format of a language generation engine and operating the language generation engine.

8. A system for generating a summary of a plurality of related documents in a collection comprising:

a storage device for storing the documents in the collection;

a lexical database; and

a processing subsystem, the processing subsystem being operatively coupled to the storage device and the lexical database, the processing subsystem being programmed to access the plurality of related documents in the storage device and generate a summary thereof by;

using the lexical database to extract phrases having focus elements from the plurality of documents;

performing phrase intersection analysis on the extracted phrases to generate a phrase intersection table;

performing temporal processing by applying a timestamp to the phrases in the phrase intersection table and ordering the phrases based on the timestamps; and

performing sentence generation using the phrases in the phrase intersection table which have been subject to said temporal processing.

9. The system for generating a summary as defined by claim 8, wherein the phrase intersection analysis processing further comprises:

representing the phrases as data structures having root nodes and children nodes;

selecting those data structures with verb root nodes;

comparing the selected root nodes to the other root nodes to identify identical nodes;

applying paraphrasing rules to non-identical root nodes to determine if non identical nodes are equivalent; and

evaluating the children nodes of those tree structures where the parent nodes are identical or equivalent.

10. The system of claim 9, wherein the data structure is a DSYNT tree structure.

11. The system of claim 9, wherein the paraphrasing rules are selected from the group consisting of ordering of sentence components, main clause versus a relative clause, different syntactic categories, change in grammatical features, omission of an empty head, transformation of one part of speech to another, and semantically related words.

12. The system of claim 8, wherein the temporal processing further includes:

wherein the time stamp applied to the phrases in the phrase intersection table is based on a first occurrence of the phrase in the collection;

substituting date certain references for ambiguous temporal references;

and

inserting a temporal marker if a temporal gap between phrases exceeds a threshold value.

13. The system of claim 8, further comprising a phrase divergence processing operation.

14. The system of claim 8, wherein the processing subsystem includes a language generation engine and wherein sentence generation includes mapping phrases to an input format of the language generation engine and then operating the language generation engine.

15. The system of claim 8, wherein the storage device for storing the documents in the collection is remotely located from the processing subsystem.

16. A computer readable media for programming a computer system to perform a method of generating a summary of a plurality of related documents in a collection comprising:

extracting phrases having focus elements from the plurality of documents;

performing phrase intersection analysis on the extracted phrases to generate a phrase intersection table;

performing temporal processing by applying a timestamp to the phrases in the phrase intersection table and ordering the phrases based on the timestamps; and

generating a summary of the plurality of related documents by performing sentence generation using the phrases in the phrase intersection table which have been subject to said temporal processing.

17. The computer readable media of claim 16, wherein the phrase intersection analysis comprises:

representing the phrases in tree structures having root nodes and children nodes;

selecting those tree structures with verb root nodes;

comparing the selected root nodes to the other root nodes to identify identical nodes;

applying paraphrasing rules to non-identical root nodes to determine if non identical nodes are equivalent; and

evaluating the children nodes of those tree structures where the parent nodes are identical or equivalent.

18. The computer readable media of claim 17, wherein the tree structure is a DSYNT tree structure.

19. The computer readable media of claim 17, wherein the paraphrasing rules are selected from the group consisting of ordering of sentence components, main clause versus a relative clause, different syntactic categories, change in grammatical features, omission of an empty head, transformation of one part of speech to another, and semantically related words.

20. The computer readable media of claim 16, wherein the temporal processing further includes:

wherein the time stamp applied to the phrases in the phrase intersection table is based on a first occurrence of the phrase in the collection;

substituting date certain references for ambiguous temporal references;

and

inserting a temporal marker if a temporal gap between phrases exceeds a threshold value.

21. The computer readable media of claim 16, further comprising a phrase divergence processing operation.

22. The computer readable media of claim 16, wherein the sentence generation includes mapping phrases to an input format of a language generation engine and operating the language generation engine.