Method and apparatus for measuring similarity among electronic documents

• US 6,990,628 B1
• Filed: 06/14/1999
• Issued: 01/24/2006
• Est. Priority Date: 06/14/1999
• Status: Expired due to Term

• Current Assignee: Excalibur IP, LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Zha, Hongyuan, Palmer, Michael E., Sun, Gordon G.
• Primary Examiner(s): BASHORE, WILLIAM L
• Application Number:
  US09/333,121
• Time in Patent Office: 2,416 Days
• Field of Search: 707/3, 707/6, 707/500, 707/501.1
• US Class Current: 715/234
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 40/194 Calculation of difference between files
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method and apparatus are provided for determining when electronic documents stored in a large collection of documents are similar to one another. A plurality of similarity information is derived from the documents. The similarity information may be based on a variety of factors, including hyperlinks in the documents, text similarity, user click-through information, similarity in the titles of the documents or their location identifiers, and patterns of user viewing. The similarity information is fed to a combination function that synthesizes the various measures of similarity information into combined similarity information. Using the combined similarity information, an objective function is iteratively maximized in order to yield a generalized similarity value that expresses the similarity of particular pairs of documents. In an embodiment, the generalized similarity value is used to determine the proper category, among a taxonomy of categories in an index, cache or search system, into which certain documents belong.

Claims

1. A computer implemented method of categorizing a plurality of new electronic documents into a set of categories, comprising the steps of:

establishing a plurality of training sets, wherein each training set is associated with a category and includes training documents that have been classified as belonging to said associated category;

determining how strongly each document of said plurality of documents corresponds to each of said plurality of categories by determining similarity between said each document and the training documents that belong to the training set of said category; and

wherein the step of determining similarity is performed using a matrix representing document similarity that is derived by combining two or more measures of document similarity.

2. A method as recited in claim 1, wherein the measures of document similarity include hyperlink similarity.

3. A method as recited in claim 2, in which two documents among the plurality of documents are considered similar to each other when there is a link from one to the other, or when the two documents link to, or are linked to by, a set of other associated documents.

4. A method as recited in claim 3, in which certain hyperlinks have greater or lesser similarity weight than other hyperlinks, based on other features of the links or their source or destination documents.

5. A method as recited in claim 1, wherein the measures of document similarity include a similarity of text of the documents.

6. A method as recited in claim 5, wherein two documents are considered similar based on a comparison of word vectors derived from the text of each of the two documents.

7. A method as recited in claim 5, wherein text similarity is determined in part based upon weight values assigned to words of the text, and wherein certain words have greater or lesser weight than other words.

8. A method as recited in claim 1, wherein the measures of document similarity include user click-through similarity.

9. A method as recited in claim 8, wherein two documents are considered similar based on user click-through similarity when the documents are associated with similar patterns of user click behavior, selected from among frequency of clicks, click context, duration of viewing, proximity in time to other clicks, or proximity in context to other clicks.

10. A method as recited in claim 1, wherein the measures of document similarity are derived from patterns detected in user viewing of the documents.

11. A method as recited in claim 10, wherein the user viewing information is monitored by a web caching system and stored in a log.

12. A method as recited in claim 10, wherein two documents are considered similar based on patterns of user viewing behavior, including frequency of viewing, viewing context, duration of viewing, proximity in time to other documents viewed by the same user, or similarity of patterns of viewing by all users.

13. A method as recited in claim 1, wherein the measures of document similarity include URL similarity.

14. A method as recited in claim 13, wherein two documents are considered similar if a URL of each document contains similar URL sub-components.

15. A method as recited in claim 1, wherein the measures of document similarity include multimedia similarity.

16. A method as recited in claim 15, wherein two documents are considered similar based on features derived from multimedia components linked to or contained by the documents.

17. A method as recited in claim 1, wherein the combination of two or more measures of document similarity is achieved by taking the union of each of a plurality of graphs, each graph describing one of the measures of document similarity, to compute a combined graph that describes the combined document similarity.

18. A method as recited in claim 1, wherein the combination of two or more measures of document similarity is achieved by taking the intersection of each of a plurality of graphs, each graph describing one of the measures of document similarity, to compute a combined graph that describes the combined document similarity.

19. A method as recited in claim 1, further comprising the step of extracting similarity information from the similarity matrix to obtain new documents supported by the set of training documents for each category.

20. A method as recited in claim 19, wherein the similarity information is obtained by optimizing an objective function.

21. A method as recited in claim 19, wherein the similarity information is obtained by only approximately optimizing an objective function.

22. A method as recited in claim 21, wherein approximately optimizing the objective function comprises repeated application of a growth transformation.

23. A method as recited in claim 19, further comprising the step of creating and storing a second matrix that represents an interim score for each document in each category.

24. A method as recited in claim 19, further comprising the steps of, periodically as the matrix is being computed, normalizing rows of the matrix by normalizing within each document, across all categories, whereby the score for one document in a particular category will depend on the scores for that document in all other categories.

25. A method as recited in claim 19, further comprising the steps of, periodically as the matrix is being computed, normalizing columns of the matrix by normalizing within each category, across all documents, whereby the score for one document in a particular category depends on the scores for all other documents in that category.

26. A method as recited in claim 1, in which the categories come from a manually defined taxonomy.

27. A method as recited in claim 1, wherein the categories are derived from logs of user queries.

28. A method as recited in claim 1, further comprising the steps of creating and storing a second matrix using columns representing documents and rows representing user sessions, and wherein values of elements of the second matrix represent interest in a document shown by a particular user in a particular session.

29. A method as recited in claim 1, further comprising the steps of creating and storing a matrix using columns representing user sessions and rows representing documents, and wherein values of elements of the second matrix represent interest in a document shown by a particular user in a particular session.

30. A method as recited in claim 28, wherein the element values are computed as a function of a time that a user has spent viewing a document associated with each element.

31. A method as recited in claim 28, further comprising the steps of creating and storing a second matrix representing a Similarity between pairs of documents i and j, wherein the second matrix is derived by comparing pairs of column vectors or row vectors, respectively i and j of the first matrix.

32. A method as recited in claim 28, further comprising the steps of creating and storing a second matrix representing a Similarity between pairs of documents i and j, by finding pairs of documents i and j which have high interest values for a particular user in a particular session or period of time.

33. The method recited in claim 1, further comprising the steps of:

identifying a category of a classification taxonomy of the hypertext system in which a first electronic document is presently classified; and

if a second electronic document is found to be highly Similar, storing information that classifies the second electronic document into the category.

34. A computer-readable recording medium carrying one or more sequences of instructions, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

establishing a plurality of training sets, wherein each training set is associated with a category and includes training documents that have been classified as belonging to said associated category;

determining how strongly each document of said plurality of documents corresponds to each of said plurality of categories by determining similarity between said each document and the documents that belong to the training set of said category; and

wherein the step of determining similarity is performed using a matrix representing document similarity that is derived by combining two or more measures of document similarity.