System and Method for Grouping Cluster Spines Into a Two-Dimensional Visual Display Space

• US 20100220112A1
• Filed: 05/17/2010
• Published: 09/02/2010
• Est. Priority Date: 02/13/2004
• Status: Active Grant

• Current Assignee: Nuix North America Inc. (Nuix Ltd.)
• Original Assignee: FTI Consulting Technology LLC (FTI Consulting Incorporated)
• Inventors: Evans, Lynne Marie
• Granted Patent: US 7,885,468 B2
• Time in Patent Office: Days
• US Class Current: 345/619
• 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 grouping cluster spines into a two-dimensional visual display space is provided. Clusters of concepts, each extracted from documents, are obtained. Spines are formed by placing the clusters sharing at least one of the concepts along a spine. The spines are ordered based on a length of each spine. One or more of the spines are selected as unique spines and placed into a visual display space. A similarity is determined between one of the spines not placed and each of the placed unique spines. The placed unique spine most similar is identified. An anchor cluster on the most similar unique spine that satisfies a threshold similarity with the unplaced spine is selected. A cluster on the unplaced spine that is most similar to the selected anchor cluster is identified and grafted to the selected anchor cluster as a group of cluster spines.

Claims

1. A system for grouping cluster spines into a two-dimensional visual display space, comprising:

a spine generator to obtain clusters of concepts each extracted from one or more documents and to form spines by placing the clusters sharing at least one of the concepts along a vector;

a spine ordering module to order the spines based on a length of each spine;

a spine placement module to select one or more of the spines, each unique from the other spines, as unique spines and to place the unique spines into a visual display space;

a similarity module to determine a similarity between at least one of the spines not placed and each of the placed unique spines and to identify the placed unique spine most similar;

an anchor selection module to select at least one anchor cluster on the most similar unique spine that satisfies a threshold similarity with the unplaced spine;

a grafting module to identify one of the clusters on the unplaced spine that is most similar to the selected anchor cluster and to graft the most similar cluster to the selected anchor cluster such that the unplaced spine is positioned along a vector extending from a center of the selected anchor cluster to form a group of cluster spines; and

a display to display the group of cluster spines in the visual display space.

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

a size module to determine the spine length based on a number of the clusters located along that spine.

3. A system according to claim 1, wherein the most similar anchor cluster comprises a strong anchor cluster that shares a common concept with the unplaced spine.

4. A system according to claim 1, wherein the most similar anchor cluster comprises a weak anchor cluster comprising a minimum similarity with the unplaced spine

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

an anchor identification module to identify additional anchor clusters on the unplaced spine by locating an open edge formed by an additional vector extending from a center of one of the clusters along that unplaced spine.

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

a spine group generator to generate a new spine group when one of the unplaced spines is insufficiently similar to the placed unique spines.

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

a spine length determination module to change an angle of the unplaced spine grafted to the most similar placed unique spine when a number of the clusters on the unplaced spine and most similar placed unique spine exceed a maximum line segment threshold.

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

a unique spine identification module to select, based on the spine length, the longest spine as an initial unique spine for placement into the visual display space.

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

a spine group placement module to place the spine group circumferentially about a central shape in the visual display space with other spine groups.

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

a similarity calculator to calculate the similarity between the unplaced spine and each of the placed unique spines, comprising;

a vector module to generate a concept score vector for the unplaced spine and each of the placed unique spines; and

a comparison module to compare the concept score vectors for the unplaced spine and one such placed unique spines to determine the similarity.

11. A method for grouping cluster spines into a two-dimensional visual display space, comprising:

obtaining clusters of concepts each extracted from one or more documents and forming spines by placing the clusters sharing at least one of the concepts along a vector;

ordering the spines based on a length of each spine;

selecting one or more of the spines, each unique from the other spines, as unique spines and placing the unique spines into a visual display space;

determining a similarity between at least one of the spines not placed and each of the placed unique spines and identifying the placed unique spine most similar;

selecting at least one anchor cluster on the most similar unique spine that satisfies a threshold similarity with the unplaced spine;

identifying one of the clusters on the unplaced spine that is most similar to the selected anchor cluster and grafting the most similar cluster to the selected anchor cluster such that the unplaced spine is positioned along a vector extending from a center of the selected anchor cluster to form a group of cluster spines; and

displaying the group of cluster spines in the visual display space.

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

determining the spine length based on a number of the clusters located along that spine.

13. A method according to claim 11, wherein the most similar anchor cluster comprises a strong anchor cluster that shares a common concept with the unplaced spine.

14. A method according to claim 11, wherein the most similar anchor cluster comprises a weak anchor cluster comprising a minimum similarity with the unplaced spine

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

identifying additional anchor clusters on the unplaced spine by locating an open edge formed by an additional vector extending from a center of one of the clusters along that unplaced spine.

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

generating a new spine group when one of the unplaced spines is insufficiently similar to the placed unique spines.

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

changing an angle of the unplaced spine grafted to the most similar placed unique spine when a number of the clusters on the unplaced spine and most similar placed unique spine exceed a maximum line segment threshold.

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

selecting, based on the spine length, the longest spine as an initial unique spine for placement into the visual display space.

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

placing the spine group circumferentially about a central shape in the visual display space with other spine groups.

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

calculating the similarity between the unplaced spine and each of the placed unique spines, comprising;

generating a concept score vector for the unplaced spine and each of the placed unique spines; and

comparing the concept score vectors for the unplaced spine and one such placed unique spines to determine the similarity.