System and method for automatic clustering, sub-clustering and cluster hierarchization of search results in cross-referenced databases using articulation nodes

• US 20050060287A1
• Filed: 05/14/2004
• Published: 03/17/2005
• Est. Priority Date: 05/16/2003
• Status: Abandoned Application

• Current Assignee: Robert Todd Chesler, Ziv Z. Hellman
• Original Assignee: Robert Todd Chesler, Ziv Z. Hellman
• Inventors: Hellman, Ziv Z., Chesler, Robert Todd
• Application Number:
  US10/845,097
• Publication Number:
  US 20050060287A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates

Abstract

Within the context of a cross-referenced data-base, an initial “base-set” of results to a query is generated using any conventional search engine tool. The base-set is then expanded by adding to it entries referencing entries in the original set or referenced by those entries, in a possibly iterative manner. The resulting collection of entries and references is represented as a mathematical graph or network, amendable to graph theoretic analysis. Connected components within the graph form top-level clusters, and articulation nodes within these clusters are calculated. These articulation nodes serve as both navigational “gateways” and anchors for sub-clusters. Sub-clusters, consisting of the transitive descendants of the articulation nodes, are associated with each articulation node. The articulation nodes themselves then form a graph, which is analyzed further for prominence, and a hierarchy of articulation nodes is calculated. The resulting hierarchy consisting of the top-level clusters and the sub-clusters associated with the articulation nodes is then presented visually to users in a manner enabling them to easily navigate through the space of expanded search results.

Claims

1. A method for clustering and sub-clustering documents and/or other types of objects listed as entries in a cross-referenced database or plurality of databases, along with a hierarchization of the resultant clusters and sub-clusters, the method comprising the steps of:

a) entering one or more first entries in the database, said first entries referred to as an original base set;

b) determining in the database second entries which reference to each of said first entries;

c) calculating a link number defined as the number of second entries referencing each of said first entries;

d) utilizing a connectivity index produced by a cross-referenced database for each of said first entries to create an augmented base set of said first entries;

e) expanding said augmented base set by adding to it all entries which reference and/or are referenced by each and every entry in said original base set;

f) iteratively repeating step e), in either a forward direction or a backward direction;

g) defining clusters and sub-clusters of the expanded set of entries;

h) creating a hierarchy of the said clusters and said sub-clusters;

i) presenting users, in a visual manner, the defined clusters and sub-cluster hierarchy; and

j) enabling users to store, in a persistent manner in a computer memory, any of the said clusters and/or said sub-clusters, and the visualization of their interconnections.

2. The method in accordance with claim 1, further including the step of providing the users with a summary or name for each of said clusters and sub-clusters, allowing the user to navigate between said clusters at and said sub-clusters.

3. The method for generating the clusters and sub-clusters, in accordance with claim 1, including the steps of:

a) representing said expanded set of entries as a mathematical non-directed graph or network within the computer memory;

b) calculating the connected components of said graph;

c) calculating within each of said connected components, articulation nodes bridging each of said connected components;

d) defining each connected pairs of connected components so calculated as a basic cluster of entries;

e) associating with each of said articulation nodes its respective set of transitive descendants, said set of transitive descendants being defined as a basic sub-cluster of the cluster of which said articulation node is a member;

f) assigning a name to each of said clusters and said sub-clusters by making use of a weighted averaging formula summarizing keywords, titles, and/or other textual elements associated with each entry within said clusters or said sub-cluster;

g) creating a representation of a reduced mathematical directed graph, said articulation nodes and directed arcs defined between said nodes defined whenever one articulation node is a transitive ancestor of another articulation node;

h) calculating the relative prominence of said articulation nodes associated with each said connected components, utilizing eigenvectors of incidence matrices;

i) traversing said reduced graphs beginning with the most prominent articulation nodes in each connected component;

j) translating the hierarchy of said articulation nodes in each of said connected components, using the association of a sub-cluster to each of said articulation nodes; and

k) presenting the full hierarchy of said clusters and said sub-clusters to the users.

4. The method in accordance with claim 3, further including the step of presenting a visual display to the users in hyper text markup language.

5. The method in accordance with claim 3, further including the step of presenting a three-dimensional visual display to the users in three dimensional virtual reality markup language.

6. The method in accordance with claim 5, wherein the step of presenting said three-dimensional display is accomplished using virtual realize markup language.

9. The method in accordance with claim 1, further including the step of utilizing a browser plug-in for clustering and sub-clustering the documents.

10. The method in accordance with claim 3, further including the step of utilizing a browser plug-in for clustering and sub-clustering the documents.

11. The method in accordance with claim 1, further including the steps of:

maintaining said clusters and sub-clusters in a memory; and

utilizing said clusters and said sub-clusters in said memory as a domain to be used in searches of similar documents.

12. The method in accordance with claim 3, further including the steps of:

maintaining said clusters and sub-clusters in a memory; and

utilizing said clusters and said sub-clusters in said memory as a domain to be used in searches of similar documents.

7. The method in accordance with claim 7, wherein said augmented base set is a set of web pages.

13. A system for clustering and sub-clustering documents and/or other types of objects listed as entries in a cross-referenced database, comprising:

a device for entering search entries in a search engine processor;

a device for calculating links between said search entries;

a device for mathematically representing an expanding set of said entries as a non-directed graph;

a device for calculating connection compounds of said graph;

a device for calculating articulation nodes bridging each of said connected components;

a device for defining transitive descendants of said articulation nodes, defined as a basic sub-cluster;

a device for creating a reduced mathematical directed graph utilizing said non-directed graph and said articulation nodes;

a prominence calculator used to order each of said articulation nodes in decreasing size based upon said connected components; and

a display device of displaying the output of said search entries.

14. The system in accordance with claim 13, wherein said display device displays a three-dimensional rendition of said sub-classes and said articulated nodes.

15. The system in accordance with claim 13, further including a hierarchy calculator for calculating the hierarchy of said articulation nodes.

16. The system in accordance with claim 14, further including a hierarchy calculator for calculating the hierarchy of said articulation nodes.