System and method for generating cluster spines

• US 8,312,019 B2
• Filed: 02/07/2011
• Issued: 11/13/2012
• Est. Priority Date: 02/13/2004
• Status: Expired due to Term

• Current Assignee: Nuix North America Inc. (Nuix Ltd.)
• Original Assignee: FTI Consulting Technology LLC (FTI Consulting Incorporated)
• Inventors: Evans, Lynne Marie
• Primary Examiner(s): LEROUX, ETIENNE PIERRE
• Application Number:
  US13/022,586
• Publication Number:
  US 20110125751A1
• Time in Patent Office: 645 Days
• Field of Search: 707/2, 707/739, 707/737, 715/900
• US Class Current: 707/737
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/287 Visualization; Browsing
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/358 Browsing; Visualisation therefor
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06T 11/20 Drawing from basic elements, e.g. lines or circles
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G06T 2200/32 involving image mosaicing
• CPC Class Codes: G06V 30/416 Extracting the logical structure, e.g. chapters, sections or page numbers; Identifying elements of the document, e.g. authors
• CPC Class Codes: H05K 999/99 dummy group
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A system and method for generating cluster spines is provided. Clusters of documents are maintained. Each document is associated with a document concept that is formed from one or more terms extracted from that document. At least one cluster concept is determined for each cluster. The document concepts are ranked and at least one of the document concepts that is highly ranked is selected as the cluster concept. One or more spines are formed. Each spine includes two or more clusters that share at least one of the cluster concepts. The shared cluster concept is identified as a spine concept. One or more of the remaining clusters is assigned to the spines based on a similarity between the cluster concepts for the remaining clusters and the spine concepts for the formed spines.

Claims

1. A system for generating cluster spines, comprising:

a set of clusters, each cluster comprising one or more documents and each document associated with a document concept formed from one or more terms extracted from that document;

a cluster concept determination module to determine at least one cluster concept for each cluster, comprising;

a concept ranking module to rank the document concepts;

a concept selection module to select at least one of the document concepts that is highly ranked as the cluster concept; and

a concept removal module to discard those cluster concepts that are referenced by more than 10% of the clusters;

a spine generation module to form one or more spines each comprising two or more clusters from the cluster set that share at least one of the cluster concepts, wherein the shared cluster concept is identified as a spine concept;

a cluster assignment module to assign one or more of the clusters remaining in the cluster set to the spines based on a similarity between the cluster concepts for the remaining clusters and the spine concepts for the formed spines; and

a processor to execute the modules.

2. A system according to claim 1, further comprising:

a document scoring module to score each document concept based on at least one of a frequency of occurrence of the terms associated with that document concept, concept weight, structural weight, and corpus weight.

3. A system according to claim 2, further comprising:

a cluster scoring module to determine a score for each cluster concept by aggregating the document concept scores for each document concept in that cluster.

4. A system according to claim 3, further comprising:

a spine scoring module to determine a score for each spine concept by aggregating the cluster concept scores for each cluster associated with that spine.

5. A system according to claim 1, wherein the cluster concepts are each located in an initial center of the associated cluster and in a minimum number of documents.

6. A system according to claim 1, wherein the minimum number of documents comprises one or more of a minimum of two documents, a minimum of 30% of the documents in that cluster, and a minimum having a greater value of the two documents and the 30% of the documents.

7. A system according to claim 1, further comprising:

a cluster grafting module to graft the one or more remaining clusters onto the spines that are most similar.

8. A system according to claim 1, further comprising:

a unique spine identifier to select one or more one unique spines from the formed spines; and

a display to present the unique spines.

9. A system according to claim 8, further comprising:

a spine group generator to generate one or more spine groups, comprising;

a comparison module to compare at least one remaining spine from the formed spines with the placed unique spines;

an identification module to identify the placed unique spine most similar to the at least one remaining spine; and

a placement module to position the at least one remaining spine adjacent to the placed unique spine.

10. A method for generating cluster spines by executing on a computer the method comprising:

maintaining a set of clusters, each cluster comprising one or more documents and each document associated with a document concept formed from one or more terms extracted from that document;

determining at least one cluster concept for each cluster, comprising;

ranking the document concepts;

selecting at least one of the document concepts that is highly ranked as the cluster concept; and

discarding those cluster concepts that are referenced by more than 10% of the clusters;

forming one or more spines each comprising two or more clusters from the cluster set that share at least one of the cluster concepts, wherein the shared cluster concept is identified as a spine concept; and

assigning one or more of the clusters remaining in the cluster set to the spines based on a similarity between the cluster concepts for the remaining clusters and the spine concepts for the formed spines.

11. A method according to claim 10, further comprising:

scoring each document concept based on at least one of a frequency of occurrence of the terms associated with that document concept, concept weight, structural weight, and corpus weight.

12. A method according to claim 11, further comprising:

determining a score for each cluster concept by aggregating the document concept scores for each document concept in that cluster.

13. A method according to claim 12, further comprising:

determining a score for each spine concept by aggregating the cluster concept scores for each cluster associated with that spine.

14. A method according to claim 10, wherein the cluster concepts are each located in an initial center of the associated cluster and in a minimum number of documents.

15. A method according to claim 10, wherein the minimum number of documents comprises one or more of a minimum of two documents, a minimum of 30% of the documents in that cluster, and a minimum having a greater value of the two documents and the 30% of the documents.

16. A method according to claim 10, further comprising:

grafting the one or more remaining clusters onto the spines that are most similar.

17. A method according to claim 10, further comprising:

selecting one or more one unique spines from the formed spines; and

placing the unique spines into a display.

18. A method according to claim 17, further comprising:

generating one or more spine groups, comprising;

comparing at least one remaining spine from the formed spines with the placed unique spines;

identifying the placed unique spine most similar to the at least one remaining spine; and

positioning the at least one remaining spine adjacent to the placed unique spine.