Three-dimensional display of document set

• US 7,113,958 B1
• Filed: 06/24/2003
• Issued: 09/26/2006
• Est. Priority Date: 08/12/1996
• Status: Expired due to Fees

• Current Assignee: Battelle Memorial Institute
• Original Assignee: Battelle Memorial Institute
• Inventors: Schur, Anne, Thomas, James J., Pottier, Marc C., Lantrip, David B., Pennock, Kelly A., Wise, James A.
• Primary Examiner(s): MIZRAHI, DIANE D
• Application Number:
  US10/602,802
• Time in Patent Office: 1,190 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206, 382/305, 706/46
• US Class Current: 1/1
• CPC Class Codes: G06F 16/34 Browsing; Visualisation therefor
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method for spatializing text content for enhanced visual browsing and analysis. The invention is applied to large text document corpora such as digital libraries, regulations and procedures, archived reports, and the like. The text content from these sources may e transformed to a spatial representation that preserves informational characteristics from the documents. The three-dimensional representation may then be visually browsed and analyzed in ways that avoid language processing and that reduce the analysts'"'"' effort.

Claims

1. A computer implemented method of visually presenting information for human use, comprising the steps of:

(a) receiving a high dimensional vector representing information associated with at least one object;

(b) defining a display space having a small number of display dimensions, less than a dimensionality of said high dimensional vector;

(c) projecting, into said defined display space, a dispersed set of points, each point representing a dimension of said high dimensional vector; and

(d) projecting, into said defined display space, a point representing an object, wherein spatial relationships between the projected point representing an object and a projected point representing another object or a dimension of the high dimensional vector are optimized to represent a relatedness thereof.

2. The computer implemented method according to claim 1, wherein each dimension of said high dimensional vector represents a semantic theme.

3. The computer implemented method according to claim 1, wherein said display space comprises a three-dimensional image.

4. The computer implemented method according to claim 1, wherein said projecting step is repeated to project a plurality of points representing objects.

5. The computer implemented method according to claim 4, wherein said projecting of said dispersed set of points is optimized with respect to computational complexity and an associated error of said projection of said point representing an object.

6. The computer implemented method according to claim 4, wherein a distance metric is calculated in said high dimensional space between pairs of objects, and said projecting into said defined display space seeks to preserve said distance between pairs of objects in said display space.

7. The computer implemented method according to claim 4, wherein a distance metric is calculated in said high dimensional space between an object and said dispersed set of points, and said projecting into said defined display space seeks to preserve said distance between said object and each of said dispersed set of points in said display space.

8. The computer implemented method according to claim 4, further comprising the step of clustering a group of objects with an associated one of the dispersed set of points, determining a quantitative relationship of each of the objects in a cluster to the dimension of the high dimensional vector represented by the one of the dispersed set of points.

9. The computer implemented method according to claim 1, wherein said projecting step is repeated to project at least three thousand points representing objects.

10. The computer implemented method according to claim 1, wherein each object is a natural language document.

11. The computer implemented method according to claim 1, wherein an external weighting function is applied to control a respective distance between an object and at least one of said dispersed set of points.

12. The computer implemented method according to claim 1, wherein said high dimensional vector is derived from a semantic analysis of a document, each dimension of said high dimensional vector representing an associated gisting term or topic.

13. The computer implemented method according to claim 1, further comprising the step of producing a partition set on the plurality of objects, said partition set resulting in a cluster centroid for each of the objects, by applying a clustering algorithm with primary emphasis on k-means and complete linkage hierarchical clustering to create a cluster centroid.

14. The computer implemented method according to claim 13, wherein said step of creating said cluster centroid comprises the steps of:

(i) selecting a number of seeds;

(ii) placing said seeds in hyperspace by sampling regions to ensure a specified distribution of seeds;

(iii) identifying non-overlapping hyperspheres for each cluster and assigning each document to said each cluster based on which hypersphere said document is located;

(iv) calculating a centroid coordinate, representing the center of the mass for each cluster; and

(v) repeating steps (iii) and (iv) until centroid movement is less than a specified threshold.

15. The computer implemented method according to claim 1, wherein each of said dispersed set of points represents a cluster centroid, said projecting said dispersed set of points comprising the steps of:

(i) applying a Multi-dimensional Scaling Algorithm to cluster centroid coordinates in hyperspace;

(ii) producing a vector for each object with distance measures from said object to each cluster centroid; and

(iii) constructing an operator matrix and multiplying said matrix by said vector to produce two-dimensional coordinates for each object.

16. The computer implemented method according to claim 1, wherein each of said dispersed set of points represents a cluster centroid, said projecting said dispersed set of points comprising the steps of:

(i) applying an Anchored Least Stress Algorithm to cluster centroid coordinates in hyperspace;

(ii) producing a vector for each object document with distance measures from said object to each cluster centroid; and

(iii) constructing an operator matrix and multiplying said matrix by said vector to produce two-dimensional coordinates for each object.

17. The computer implemented method according to claim 1, wherein said optimized spatial relationships are optimized with respect to computational resource consumption.

18. The computer implemented method according to claim 1, further comprising the steps of receiving a natural language query defining said at least one object;

and projecting an object representing said natural language query into said display space.

19. A computer readable storage medium storing program instructions for programming a general purpose computer to perform a method comprising the steps of:

(a) receiving a high dimensional vector representing information associated with at least one object;

(b) defining a display space having a small number of display dimensions, less than a dimensionality of said high dimensional vector;

(c) projecting, into said defined display space, a dispersed set of points, each point representing a dimension of said high dimensional vector; and

(d) projecting, into said defined display space, a point representing an object, wherein spatial relationships between the projected point representing an object and a projected point representing another object or a dimension of the high dimensional vector are optimized to represent a relatedness thereof.

20. The computer readable storage medium storing program instructions according to claim 19, said performed method further comprising the step of receiving a natural language query defining said at least one object.

21. An apparatus for visually presenting information for human use, comprising:

(a) an input adapted for receiving a high dimensional vector representing information associated with at least one object;

(b) at least one processor, adapted for;

(i) defining a display space having a small number of display dimensions, less than a dimensionality of said high dimensional vector;

(ii) projecting, into said defined display space, a dispersed set of points, each point representing a dimension of said high dimensional vector; and

(iii) projecting, into said defined display space, a point representing an object, wherein spatial relationships between the projected point representing an object and a projected point representing another object or a dimension of the high dimensional vector are optimized to represent a relatedness thereof; and

(c) an output, adapted for transmitting a representation of the display space.