Computer-implemented system and method for generating clusters for placement into a display

• US 9,558,259 B2
• Filed: 12/07/2015
• Issued: 01/31/2017
• Est. Priority Date: 08/31/2001
• Status: Expired due to Fees

• Current Assignee: Nuix North America Inc. (Nuix Ltd.)
• Original Assignee: FTI Consulting Technology LLC (FTI Consulting Incorporated)
• Inventors: Gallivan, Dan
• Primary Examiner(s): Perveen, Rehana
• Assistant Examiner(s): Hoffler, Raheem
• Application Number:
  US14/961,845
• Publication Number:
  US 20160085849A1
• Time in Patent Office: 421 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: G06F 16/287 Visualization; Browsing
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A computer-implemented system and method for generating clusters for placement into a display is provided. A set of clusters is generated from a document set. A single cluster of related documents from the document set is obtained and at least one new cluster is added. One such document in the set is compared to the cluster. A difference in distance between the document and a common origin and the cluster and the common origin is determined. The document is designated as the new cluster when the difference fails to satisfy a predetermined threshold. One or more cluster spines each having two or more clusters placed along a vector are placed into a display. The clusters along each spine are identified as similar and the clusters of one such spine are also similar to further clusters located along a further spine having a small cosine rotation from that cluster spine.

Claims

1. A computer-implemented system for generating clusters for placement into a display, comprising:

a database to store a document set; and

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

generate a set of clusters from the document set by obtaining a single cluster of related documents from the document set and adding at least one new cluster comprising comparing one such document in the set to the cluster, determining a difference in distance between the document and a common origin and the cluster and the common origin, and designating the document as the new cluster when the difference fails to satisfy a predetermined similarity threshold;

place into a display one or more cluster spines each comprising two or more of the clusters in the set placed along a vector; and

identify the clusters along each spine as similar, wherein the clusters in one such spine are also similar to further clusters located along a further spine having a small cosine rotation from that cluster spine.

2. A system according to claim 1, wherein the display is three-dimensional and each cluster represents multi-dimensional data modeled in the three-dimensional display.

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

an identification module to identify for each cluster in the set a center and radius.

4. A system according to claim 3, wherein the center of each cluster is located at a fixed distance from the common origin.

5. A system according to claim 3, wherein the radius of each cluster in the set is independent of the other clusters and reflects a relative number of the related documents in that cluster.

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

a cluster presentation module to display each cluster in the set as one of a circular shape and non-circular shape.

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

a cluster completion module to finalize the clusters in the set prior to generating the cluster spines by performing at least one of merging two or more of the clusters into a single cluster, splitting a single cluster into two or more clusters, and removing minimal clusters.

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

a calculation module to calculate each of the distances between the cluster and the common origin and between the document and the common origin as a Euclidean distance.

9. A system according to claim 1, wherein each document in the set appears in at least one cluster.

10. A system according to claim 1, wherein each cluster in the set comprises a center of mass and defines a convex volume.

11. A computer-implemented method for generating clusters for placement into a display, comprising:

generating a set of clusters from a document set, comprising;

obtaining a single cluster of related documents from the document set; and

adding at least one new cluster, comprising;

comparing one such document in the set to the cluster;

determining a difference in distance between the document and a common origin and the cluster and the common origin; and

designating the document as the new cluster when the difference fails to satisfy a predetermined similarity threshold;

placing into a display one or more cluster spines each comprising two or more of the clusters in the set placed along a vector; and

identifying the clusters along each spine as similar, wherein the clusters in one such spine are also similar to further clusters located along a further spine having a small cosine rotation from that cluster spine.

12. A method according to claim 11, wherein the display is three-dimensional and each cluster represents multi-dimensional data modeled in the three-dimensional display.

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

identifying for each cluster in the set a center and radius.

14. A method according to claim 13, wherein the center of each cluster is located at a fixed distance from the common origin.

15. A method according to claim 13, wherein the radius of each cluster in the set is independent of the other clusters and reflects a relative number of the related documents in that cluster.

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

displaying each cluster in the set as one of a circular shape and non-circular shape.

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

finalizing the clusters in the set prior to generating the cluster spines, comprising at least one of;

merging two or more of the clusters into a single cluster;

splitting a single cluster into two or more clusters; and

removing minimal clusters.

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

calculating each of the distances as a Euclidean distance.

19. A method according to claim 11, wherein each document in the set appears in at least one cluster.

20. A method according to claim 11, wherein each cluster in the set comprises a center of mass and defines a convex volume.