System and method for displaying clusters

• US 7,885,957 B2
• Filed: 01/14/2008
• Issued: 02/08/2011
• 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
• Primary Examiner(s): LEROUX, ETIENNE PIERRE
• Application Number:
  US12/014,068
• Publication Number:
  US 20080114763A1
• Time in Patent Office: 1,121 Days
• Field of Search: 707/2, 707/10, 707/724
• US Class Current: 707/724
• 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 displaying clusters is provided. A plurality of clusters are generated. Each cluster includes one or more documents. A cluster concept selected from the documents is identified. The cluster concepts that satisfy an acceptance criteria are selected. Spines are formed from the clusters associated therewith. The clusters including the cluster concepts not selected are assigned to one of the spines, which provides a best fit with the cluster concept. The spines are placed into a display, wherein each placed spine is unique. An anchor cluster with an open edge on the placed spines is identified. One or more of the spines not already in the display are placed. Similarity between the non-placed spine and each anchor cluster is determined. The anchor cluster most similar is selected. The non-placed spine is set on the open edge of the anchor cluster.

Claims

1. A system for displaying clusters, comprising:

a generator to generate a plurality of clusters, which each comprise one or more documents and to identify concepts for the clusters based on the documents;

a selection module to select the cluster concepts that satisfy an acceptance criteria and to form spines from the clusters associated therewith;

a best fit assignor to assign at least one of the remaining clusters to one of the spines, which provides a best fit with the cluster concepts for that cluster;

a spine placement module to place one or more of the spines into a display, wherein each placed spine is unique;

an anchor cluster identification module to identify an anchor cluster with an open edge on at least one of the placed spines; and

a visualization module to place one or more of the spines not already in the display, comprising;

a similarity module to determine a similarity between the non-placed spine and each anchor cluster and to select the anchor cluster most similar; and

an arrangement module to set the non-placed spine on the open edge of the anchor cluster.

2. A system according to claim 1, wherein one or more of the cluster concepts can be selected by a user.

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

an acceptance criteria module to define the acceptance criteria comprising at least one of a minimum cluster reference count, maximum cluster reference count, and user specified.

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

a similarity module to determine the anchor cluster most similar based on at least one of a cosine value concept vector, maximum bounds, minimum bounds, and median bounds.

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

a vector placement module to place the non-placed spine at the open edge along a vector defined from a center of the anchor cluster most similar.

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

a vector module to change an angle of the vector when the non-placed spine arranged at the open edge of the anchor cluster most similar satisfies a maximum line segment.

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

a related spine placement module to place the non-placed spines not previously arranged at the open edge of one such anchor cluster into the display in a related area.

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

an overlap module to minimize overlap between the arranged non-placed spines and the anchor cluster most similar.

9. A method for displaying clusters, comprising:

generating a plurality of clusters, which each comprise one or more documents and identifying concepts for the clusters based on the documents;

selecting the cluster concepts that satisfy an acceptance criteria and forming spines from the clusters associated therewith;

assigning at least one of the remaining clusters to one of the spines, which provides a best fit with the cluster concepts for that cluster;

placing one or more of the spines into a display, wherein each placed spine is unique;

identifying an anchor cluster with an open edge on at least one of the placed spines; and

placing one or more of the spines not already in the display, comprising;

determining a similarity between the non-placed spine and each anchor cluster and selecting the anchor cluster most similar; and

setting the non-placed spine on the open edge of the anchor cluster.

10. A method according to claim 9, wherein one or more of the cluster concepts can be selected by a user.

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

defining the acceptance criteria comprising at least one of a minimum cluster reference count, maximum cluster reference count, and user specified.

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

determining the anchor cluster most similar based on at least one of a cosine value concept vector, maximum bounds, minimum bounds, and median bounds.

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

placing the non-placed spine at the open edge along a vector defined from a center of the anchor cluster most similar.

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

changing an angle of the vector when the non-placed spine arranged at the open edge of the anchor cluster most similar satisfies a maximum line segment.

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

placing the non-placed spines not previously arranged at the open edge of one such anchor cluster into the display in a related area.

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

minimizing overlap between the arranged non-placed spines and the anchor cluster most similar.

17. A method for placing clusters into a display, comprising:

generating a set of clusters, each cluster comprising one or more concepts;

forming candidate spines from the clusters, comprising;

grouping each candidate spine from those clusters sharing at least one of the concepts; and

assigning the remaining clusters in the set to the candidate spines having a best fit;

placing those candidate spines that are sufficiently unique from the other candidate spines into a display; and

displaying the other candidate spines, comprising;

selecting anchor clusters on the placed candidate spines;

determining a similarity between at least one of the candidate spines and each anchor cluster; and

grafting the candidate spine on one such anchor cluster that is most similar.

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

applying acceptance criteria to the concepts; and

selecting those concepts that satisfy the acceptance criteria as candidate spine concepts.

19. A method according to claim 18, wherein the acceptance criteria comprise at least one such concept being contained in at least one of the clusters and within a predetermined maximum of the clusters.

20. A method according to claim 18, wherein each candidate spine concept defines a theme for one such candidate spine.