Clustering user interface

• US 5,790,121 A
• Filed: 09/06/1996
• Issued: 08/04/1998
• Est. Priority Date: 09/06/1996
• Status: Expired due to Term

• Current Assignee: PSCC Pacific LLC
• Original Assignee: Cole Coleman, Peter Sklar
• Inventors: Sklar, Peter, Coleman, Cole
• Primary Examiner(s): Bayerl, Raymond J.
• Assistant Examiner(s): Nguyen, Cao H.
• Application Number:
  US08/711,300
• Time in Patent Office: 697 Days
• Field of Search: 345/333, 345/334, 345/339, 345/348, 345/356, 345/357, 345/340, 345/762, 345/968
• US Class Current: 715/853
• CPC Class Codes: G06F 16/26 Visual data mining; Browsing structured data
• CPC Class Codes: Y10S 715/968 interface for database querying and retrieval

Abstract

A user is presented with a display map from which the user selects database records of interest. For the records which are in range of the display map'"'"'s limits, a cluster evaluator groups some of the records into clusters. On the display map, unclustered records are represented by item icons, while clusters are represented by cluster icons. If a user selects an item icon, the associated record is selected and a predetermined action is taken. If a cluster icon is selected, the display map is "zoomed in" to show greater detail around the cluster. Typically, a number of clustered records become unclustered records when the zooming occurs, because the clustering criteria is sharpened. The user can iteratively select clusters, resulting in greater and greater detail, until the user selects an item icon and the predetermined action is taken with that record.

Claims

1. A user interface generated by a digital computer for user selection from among a plurality of items wherein each of the plurality of items is referenced by a record in a database with at least one field in the record defining at least one coordinate for the item, the user interface comprising:

a display map wherein points on the display map are defined by at least one coordinate comparable with the at least one coordinate for an item selectable by the user;

at least one cluster on the display map, wherein a cluster represents a plurality of items all being within a threshold of a function of coordinate differences defined by the plurality of items represented;

at least one unclustered item icon, displayed on the display map at a location substantially corresponding to coordinates of the at least one unclustered item;

means for accepting user selection of a coordinate;

means for determining if the user selection is of the unclustered item, the cluster, or neither;

means for producing a more detailed map when the means for determining determines that the user selected a cluster; and

means for retrieving the record for the unclustered item when the unclustered item is selected.

2. A method of presenting a user with selections of items, wherein each item has a position associated with the item and the position is a location in an N-dimensional space, N being predetermined number greater than zero, the method comprising the steps of:

determining an initial display scale and initial display bounds;

determining which items have positions which are within the initial display bounds;

determining which of the items have positions which are within a clustering threshold of other positions and grouping such items into clusters;

displaying unclustered items on the display so as to identify the item by position and as an unclustered item;

displaying a cluster of clustered items so as to identify the cluster; and

accepting user input selections of either an unclustered item or a cluster.

3. The method of claim 2, further comprising the steps of:

when an unclustered item is selected, acting on that selection;

when a cluster is selected, narrowing the display bounds from the initial display bounds and lowering the clustering threshold until at least one item in the cluster becomes an unclustered item; and

repeating the step of narrowing and lowering until an unclustered item is selected.

4. The method of claim 2, wherein N=1 and the position of an item is a point on a line.

5. The method of claim 2, wherein N=2 and the position of an item is a point on a plane.

6. The method of claim 2, wherein N=3 and the position of an item is a point in a 3-space.

7. The method of claim 2, wherein N is greater than two and a projection onto a plane of clusters and unclustered items in an N-dimensional space is used to generate a two-dimensional display.

8. The method of claim 2, wherein the step of displaying a cluster is a step of generating a shape of a cluster to be displayed based on positions of items within the cluster.

9. The method of claim 8, wherein the shape of the cluster is a bounding rectangle enclosing each position of items within the cluster.

10. A method of presenting a user with selection of items, wherein each item has a position in a hierarchical structure, the method comprising the steps of:

determining an origin point in the hierarchical structure;

determining a weight for each of a plurality of links in the hierarchical structure;

setting a threshold distance;

clustering items in the hierarchical structure, wherein a cluster is a plurality of items whose path distance to another item in the cluster is less than the threshold, a path distance being a sum of the weights of the links traversed to reach either a common ancestor or to reach the other item which is clustered;

displaying unclustered items on the display so as to identify the unclustered items as unclustered items;

displaying a cluster of clustered items so as to identify the cluster; and

accepting user input selection of either an unclustered items or a cluster.

11. The method of claim 10, further comprising the steps of:

when an unclustered item is selected, acting on that selection;

when a cluster is selected, regenerating a display of clusters and unclustered items using the selected cluster as the initial point.

12. The method of claim 10, wherein the hierarchical structure is a directory structure.

13. The method of claim 10, wherein the hierarchical structure is a file structure of a file storage device.

14. The method of claim 10, wherein hierarchical structure represents abstract data.