Method and apparatus for generating overview information for hierarchically related information

• US 20040117449A1
• Filed: 12/16/2002
• Published: 06/17/2004
• Est. Priority Date: 12/16/2002
• Status: Active Grant

• Current Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Newman, Paula S., Blitzer, John C., Brants, Thorsten H.
• Granted Patent: US 7,280,957 B2
• Time in Patent Office: Days
• US Class Current: 709/206
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 40/258 Heading extraction; Automatic titling; Numbering

Abstract

A method is provided for digesting the content of hierarchically related information. The method, which obtains relatively short overviews, selects a proportion of representative nodes and then extracts and organizes one or more sentences from the text associated with each selected node. For text trees representing archived discussions, the selection of nodes and sentences is from comment/response sequences drawn from lexically central nodes which will capture those aspects of the discussion considered most important to discussion participants.

Claims

1. ) A method of forming an overview for hierarchically related information, where the information can be represented as a set of nodes wherein each node is associated with a portion of the information comprising:

a) forming a set of lexically central nodes and a remainder set,

b) forming a set of auxiliary nodes from the remainder set,

c) combining the set of lexically central nodes and the set of auxiliary nodes to form an extraction node set,

d) selecting an overview string from the information associated with each node in the extraction node set, and

e) combining the overview strings to form an overview for the information.

2. ) The method of claim 1 wherein determining the lexically central nodes comprises:

a) determining a word vector for each node,

b) determining a lexical centroid of the word vectors, and

c) selecting a given number of nodes having word vectors closest to the lexical centroid.

3. ) The method of claim 1 wherein the step of forming a set of auxiliary nodes from the remainder set comprises selecting nodes which are parents of central nodes.

4. ) The method of claim 1 wherein the step of forming a set of auxiliary nodes from the remainder set comprises selecting nodes which are parents of more than a specified number of nodes.

5. ) The method of claim 1 wherein the step of forming a set of auxiliary nodes from the remainder set comprises selecting nodes which are parents of central nodes and selecting nodes which are parents of more than a specified number of nodes.

6. ) The method of claim 1 wherein selecting an overview string from the information associated with each node in the extraction node set comprises:

a) determining whether the node is a root node, and

b) responsive to the determination in step a, selecting an initial string from the information.

7. ) The method of claim 1 wherein selecting an overview string from the information associated with each node in the extraction node set comprises:

a) determining whether the node is in the set of lexically central nodes, and if the information associated with the node comprises one or more quoting portions, and

b) responsive to the determination in step a, selecting at least one string from the information following a quoting portion.

8. ) The method of claim 7 wherein an initial string is selected from the information.

9. ) The method of claim 1 wherein selecting an overview string from the information associated with each node in the extraction node set comprises:

a) determining whether the information associated with the node comprises one or more quoted portions, and

b) responsive to the determination in step a, selecting at least one string from the information comprising part of at least one quoted portion.

10. ) The method of claim 1 wherein selecting an overview string from the information associated with each node in the extraction node set comprises:

a) determining whether the node is an auxiliary node and the information associated with the node does not contain any quoted portions, and

b) responsive to the determination in step a, selecting at least one string from the final part of the information associated with the node.

11. ) The method of claim 7 wherein selecting at least one string from the information comprises selecting the most lexically central string.

12. ) The method of claim 2 wherein determining the lexically central nodes further comprises determining the lexical centroid of selected groups of adjacent nodes and selecting the node closest to the lexical centroid of each such group.

13. ) The method of claim 2 wherein determining the lexically central nodes further comprises

a) determining whether the nodes include the root node of a tree representing a stored conversation.

b) responsive to the determination in step a, selecting the root node and a proportion of its children.