System and method for arranging concept clusters in thematic relationships in a two-dimensional visual display area

• US 7,271,804 B2
• Filed: 02/25/2002
• Issued: 09/18/2007
• Est. Priority Date: 02/25/2002
• Status: Active Grant

• Current Assignee: Nuix North America Inc. (Nuix Ltd.)
• Original Assignee: Attenex Corp. (FTI Consulting Incorporated)
• Inventors: Evans, Lynne Marie
• Primary Examiner(s): Brier; Jeffery A
• Application Number:
  US10/084,401
• Publication Number:
  US 20040172600A1
• Time in Patent Office: 2,031 Days
• Field of Search: 345/440, 345/635
• US Class Current: 345/440
• CPC Class Codes: G06F 16/287 Visualization; Browsing
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: G06F 16/358 Browsing; Visualisation therefor
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs

Abstract

A system and method for arranging concept clusters in thematic relationship in a two-dimensional visual display space is described. A plurality of stored clusters are selected from a multi-dimensional visualization space sharing a common theme including at least one concept. Each theme logically represents one or more concepts based on terms extracted from a document set. Each cluster not yet grouped from the selected clusters for the shared common theme is combined in order into a list of placeable clusters. Each clusters list is grafted into a grouping of one or more other clusters lists at an anchor point. The anchor point includes an open edge formed along a vector defined from the center of one such cluster in the grouping. The clusters in each other clusters list share at least one concept represented in the shared common theme.

Claims

1. A system for generating a two-dimensional spatial arrangement of a cluster rendering, comprising:

clusters stored in a storage to represent concepts and terms extracted from a set of documents;

a set of the stored clusters selected with each selected cluster sharing a common theme comprising one or more of the extracted concepts and terms that are shared; and

a placement module to place the set of the stored clusters into a grouping, comprising;

an anchor point selector submodule to choose one of the selected clusters and to determine an anchor point on the chosen cluster that is located on an open edge of the chosen cluster along a vector defined from a center of the chosen cluster, wherein the vector intersects the anchor point; and

a cluster placement submodule to place a center of a further selected cluster outside of the anchor point on the vector and to limit overlap of the chosen cluster and the further selected cluster; and

an arrangement submodule to arrange one or more of the remaining selected clusters into an arrangement of clusters that each have a center originating outside of the anchor point and on the vector; and

a display and visualization module to display the grouping via a display.

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

a sort module to sort the selected clusters in the set of the stored clusters by cluster size.

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

an angle submodule to define the vector at a normalized angle.

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

a rendering module to render each selected cluster as a circle having an independent radius.

5. A system according to claim 4, wherein each circle has a volume dependent on a number of concepts contained in the selected cluster.

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

a rendering module to render each selected cluster as a convex volume, wherein each convex shape represents visualized data for a semantic concept space.

7. A system according to claim 1, wherein the placement module determines a further anchor point located on another open edge of the chosen cluster where a center of a further selected cluster is placed outside the further anchor point on a further vector and limits overlap of the chosen cluster and the further selected cluster, further comprising:

a grafting submodule arranging one or more of the remaining selected clusters into an additional arrangement of clusters that each have a center originating outside of the further anchor point and on the further vector.

8. A system according to claim 1, wherein the common theme is defined by selecting the shared extracted terms to have common semantic meanings.

9. A system according to claim 1, wherein at least one additional set of the stored clusters are selected with each selected additional cluster sharing a further common theme comprising one or more of the extracted terms that are shared, wherein the further common theme is different than the common theme;

and the at least one additional set of the stored clusters is placed into the grouping.

10. A system according to claim 1, wherein at least one additional cluster is selected comprising the extracted terms that are unique from each other cluster;

and the at least one additional cluster is placed into the grouping.

11. A method for generating a two-dimensional spatial arrangement of a cluster rendering, comprising:

storing clusters in a storage to represent concepts and terms extracted from a set of documents;

selecting a set of the clusters with each selected cluster sharing a common theme comprising one or more of the extracted concepts and terms that are shared; and

placing the set of the stored clusters into a grouping, comprising;

choosing one of the selected clusters and determining an anchor point on the chosen cluster that is located on an open edge of the chosen cluster along a vector defined from a center of the chosen cluster, wherein the vector intersects the anchor point; and

placing a center of a further selected cluster outside of the anchor point on the vector and limiting overlap of the chosen cluster and the further selected cluster; and

arranging one or more of the remaining selected clusters into an arrangement of clusters that each have a center originating outside of the anchor point and on the vector; and

displaying the grouping via a display.

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

sorting the selected clusters in the set of the stored clusters by cluster size.

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

defining the vector at a normalized angle.

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

rendering each selected cluster as a circle having an independent radius.

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

calculating a volume for each circle dependent on a number of concepts contained in the selected cluster.

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

rendering each cluster as a convex volume, wherein each convex shape represents visualized data for a semantic concept space.

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

determining a further anchor point located on another open edge of the chosen cluster where a center of a further selected cluster is placed outside the further anchor point on a further vector and limiting overlap of the chosen cluster and the further selected cluster; and

arranging one or more of the remaining selected clusters into an additional arrangement of clusters that each have a center originating outside of the further anchor point and on the further vector.

18. A computer-readable storage medium storing code for causing a computer to perform the method according to claim 11.

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

defining the common theme by selecting the shared extracted terms to have common semantic meanings.

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

selecting at least one additional set of the stored clusters with each selected additional cluster sharing a further common theme comprising one or more of the extracted terms that are shared, wherein the further common theme is different than the common theme; and

placing the at least one additional set of the stored clusters into the grouping.

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

selecting at least one additional cluster comprising the extracted terms that are unique from each other cluster; and

placing the at least one additional cluster into the grouping.

22. A system for arranging concept clusters in thematic relationship in a two-dimensional visual display area, comprising:

a stored theme to logically represent one or more concepts based on terms extracted from a document set;

a plurality of clusters selected to represent a multi-dimensional visualization space stored as clusters in a storage, wherein each selected cluster comprises at least one of the concepts in one such theme that is in common with the other selected clusters; and

a placement module to place the clusters into a grouping, comprising;

a listing submodule to combine in order each ungrouped cluster from the selected clusters for the shared common theme into a list of placeable clusters;

a grouping submodule to add each placeable clusters list into the grouping with one or more other placeable clusters lists, wherein the clusters in the other placeable clusters lists each comprise at least one concept in the shared common theme;

an anchor submodule to choose a selected cluster and to determine an anchor point on the chosen cluster that is located on an open edge of the chosen cluster along a vector defined from a center of the chosen cluster, wherein the vector intersects the anchor point; and

a cluster placement submodule to place a center of a further selected cluster outside of the anchor point on the vector and to limit overlap of the chosen cluster and the further selected cluster; and

a grafting submodule to place the center of a selected cluster and to graft the clusters in the remaining placeable clusters lists in the grouping outside the anchor point and along the vector; and

a display and visualization module to display the clusters via a display.

23. A system according to claim 22, further comprising:

a sort module sorting the clusters in each placeable clusters list in sequence.

24. A system according to claim 23, wherein the sequence comprises a number of documents containing the one or more logically represented concepts.

25. A system according to claim 23, wherein the sequence comprises one of ascending and descending order.

26. A system according to claim 22, wherein each cluster is formed as one of a circular and non-circular convex volume.

27. A system according to claim 22, wherein the vector is defined at normalized angles.

28. A system according to claim 22, wherein the shared common theme contains concepts within a pre-specified range of variance.

29. A system according to claim 22, wherein at least one additional plurality of the clusters is selected, wherein each selected additional cluster comprises one or more of the extracted terms that is in common with the other selected clusters in a further common theme that is different than the shared common theme;

and the at least one additional plurality of the clusters is placed into the grouping.

30. A system according to claim 22, wherein at least one additional cluster is selected that comprises the extracted terms that are unique from each other cluster;

and the at least one additional cluster is placed into the grouping.

31. A method for arranging concept clusters in thematic relationship in a two-dimensional visual display area, comprising:

logically representing one or more concepts based on terms extracted from a document set as a theme;

selecting clusters representing a multi-dimensional visualization space stored as clusters in a storage, wherein each selected cluster comprises at least one of the concepts in one such theme that is in common with the other selected clusters; and

placing the clusters into a grouping, comprising;

combining in order each ungrouped cluster from the selected clusters for the shared common theme into a list of placeable clusters;

adding each placeable clusters list into the grouping with one or more other placeable clusters lists, wherein the clusters in the other placeable clusters lists each comprise at least one concept in the shared common theme;

choosing a selected cluster and determining an anchor point on the chosen cluster that is located on an open edge of the chosen cluster along a vector defined from a center of the chosen cluster, wherein the vector intersects the anchor point; and

placing a center of a further selected cluster outside of the anchor point on the vector and limiting overlap of the chosen cluster and the further selected cluster; and

placing the center of a selected cluster and grafting the clusters in the remaining placeable clusters lists in the grouping outside the anchor point along the vector; and

displaying the grouping via a display.

32. A method according to claim 31, further comprising:

sorting the clusters in each placeable clusters list in sequence.

33. A method according to claim 32, wherein the sequence comprises a number of documents containing the one or more logically represented concepts.

34. A method according to claim 32, wherein the sequence comprises one of ascending and descending order.

35. A method according to claim 31, further comprising:

forming each cluster as one of a circular and non-circular convex volume.

36. A method according to claim 31, further comprising:

defining the vector at normalized angles.

37. A method according to claim 31, wherein the shared common theme contains concepts within a pre-specified range of variance.

38. A computer-readable storage medium storing code for causing a computer to perform the method according to claim 31.

39. A method according to claim 31, further comprising:

selecting additional clusters, wherein each selected additional cluster comprises one or more of the extracted terms that is in common with the other selected clusters in a further common theme that is different than the shared common theme; and

placing the additional clusters into the grouping.

40. A method according to claim 31, further comprising:

selecting at least one additional cluster comprising the extracted terms that are unique from each other cluster; and

placing the at least one additional cluster into the grouping.