Clustering hypertext with applications to WEB searching

• US 7,233,943 B2
• Filed: 09/11/2003
• Issued: 06/19/2007
• 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): Gaffin; Jeffrey
• Assistant Examiner(s): Veillard; Jacques
• Application Number:
  US10/660,242
• Publication Number:
  US 20040049503A1
• Time in Patent Office: 1,377 Days
• Field of Search: 707/2, 707/3, 707/5, 707/6, 707/10, 707/104.1, 707/4, 715/513, 715/501.1, 715/532
• 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 of searching a database of documents, wherein the method includes performing a search of the database using a query to produce query result documents; constructing a word dictionary of words within the query result documents; constructing an out-link dictionary of documents within the database that are pointed to by the query result documents; adding the query result documents to the out-link dictionary; constructing an in-link dictionary of documents within the database that point to the query result documents; and adding the query result documents to the in-link dictionary.

Claims

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

performing a search of said database using a query to produce query result documents;

constructing a word dictionary of words within said query result documents;

constructing an out-link dictionary of documents within said database that are pointed to by said query result documents;

adding said query result documents to said out-link dictionary;

constructing an in-link dictionary of documents within said database that point to said query result documents; and

adding said query result documents to said in-link dictionary.

2. The method in claim 1, further comprising:

forming first vectors for words remaining in said word dictionary;

forming second vectors for documents remaining in said out-link dictionary;

forming third vectors for documents remaining in said in-link dictionary;

normalizing said first vectors, said second vectors, and said third vectors to create vector triplets for document remaining in said in-link dictionary and said out-link dictionary; and

clustering the said vector triplets into one of clusters, or classes and partitions.

3. The method in claim 2, wherein said clustering comprises a four toric k-means process comprising:

arbitrarily segregating the vector triplets into clusters;

for each cluster, computing a set of concept triplets describing said cluster;

re-segregating said vector triplets into a more coherent set of clusters by putting each vector triplet into a cluster corresponding to a concept triplet that is most similar to, a given vector triplet;

determining a coherence for each of said clusters based on a similarity of vector triplets within each of said clusters, and repeating the computing and re-segregating steps until coherence of the obtained clusters no longer significantly increases.

4. The method in claim 2, further comprising annotating and summarizing said clusters using nuggets of information, said nuggets including summary, breakthrough, review, keyword, citation, and reference.

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

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

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

8. The method in claim 4, wherein said keyword comprises a word in said word dictionary for said cluster that has the largest weight.

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

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

11. The method in claim 1, further comprising pruning function words from said word dictionary.

12. The method in claim 1, further comprising pruning documents from said out-link dictionary that are pointed to by fewer than a first predetermined number of said query result documents.

13. The method in claim 1, further comprising pruning documents from said in-link dictionary that point to fewer than a second predetermined number of said query result documents.

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

performing a search of said database using a query to produce query result documents;

constructing a word dictionary of words within said query result documents;

constructing an out-link dictionary of documents within said database that are pointed to by said query result documents;

adding said query result documents to said out-link dictionary;

constructing an in-link dictionary of documents within said database that point to said query result documents; and

adding said query result documents to said in-link dictionary.

15. The program storage device in claim 14, wherein said method further comprises:

forming first vectors for words remaining in said word dictionary;

forming second vectors for documents remaining in said out-link dictionary;

forming third vectors for documents remaining in said in-link dictionary;

normalizing said first vectors, said second vectors, and said third vectors to create vector triplets for document remaining in said in-link dictionary and said out-link dictionary; and

clustering the said vector triplets into one of clusters, or classes and partitions.

16. The program storage device in claim 15, wherein in said method, said clustering comprises a four toric k-means process comprising:

arbitrarily segregating the vector triplets into clusters;

for each cluster, computing a set of concept triplets describing said cluster;

re-segregating said vector triplets into a more coherent set of clusters by putting each vector triplet into a cluster corresponding to a concept triplet that is most similar to, a given vector triplet;

determining a coherence for each of said clusters based on a similarity of vector triplets within each of said clusters, and repeating the computing and re-segregating steps until coherence of the obtained clusters no longer significantly increases.

17. The program storage device in claim 15, wherein said method further comprises annotating and summarizing said clusters using nuggets of information, said nuggets including summary, breakthrough, review, keyword, citation, and reference.

18. The program storage device in claim 17, wherein said summary comprises a document in a cluster having a most typical in-link feature vector amongst all the documents in said cluster, wherein said breakthrough comprises a document in a cluster having a most typical in-link feature vector amongst all the documents in said cluster, wherein said review comprises a document in a cluster having a most typical out-link feature vector amongst all the documents in said cluster, wherein said keyword comprises a word in said word dictionary for said cluster that has the largest weight, wherein said citation comprises a document in a cluster representing a most typical in-link info said cluster, and wherein said reference comprises a document in a cluster representing a most typical out-link out of said cluster.

19. The program storage device in claim 14, wherein said method further comprises:

pruning function words from said word dictionary;

pruning documents from said out-link dictionary that are pointed to by fewer than a first predetermined number of said query result documents; and

pruning documents from said in-link dictionary that point to fewer than a second predetermined number of said query result documents.

20. A system for searching a database of documents, said system comprising:

means for performing a search of said database using a query to produce query result documents;

means for constructing a word dictionary of words within said query result documents;

means for constructing an out-link dictionary of documents within said database that are pointed to by said query result documents;

means for adding said query result documents to said out-link dictionary;

means for constructing an in-link dictionary of documents within said database that point to said query result documents; and

means for adding said query result documents to said in-link dictionary.