Clustering hypertext with applications to web searching

• US 6,684,205 B1
• Filed: 10/18/2000
• Issued: 01/27/2004
• Est. Priority Date: 10/18/2000
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Modha, Dharmendra Shantilal, Spangler, William Scott
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): Liang, Gwen
• Application Number:
  US09/690,854
• Time in Patent Office: 1,196 Days
• Field of Search: 707/3, 707/532, 707/513, 707/501.1, 707/10, 707/1, 715/501.1, 715/513
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 18/23213 with fixed number of clusters, e.g. K-means clustering
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A method and structure of searching a database containing hypertext documents comprising searching the database using a query to produce a set of hypertext documents; and geometrically clustering the set of hypertext documents into various clusters using a toric k-means similarity measure such that documents within each cluster are similar to each other, wherein the clustering has a linear-time complexity in producing the set of hypertext documents, wherein the similarity measure comprises a weighted sum of maximized individual components of the set of hypertext documents, and wherein the clustering is based upon words contained in each hypertext document, out-links from each hypertext document, and in-links to each hypertext document.

Claims

1. A method of searching a database containing hypertext documents, said method comprising:

searching said database using a query to produce a set of hypertext documents;

geometrically clustering said set of hypertext documents into various clusters using a similarity measure such that documents within each cluster are similar to each other,

wherein said clustering has a linear-time complexity in producing said set of hypertext documents,

wherein said similarity measure comprises a weighted sum of maximized individual components of said set of hypertext documents,

wherein said clustering is based upon words contained in each hypertext document, out-links from each hypertext document, and in-links to each hypertext document; and

eliminating said hypertext documents if said words contained in said hypertext documents appear in fewer than two documents, said out-links contained in said hypertext documents are pointed to by fewer than two documents, and said in-links contained in said hypertext documents are pointed to by fewer than two documents.

2. The method in claim 1, wherein said set of hypertext documents comprises a collection or unstructured, unlabeled documents and said clustering organizes said set of hypertext documents into labeled categories that are discriminated and disambiguated from each other.

3. The method in claim 1, wherein said clustering includes determining a relative importance of said words, said out-links, and said in-links in an adaptive, data-driven process.

4. The method in claim 1, further comprising annotating each cluster using information nuggets.

5. The method in claim 4, wherein said information nuggets include nuggets relating to summary, breakthrough, review, keywords, citations, and references.

6. The method in claim 5, wherein said summary and said keywords are derived from said words, said review and said references are derived from said out-links, and said breakthrough and said citations are derived from said in-links.

7. The method in claim 5, wherein said summary comprises a document in a cluster having a most typical in-link feature vector amongst the documents in said cluster.

8. The method in claim 5, wherein said breakthrough comprises a document in a cluster having a most typical in-link feature vector amongst all documents in said cluster.

9. The method in claim 5, wherein said review comprises a document in a cluster having a most typical out-link feature vector amongst the documents in said cluster.

10. The method in claim 5, wherein said keywords comprise a word in a word dictionary for said cluster that has a largest weight.

11. The method in claim 5, wherein said citation comprises a document in a cluster representing a most typical in-link into said cluster.

12. The method in claim 5, wherein said reference comprises a document in a cluster representing a most typical out-link out of said cluster.

13. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform a method of searching a database containing hypertext documents, said method comprising:

searching said database using a query to produce a set of hypertext documents;

geometrically clustering said set of hypertext documents into various clusters using a similarity measure such that documents within each cluster are similar to each other,

wherein said clustering has a linear-time complexity in producing said set of hypertext documents,

wherein said similarity measure comprises a weighted sum of maximized individual components of said set of hypertext documents,

wherein said clustering is based upon words contained in each hypertext document, out-links from each hypertext document, and in-links to each hypertext document; and

eliminating said hypertext documents if said words contained in said hypertext documents appear in fewer than two documents, said out-links contained in said hypertext documents are pointed to by fewer than two documents, and said in-links contained in said hypertext documents are pointed to by fewer than two documents.

14. A program storage device as in claim 13, wherein said set of hypertext documents comprises a collection of unstructured, unlabeled documents and said clustering organizes said set of hypertext documents into labeled categories that are discriminated and disambiguated from each other.

15. A program storage device as in claim 13, wherein said clustering includes determining a relative importance of said words, said out-links, and said in-links in an adaptive, data-driven process.

16. A program storage device as in claim 13, further comprising annotating each cluster using information nuggets.

17. A program storage device as in claim 16, wherein said information nuggets include nuggets relating to summary, breakthrough, review, keywords, citations, and reference.

18. A program storage device as in claim 16, wherein said summary and said keywords are derived from said words, said review and said references are derived from said out-links, and said breakthrough and said citations are derived from said in-links.

19. A program storage device as in claim 16, wherein said summary comprises a document in a cluster having a most typical in-link feature vector amongst the documents in said cluster.

20. A program storage device as in claim 16, wherein said breakthrough comprises a document in a cluster having a most typical in-link feature vector amongst the documents in said cluster.

21. A program storage device as in claim 17, wherein said review comprises a document in a cluster having a most typical out-link feature vector amongst the documents in said cluster.

22. A program storage device as in claim 17, wherein said keywords comprise a word in a word dictionary for said cluster that has a largest weight.

23. A program storage device as in claim 17, wherein said citation comprises a document in a cluster representing a most typical in-link into said cluster.

24. A program storage device as in claim 17, wherein said reference comprises a document in a cluster representing a most typical out-link out of said cluster.