Computer-implemented system and method for generating and placing cluster groups

• US 9,619,909 B2
• Filed: 11/14/2016
• Issued: 04/11/2017
• 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:
  US15/351,371
• Publication Number:
  US 20170061661A1
• Time in Patent Office: 148 Days
• Field of Search: 382181, 382190, 382209, 382218, 382224, 382225, 382305, 345440, 345467, 707707, 707710, 707713
• 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 computer-implemented system and method for generating and placing cluster groups is provided. A set of clusters each having one or more documents is maintained. A portion of the clusters is assigned to two or more spines. The cluster spines are ordered by cluster length. Those cluster spines that are unique are identified in decreasing cluster length order and placed. One or more of the remaining spines are placed in relation to at least one of the placed unique spines. At least one of the remaining clusters is placed in relation to one or more of the unique placed spines. Groups of clusters are displayed. Each group includes two or more of one such unique placed spine, the remaining spines placed in relation to that placed unique spine; and the remaining clusters placed in relation to the unique placed spine.

Claims

1. A computer-implemented system for generating and placing cluster groups, comprising:

a set of clusters each comprising one or more documents;

a display; and

a server comprising a central processing unit, memory, an input port to receive the cluster set, and an output port, wherein the central processing unit is configured to;

assign at least a portion of the clusters to two or more spines;

order the cluster spines by length;

identify those cluster spines that are unique in decreasing length order and place the unique spines;

place one or more of the remaining spines in relation to at least one of the placed unique spines;

place one or more of the remaining clusters in relation to at least one of the unique placed spines; and

display groups of clusters, each group comprising two or more of one such placed unique spine, the remaining spines placed in relation to that placed unique spine; and

the remaining clusters placed in relation to the unique placed spine.

2. A system according to claim 1, wherein the central processing unit is further configured to:

select the spines assigned to the clusters by comparing each cluster in the set to each spine, determining a similarity between each cluster and each spine, and identifying for each cluster the spine having the maximum similarity.

3. A system according to claim 1, wherein the central processing unit is further configured to:

identify one such placed unique spine on which to graft one of the remaining spines by maintaining a list of anchor clusters on each of the placed unique spines, identifying from the list at least one of a strong anchor cluster and a weak anchor cluster, wherein the strong anchor cluster comprises a concept in common with the remaining spine, identifying the placed unique spine with a maximum similarity to the remaining spine, and positioning the remaining spine with respect to the strong anchor cluster or the weak anchor cluster on the placed unique spine.

4. A system according to claim 3, wherein the central processing unit is further configured to perform one of:

selecting the strong anchor cluster over the weak anchor cluster for positioning the remaining spine; and

selecting the weak anchor cluster for positioning the remaining spine when the placed unique spine has no strong anchor cluster.

5. A system according to claim 3, wherein the central processing unit is further configured to perform one of:

grafting the remaining spine onto the strong anchor cluster; and

placing the remaining spine adjacent to the weak anchor cluster.

6. A system according to claim 3, wherein the central processing unit is further configured to:

arrange the remaining spine on the strong anchor cluster along a vector extending from a center of the cluster.

7. A system according to claim 1, wherein the central processing unit is further configured to:

compare each of the remaining spines to the placed unique spines;

determine that one such remaining spine fails to satisfy a threshold similarity; and

place the remaining spine independently of the placed unique spines.

8. A system according to claim 1, wherein the central processing unit is further configured to:

identify the placed unique spines for placing one such remaining cluster by building a list of candidate anchor clusters on the placed unique spines, determining a similarity of each candidate anchor cluster and the remaining cluster, identifying the candidate anchor cluster with the highest similarity to the remaining cluster, and selecting the placed unique spine having the candidate anchor cluster with the highest similarity.

9. A system according to claim 1, wherein the central processing unit is further configured to:

identify those spine groups that are unique from the other spines groups; and

place the unique spine groups into a display.

10. A system according to claim 9, wherein the central processing unit is further configured to:

arrange the unique spine groups around a centrally placed shape in the display.

11. A computer-implemented method for generating and placing cluster groups, comprising:

maintaining a set of clusters each comprising one or more documents;

assigning at least a portion of the clusters to two or more spines;

ordering the cluster spines with clusters by length;

identifying those cluster spines that are unique in decreasing length order and placing the unique spines;

placing one or more of the remaining spines in relation to at least one of the placed unique spines;

placing one or more of the remaining clusters in relation to at least one of the placed unique spines;

displaying groups of clusters, each group comprising two or more of one such placed unique spine, the remaining spines placed in relation to that placed unique spine; and

the remaining clusters placed adjacent to the unique placed spine.

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

selecting the spines for assignment with the clusters, comprising;

comparing each cluster in the set to each spine and determining a similarity between each cluster and spine; and

identifying for each cluster the spine having the maximum similarity.

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

identifying one such placed unique spine on which to graft one of the remaining spines, comprising;

maintaining a list of anchor clusters on each of the placed unique spines;

identifying from the list at least one of a strong anchor cluster and a weak anchor cluster, wherein the strong anchor cluster comprises a concept in common with the remaining spine;

identifying the placed unique spine with a maximum similarity to the remaining spine; and

positioning the remaining spine with respect to the strong anchor cluster or the weak anchor cluster on the placed unique spine.

14. A method according to claim 13, further comprising at least one of:

selecting the strong anchor cluster over the weak anchor cluster for positioning the remaining spine; and

selecting the weak anchor cluster for positioning the remaining spine when the placed unique spine has no strong anchor cluster.

15. A method according to claim 13, further comprising at least one of:

grafting the remaining spine onto the strong anchor cluster; and

placing the remaining spine adjacent to the weak anchor cluster.

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

arranging the remaining spine on the strong anchor cluster along a vector extending from a center of the cluster.

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

comparing each of the remaining spines to the placed unique spines;

determining that one such remaining spine fails to satisfy a threshold similarity; and

placing the remaining spine independently of the placed unique spines.

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

identifying the placed unique spines for placing one such remaining cluster, comprising;

building a list of candidate anchor clusters on the placed unique spines;

determining a similarity of each candidate anchor cluster and the remaining cluster;

identifying the candidate anchor cluster with the highest similarity to the remaining cluster; and

selecting the placed unique spine having the candidate anchor cluster with the highest similarity.

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

identifying those spine groups that are unique from the other spines groups; and

placing the unique spine groups into a display.

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

arranging the unique spine groups around a centrally placed shape in the display.