System and method for generating cluster spine groupings for display

• US 7,983,492 B2
• Filed: 02/07/2011
• Issued: 07/19/2011
• 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): Mariam; Daniel G
• Application Number:
  US13/022,580
• Publication Number:
  US 20110122151A1
• Time in Patent Office: 162 Days
• Field of Search: 382/181, 382/190, 382/197, 382/209, 382/224, 382/225, 382/305, 382/218, 345/440, 345/467, 707705-713
• US Class Current: 382/225
• 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 spine groupings for display is provided. A set of spines is obtained. Each spine in the set includes a grouping of clusters that share a common concept and are arranged linearly along a vector. Those spines that are unique from each other spine are identified. At least one remaining spine from the set of spines is selected. The remaining spine is compared to the unique spines. At least one spine group is formed by grafting the remaining spine onto the unique spine that is most similar. The spine group is displayed.

Claims

1. A system for generating cluster spine groupings for display, comprising:

a set of spines, each spine comprising a grouping of clusters sharing a common concept and arranged linearly along a vector;

a unique spine identifier to identify those spines that are unique from each other spine;

a spine group module to select at least one remaining spine from the set of spines, to compare the remaining spine to the unique spines, and to form at least one spine group by grafting the remaining spine onto the unique spine that is most similar; and

a display to present the spine group.

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

an anchor cluster module to identify an anchor cluster on the remaining spine, wherein the anchor cluster comprises at least one open edge; and

the spine group module to graft a further remaining spine onto the anchor cluster of the remaining spine at the at least one open edge as part of the spine group.

3. A system according to claim 1, wherein the display presents further spine groups in relation to the spine group.

4. A system according to claim 1, wherein the spine group module identifies at least one anchor cluster on the most similar unique spine, determines a cluster on the remaining spine that is most similar to the anchor cluster;

and grates the cluster of the remaining spine onto the anchor cluster of the most similar unique spine.

5. A system according to claim 1, wherein the remaining spine and the most similar unique spine have a minimum similarity of at least 0.1 similarity.

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

a unique spine selector to determine the unique spines, comprising;

a scoring module to calculate a spine concept score vector for each of the spines in the set;

a ranking module to order the spines based on a number of the clusters arranged linearly along the vector for each spine in the set;

a spine removal module to discard the spines that do not have a sufficient number of clusters;

a comparison module to compare the spines remaining in the set with one or more previously placed unique spines; and

a spine selector to select the spines that are sufficiently dissimilar from the previously placed unique spines as the unique spines.

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

a score determination module to determine the spine concept score vectors by aggregating concept scores assigned to each cluster along that spine.

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

a new spine group module to generate a new spine group comprising at least one of the remaining cluster spines not previously placed when a most similar unique spine is not available for the one remaining cluster spine.

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

a spine selector to select the spines for inclusion in the set, comprising;

a comparison module to apply an acceptance criteria to a corpus of spines;

a result identification module to identify those spines that satisfy the acceptance criteria as results;

a spine removal module to remove from the results, those spines that have only a single cluster and to further remove those clusters that have more than 10% of the total clusters; and

a spine assignment module to assign the spines remaining in the corpus to the set of spines.

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

a similarity module to determine similarities between the remaining spine and the unique spines comprising at least one of cosine similarity, minimum similarity bounds, maximum similarity bounds, and median similarity bounds.

11. A method for generating cluster spine groupings for display, comprising:

obtaining a set of spines, each spine comprising a grouping of clusters sharing a common concept and arranged linearly along a vector;

identifying those spines that are unique from each other spine;

selecting at least one remaining spine from the set of spines and comparing the remaining spine to the unique spines;

forming at least one spine group by grafting the remaining spine onto the unique spine that is most similar;

displaying the spine group; and

wherein the method is performed by a processor.

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

identifying an anchor cluster on the remaining spine, wherein the anchor cluster comprises at least one open edge; and

grafting a further remaining spine onto the anchor cluster of the remaining spine at the at least one open edge as part of the spine group.

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

generating and presenting further spine groups in the display.

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

identifying at least one anchor cluster on the most similar unique spine;

determining a cluster on the remaining spine that is most similar to the anchor cluster; and

grating the cluster of the remaining spine onto the anchor cluster of the most similar unique spine.

15. A method according to claim 11, wherein the remaining spine and the most similar unique spine have a minimum similarity of at least 0.1 similarity.

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

determining the unique spines, comprising;

calculating a spine concept score vector for each of the spines in the set;

ordering the spines based on a number of the clusters arranged linearly along the vector for each spine in the set;

discarding the spines that do not have a sufficient number of clusters;

comparing the spines remaining in the set with one or more previously placed unique spines; and

selecting the spines that are sufficiently dissimilar from the previously placed unique spines as the unique spines.

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

determining the spine concept score vectors by aggregating concept scores assigned to each cluster along that spine.

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

generating a new spine group comprising at least one of the remaining cluster spines not previously placed when a most similar unique spine is not available for the one remaining cluster spine.

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

selecting the spines for inclusion in the set, comprising;

applying an acceptance criteria to a corpus of spines;

identifying those spines that satisfy the acceptance criteria as results;

removing from the results, those spines that have only a single cluster;

removing from the results, those clusters that have more than 10% of the total clusters; and

assigning the spines remaining in the corpus to the set of spines.

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

determining similarities between the remaining spine and the unique spines comprising at least one of cosine similarity, minimum similarity bounds, maximum similarity bounds, and median similarity bounds.