Feature diffusion across hyperlinks

• US 6,125,361 A
• Filed: 04/10/1998
• Issued: 09/26/2000
• Est. Priority Date: 04/10/1998
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Dom, Byron Edward, Chakrabarti, Soumen
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Mizrahi, Diane D.
• Application Number:
  US09/058,635
• Time in Patent Office: 900 Days
• Field of Search: 707/1, 707/3, 707/5, 707/4, 707/6, 707/7, 709/217, 709/218
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A system and method for ranking wide area computer network (e.g., Web) pages by popularity in response to a query. Further, using a query and the response thereto from a search engine, the system and method finds additional key words that might be good extended search terms, essentially generating a local thesaurus on the fly at query time.

Claims

1. A computer including a data storage device including a computer usable medium having computer usable code means for ranking documents in a set of documents in response to a query, the computer usable code means having:

computer readable code means for identifying a reference to a second document in a first document;

computer readable code means for receiving a lexical distance, the lexical distance defining a number of document terms;

computer readable code means for receiving a query including one or more query terms; and

computer readable code means for determining a number of times at least one of the query terms is present in the first document within the lexical distance of the reference to the second document, for ranking the documents based thereon.

2. The computer of claim 1, wherein the documents are accessible via a wide area computer network, and the reference includes a uniform resource listing (URL).

3. The computer of claim 2, wherein the lexical distance is established based on the query.

4. The computer of claim 2, further comprising computer readable code means for ranking multiple documents based on respective numbers of times query terms are present within lexical distances of references in the documents.

5. The computer of claim 1, further comprising:

computer readable code means for receiving a set "U" of documents;

computer readable code means for, for at least one test document "u" in the set "U", defining as neighbor documents "N(u)" documents in the set "U" that include at least one reference to the test document "u";

computer readable code means for determining, for at least one document term in at least one neighbor document "N(u)", whether the at least one document term is within a predetermined distance of a reference in the neighbor document "N(u)" to the test document "u"; and

computer readable code means for outputting a signal in response to the means for determining whether the at least one document term is within a predetermined distance of a reference.

6. The computer of claim 5, wherein the means for outputting increments a counter associated with the at least one document term when the at least one document term is within a predetermined distance of a reference to the test document "u".

7. The computer of claim 2, further comprising:

computer readable code means for receiving a set "U" of documents in response to a query including one or more query terms, each document containing one or more document terms; and

computer readable code means for defining a correlation between at least a first document and at least one document term when both the document term and a reference to the first document are within a predetermined distance of a query term in the at least one of the documents.

8. The computer of claim 7, wherein the correlation is associated with a weight, and the weight is based on the number of times the document term and a reference to the first document are within a predetermined distance of a query term in the set "U" of documents.

9. A computer program device comprising:

a computer program storage device readable by a digital processing apparatus; and

a program means on the program storage device and including instructions executable by the digital processing apparatus for performing method steps for finding key words in a set of documents, the method steps comprising;

receiving the set of documents;

determining referring documents and referred-to documents in the set of documents, the referring documents being documents in the set containing references to referred-to documents;

for each document term in a referring document, determining the number of times the document term appears within a predetermined distance of a reference to a referred-to document; and

ranking at least some of the document terms in the documents based on the respective number of times.

10. The computer program device of claim 9, wherein the method steps further comprise incrementing a respective counter each time a document term appears within a predetermined distance of a reference to a referred-to document.

11. The computer program device of claim 9, wherein the method steps further comprise:

receiving a set "U" of documents in response to a query including one or more query terms; and

defining a correlation between at least a first document and at least one document term when both the document term and a reference to the first document are within a predetermined distance of a query term.

12. The computer program device of claim 11, wherein the correlation is associated with a weight, and the weight is based on the number of times the document term and a reference to the first document are within a predetermined distance of a query term in the set "U" of documents.

13. The computer program device of claim 9, wherein the method steps further comprise:

receiving a lexical distance, the lexical distance defining a number of document terms;

receiving a query including one or more query terms; and

determining a number of times at least one of the query terms is present in the first document within the lexical distance of the reference to the second document, for ranking the documents based thereon.

14. The computer program device of claim 13, wherein the documents are accessible via a wide area computer network, and the reference includes a uniform resource listing (URL).

15. The computer program device of claim 14, wherein the lexical distance is established based on the query.

16. The computer program device of claim 14, wherein the method steps further comprise ranking multiple documents based on respective numbers of times query terms are present within lexical distances of references in the documents.

17. A computer-implemented method for finding associations in computer-stored documents between document terms and query topics represented by one or more query terms, the documents having respective references to referred-to documents, the method comprising the steps of:

receiving at least a list of documents in response to the query terms; and

when a document term and a reference to a referred-to document are both found in a document within a predetermined distance of a query term, outputting a signal representative of an association between the document term and the query topic.

18. The computer-implemented method of claim 17, wherein the outputting step includes:

constructing a bipartite graph having vertices, the vertices representing the documents received in the receiving step; and

for at least some documents (u), and for at least some document terms (t) in each document (u), incrementing a weight of an edge (t, u) in the bipartite graph when the document term (t) and a reference to the document (u) are both found within a predetermined distance of a query term, the edge (t, u) representing the document (u) and document term (t).

19. The computer-implemented method of claim 17, further comprising the steps of:

determining referring documents and referred-to documents in the list of documents, the referring documents being documents in the list containing references to referred-to documents;

for each document term in a referring document, determining the number of times the document term appears within a predetermined distance of a reference to a referred-to document; and

ranking at least some of the document terms in the documents based on the respective number of times.

20. The computer-implemented method of claim 17, further comprising the steps of:

receiving a lexical distance, the lexical distance defining a number of document terms;

determining a number of times at least one of the query terms is present in a first document within the lexical distance of a reference to the second document, for ranking the documents based thereon.

21. The computer-implemented method of claim 20, wherein the documents are accessible via a wide area computer network, and the reference to the second document includes a uniform resource listing (URL).

22. The computer-implemented method of claim 20, wherein the lexical distance is established based on the query terms.

23. The computer-implemented method of claim 20, further comprising the step of ranking multiple documents based on respective numbers of times query terms are present within lexical distances of references in the documents.

24. A computer including a data storage device including a computer usable medium having computer usable code means for finding associations in computer-stored documents between document terms and query topics represented by one or more query terms, the documents having respective references to referred-to documents, the computer usable code means having:

computer readable code means for receiving at least a list of documents in response to the query terms; and

computer readable code means for outputting, when a document term and a reference to a referred-to document are both found in a document within a predetermined distance of a query term, a signal representative of an association between the document term and the query topic.

25. The computer of claim 24, wherein the means for outputting includes:

computer readable code means for constructing a bipartite graph having vertices, the vertices representing the documents received in the receiving step;

computer readable code means for incrementing, for at least some documents (u), and for at least some document terms (t) in each document (u), a weight of an edge (t, u) in the bipartite graph when the document term (t) and a reference to the document (u) are both found within a predetermined distance of a query term, the edge (t, u) representing the document (u) and document term (t).

26. The computer of claim 25, further comprising:

computer readable code means for determining referring documents and referred-to documents in the list of documents, the referring documents being documents in the list containing references to referred-to documents;

computer readable code means for determining, for each document term in a referring document, the number of times the document term appears within a predetermined distance of a reference to a referred-to document; and

computer readable code means for ranking at least some of the document terms in the documents based on the respective number of times.

27. The computer of claim 26, further comprising:

computer readable code means for receiving a lexical distance, the lexical distance defining a number of document terms; and

computer readable code means for determining a number of times at least one of the query terms is present in a first document within the lexical distance of a reference to the second document, for ranking the documents based thereon.

28. The computer of claim 27, wherein the documents are accessible via a wide area computer network, and the reference to the second document includes a uniform resource listing (URL).

29. A computer including a data storage device including a computer usable medium having computer usable code means for finding key words in a set of documents, the computer usable code means having:

computer readable code means for receiving the set of documents;

computer readable code means for determining referring documents and referred-to documents in the set of documents, the referring documents being documents in the set containing references to referred-to documents;

computer readable code means for determining, for each document term in a referring document, the number of times the document term appears within a predetermined distance of a reference to a referred-to document; and

computer readable code means for ranking at least some of the document terms in the documents based on the respective number of times.

30. The computer of claim 29, further comprising computer readable code means for incrementing a respective counter each time a document term appears within a predetermined distance of a reference to a referred-to document.

31. The computer of claim 30, further comprising:

computer readable code means for receiving a set "U" of documents in response to a query including one or more query terms; and

computer readable code means for defining a correlation between at least a first document and at least one document term when both the document term and a reference to the first document are within a predetermined distance of a query term.

32. The computer of claim 31, wherein the correlation is associated with a weight, and the weight is based on the number of times the document term and a reference to the first document are within a predetermined distance of a query term in the set "U" of documents.

33. The computer of claim 32, further comprising:

computer readable code means for receiving a lexical distance, the lexical distance defining a number of document terms;

computer readable code means for receiving a query including one or more query terms; and

computer readable code means for determining a number of times at least one of the query terms is present in the first document within the lexical distance of the reference to the second document, for ranking the documents based thereon.

34. The computer of claim 33, wherein the documents are accessible via a wide area computer network, and the reference includes a uniform resource listing (URL).

35. A computer including a data storage device including a computer usable medium having computer usable code means for ranking documents in a set of documents in response to a query, the computer usable code means having

computer readable code means for receiving a set "U" of documents;

computer readable code means for, for at least one test document "u" in the set "U", defining as neighbor documents "N(u)" documents in the set "U" that include at least one reference to the test document "u";

computer readable code means for determining, for at least one document term in at least one neighbor document "N(u)", whether the at least one document term is within a predetermined distance of a reference in the neighbor document "N(u)" to the test document "u"; and

computer readable code means for outputting a signal in response to the means for determining whether the at least one document term is within a predetermined distance of a reference.

36. The computer of claim 35, wherein the means for outputting increments a counter associated with the at least one document term when the at least one document term is within a predetermined distance of a reference to the test document "u".