System and method for quantitatively representing data objects in vector space

• US 6,922,699 B2
• Filed: 10/19/1999
• Issued: 07/26/2005
• Est. Priority Date: 01/26/1999
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Li, Jun, Chi, Ed H., Gargi, Ullas, Chen, Francine R., Pirolli, Peter L., Pitkow, James E., Schuetze, Hinrich
• Primary Examiner(s): Alam, Shahid
• Assistant Examiner(s): FLEURANTIN, JEAN B
• Application Number:
  US09/421,416
• Publication Number:
  US 20030074368A1
• Time in Patent Office: 2,107 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206, 709/203, 715/513, 715521-529, 715/531, 704 9- 10, 382/194, 382/191, 382168-190, 382/225, 382/317, 382/176, 382197-198
• US Class Current: 1/1
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 16/5846 using extracted text
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A system and method for browsing, retrieving, and recommending information from a collection uses multi-modal features of the documents in the collection, as well as an analysis of users'"'"' prior browsing and retrieval behavior. The system and method are premised on various disclosed methods for quantitatively representing documents in a document collection as vectors in multi-dimensional vector spaces, quantitatively determining similarity between documents, and clustering documents according to those similarities. The system and method also rely on methods for quantitatively representing users in a user population, quantitatively determining similarity between users, clustering users according to those similarities, and visually representing clusters of users by analogy to clusters of documents.

Claims

1. A method for quantitatively representing digital documents in a vector space, comprising the steps of:

identifying a first digital document to be processed from a plurality of digital documents;

extracting a first feature corresponding to the first document from the plurality of digital documents, the first feature comprising text surrounding an image included in the digital document, the text surrounding the image not being anchor text;

converting the first feature to a first vector; and

associating the first vector with the first digital document.

2. The method of claim 1 further comprising the steps of:

extracting a second feature corresponding to the digital document, the second feature comprising a first URL representing the first digital document;

converting the second feature to a second vector; and

associating the second vector with the first digital document.

3. The method of claim 2, wherein the step of converting the second feature comprises the sub-steps of:

identifying each unique word within the URLs representing all digital documents in the collection of digital documents; and

counting the occurrences of each unique word in the first URL;

creating a vector having a number of dimensions equal to the number of unique words in the URLs representing all digital documents in the collection of digital documents, and further having as each element a numeric value representative of the number of occurrences in the first URL of the corresponding word.

4. The method of claim 3, wherein the value representative of the number of occurrences in the first URL of the corresponding word is calculated as the token frequency weight of the corresponding word multiplied by the inverse context frequency weight of the corresponding word.

5. The method of claim 1 further comprising the steps of:

extracting a second feature corresponding to the first digital document, the second feature comprising inlinks in the collection of digital documents linking to the first document;

converting the second feature to a second vector; and

associating the second vector with the first digital document.

6. The method of claim 5, wherein the step of converting the second feature comprises the sub-steps of:

identifying each digital document having links within the collection of digital documents;

determining how many times each digital document having links points to the first digital document; and

creating the second vector having a number of dimensions equal to the number of digital documents having links in the collection of digital documents, and the second vector further having as each element a numeric value representative of the number of links in each corresponding digital document linking to the first digital document.

7. The method of claim 6, wherein the numeric value representative of the number of links in each corresponding digital document linking to the first digital document is calculated as the token frequency weight of the corresponding link multiplied by the inverse context frequency weight of the corresponding link.

8. The method of claim 5, wherein the step of converting the second feature comprises the sub-steps of:

identifying each digital document having hyperlinks within the collection of digital documents, and further identifying each unique word associated with URLs defining hyperlinks in each digital document;

counting the occurrences of each unique word in the URLs defining hyperlinks pointing to the first digital document; and

creating the second vector having a number of dimensions equal to the number of unique words associated with URLs defining hyperlinks within the collection of digital documents, and the second vector further having as each element a numeric value representative of the number of occurrences in the URLs defining hyperlinks pointing to the first digital document of the corresponding word.

9. The method of claim 8, wherein the numeric value representative of the number of occurrences in the URLs defining hyperlinks pointing to the first digital document of the corresponding word is calculated as the token frequency weight of the corresponding word multiplied by the inverse context frequency weight of the corresponding word.

10. The method of claim 1 further comprising the steps of:

extracting a second feature corresponding to the first digital document, the second feature comprising outlinks in the collection of digital documents linking to the first digital document;

converting the second feature to a second vector; and

associating the second vector with the first digital document.

11. The method of claim 10, wherein the step of converting the second feature comprises the sub-steps of:

identifying each other digital document linked to by all digital documents within the collection of digital documents; and

creating the second vector having a number of dimensions equal to the number of other digital documents linked to by digital documents in the collection of digital documents, and the second vector further having as each element a numeric value representative of the number of links in the first digital document linking to each corresponding other digital document.

12. The method of claim 11, wherein the numeric value representative of the number of links in the first digital document linking to each corresponding other digital document is calculated as the token frequency weight of the corresponding link multiplied by the inverse context frequency weight of the corresponding link.

13. The method of claim 10, wherein the step of converting the second feature comprises the sub-steps of:

identifying each unique word associated with URLs defining hyperlinks in each digital document in the collection of digital documents;

counting the occurrences of each unique word in the URLs defining hyperlinks in the first digital document; and

creating the second vector having a number of dimensions equal to the number of unique words associated with the URLs defining hyperlinks in each digital document, and the second vector further having as each element a numeric value representative of the number of occurrences in the URLs defining hyperlinks in the first digital document of the corresponding word.

14. The method of claim 13, wherein the numeric value representative of the number of occurrences in the URLs defining hyperlinks in the first digital document of the corresponding word is calculated as the token frequency weight of the corresponding word multiplied by the inverse context frequency weight of the corresponding word.

15. A signal representing instructions for quantitatively representing in a vector space users of a collection of digital documents, the instructions comprising:

identifying a first user to be processed from the users of the collection of digital documents;

extracting from the collection of digital documents a first feature representing a first sub-set of digital documents of the collection that have been accessed by the first user;

converting the first feature to a first vector; and

associating the first vector with the first user.

16. The signal of claim 15, wherein the converting instruction comprises:

identifying each unique digital document in the collection of digital documents;

calculating the number of times the first user accessed each digital document in the collection of digital documents; and

creating the first vector having a number of dimensions equal to the number of digital documents in the collection of digital documents, and the first vector further having as each element a numeric value representative of the number of times the first user has accessed the corresponding digital document.

17. The signal of claim 16, wherein the value representative of the number of times the first user has accessed the corresponding digital document is calculated as the token frequency weight of the corresponding digital document multiplied by the inverse context frequency weight of the corresponding digital document.

18. A computer-readable medium containing instructions for causing a computer-system to quantitatively represent digital documents in a vector space, by the steps of:

identifying a digital document to be processed from a plurality of digital documents;

selecting an image feature as a first feature, the image feature being associated with the non-text content of an image included in the digital document;

extracting from the document information associated with the first feature;

converting information associated with the first feature into a first vector;

associating the first vector with the digital document;

selecting a second feature from a set of multi-modal features including a user information feature and a genre feature;

extracting from the document information associated with the second feature;

converting the information associated with the second feature into a second vector; and

associating the second vector with the digital document.

19. The computer-readable medium of claim 18 wherein the first feature comprises a color histogram for the image included in the digital document.

20. The computer-readable medium of claim 19 wherein converting the information associated with the first feature into the first vector comprises the steps of:

quantizing the image included in the digital document into a multi-dimensional color model;

creating a color histogram having a plurality of bins for each dimension in the color model, each bin corresponding to a unique combination of binary bits representing information from the associated dimension of the color model;

counting each of a plurality of pixels from the image in a corresponding bin associated with each dimension of the color model; and

creating a vector having a number of dimensions equal to the total number of bins in the color histogram, and further having as each element a numeric value representative of the number of pixels in the image corresponding to the corresponding histogram bin.

21. The computer-readable medium of claim 18 wherein the first feature comprises color complexity of the image included in the digital document.

22. The computer-readable medium of claim 21 wherein converting the information associated with the first feature into the first vector comprises the steps of:

quantizing the image included in the digital document into a multi-dimensional color model;

determining the maximum number of pixels in any row in any image represented by any digital document in the collection of digital documents;

determining the maximum number of pixels in any column in any image represented by any digital document in the collection of digital documents;

creating a horizontal complexity histogram and a vertical complexity histogram, each having a number of bins equal to the maximum number of pixels in any row and in any column, respectively;

identifying horizontal runs of pixels of all possible lengths in the quantized image, and for each possible length, counting the number of pixels in a plurality of rows of the quantized image belonging to the horizontal runs in a corresponding bin of the horizontal complexity histogram;

identifying vertical runs of pixels of all possible lengths in the quantized image, and for each possible length, counting the number of pixels in a plurality of columns of the quantized image belonging to the vertical runs in a corresponding bin of the horizontal complexity histogram;

creating a horizontal complexity vector having a number of dimensions equal to the maximum number of pixels in any row, and further having as each element a numeric value representing the number of pixels in the image in the corresponding horizontal histogram bin; and

creating a vertical complexity vector having a number of dimensions equal to the maximum number of pixels in any column, and further having as each element a numeric value representing the number of pixels in the image in the corresponding vertical histogram bin.

23. A method for quantitatively representing digital documents in a vector space, comprising the steps of:

identifying a first digital document to be processed from a plurality of digital documents;

extracting a first feature corresponding to the first digital document from the plurality of digital documents, the first feature comprising an image feature associated with non-text content of an image included in the first digital document;

converting the first feature to a first vector;

associating the first vector with the first digital document;

extracting a second feature corresponding to the digital document, the second feature comprising a one of a user feature and a text genre feature;

converting the second feature into a second vector; and

associating the second vector with the first digital document.

24. The method of claim 23, wherein the second feature comprises a text genre feature.

25. The method of claim 24, wherein the step of converting the second feature comprises the sub-steps of:

for each possible text genre, processing the first digital document to calculate the probability that the first digital document is of the corresponding text genre; and

creating the second vector having a number of dimensions equal to the number of possible text genres, and the second vector further having as each element a numeric value representative of the probability that the first digital document is of the corresponding genre.

26. The method of claim 23, wherein the first feature comprises the color histogram for the image included in the first digital document.

27. The method of claim 26, wherein the step of converting the first feature comprises the sub-steps of:

quantizing the image represented by the first digital document into a multi-dimensional color model;

creating a color histogram having a plurality of bins for each dimension in the color model, each bin corresponding to a unique combination of binary bits representing information from the associated dimension of the color model;

counting each of a plurality of pixels from the image in a corresponding bin associated with each dimension of the color model; and

creating the first vector having a number of dimensions equal to the total number of bins in the color histogram, and the first vector further having as each element a numeric value representative of the number of pixels in the image corresponding to the corresponding histogram bin.

28. The method of claim 27, wherein the plurality of pixels from the image in the counting step comprises all of the pixels in the image.

29. The method of claim 28, wherein the plurality of pixels from the image in the counting step comprises an approximately uniformly spaced set of subsampled pixels from the image.

30. The method of claim 27, wherein:

the color model comprises a three-dimensional hue, saturation, and value color model;

each dimension of the color model is represented by two bits of information; and

the color histogram has four bins for each dimension in the color model, for a total of twelve bins.

31. The method of claim 27, wherein the image represented by the first digital document comprises a region of a bitmap.

32. The method of claim 23, wherein the first feature comprises the color complexity of an image represented by the first digital document.

33. The method of claim 32, wherein the step of converting the first feature comprises the sub-steps of:

quantizing the image represented by the first digital document into a multi-dimensional color model;

determining the maximum number of pixels in any row in any image represented by any digital document in the collection of digital documents;

determining the maximum number of pixels in any column in any image represented by any digital document in the collection of digital documents;

creating a horizontal complexity histogram and a vertical complexity histogram, each having a number of bins equal to the maximum number of pixels in any row and in any column, respectively;

identifying horizontal runs of pixels of all possible lengths in the quantized image, and for each possible length, counting the number of pixels in a plurality of rows of the quantized image belonging to the horizontal runs in a corresponding bin of the horizontal complexity histogram;

identifying vertical runs of pixels of all possible lengths in the quantized image, and for each possible length, counting the number of pixels in a plurality of columns of the quantized image belonging to the vertical runs in a corresponding bin of the horizontal complexity histogram;

creating a horizontal complexity vector having a number of dimensions equal to the maximum number of pixels in any row, and further having as each element a numeric value representing the number of pixels in the image in the corresponding horizontal histogram bin; and

creating a vertical complexity vector having a number of dimensions equal to the maximum number of pixels in any column, and further having as each element a numeric value representing the number of pixels in the image in the corresponding vertical histogram bin.

34. The method of claim 33, wherein the plurality of rows comprises all rows of the quantized image, and wherein the plurality of columns comprises all columns of the quantized image.

35. The method of claim 33, wherein the plurality of rows comprises an approximately uniformly spaced set of subsampled rows from the image, and wherein the plurality of columns comprises an approximately uniformly spaced set of subsampled columns from the image.

36. The method of claim 33, wherein:

the color model comprises a three-dimensional hue, saturation, and value color model; and

each dimension of the color model is represented by two bits of information.

37. The method of claim 33, further comprising the step of concatenating the horizontal complexity vector and the vertical complexity vector to form a complexity vector having a number of dimensions equal to the maximum number of pixels in any row plus the maximum number of pixels in any column.

38. The method of claim 32, wherein the step of converting the first feature comprises the sub-steps of:

quantizing the image represented by the first digital document into a multi-dimensional color model;

determining the maximum number of pixels in any row in any image represented by any digital document in the collection of digital documents;

determining the maximum number of pixels in any column in any image represented by any digital document in the collection of digital documents;

creating a horizontal complexity histogram and a vertical complexity histogram, each having a selected number of bins corresponding to a plurality of quantized ranges of run lengths;

identifying horizontal runs of pixels of all possible lengths in the quantized image, and for each possible length, counting the number of pixels in a plurality of rows of the quantized image belonging to the horizontal runs in a corresponding bin of the horizontal complexity histogram;

identifying vertical runs of pixels of all possible lengths in the quantized image, and for each possible length, counting the number of pixels in a plurality of columns of the quantized image belonging to the vertical runs in a corresponding bin of the horizontal complexity histogram;

creating a horizontal complexity vector having a number of dimensions equal to the selected number of bins in the horizontal complexity histogram, and further having as each element a numeric value representing the number of pixels in the image in the corresponding horizontal histogram bin; and

creating a vertical complexity vector having a number of dimensions equal to the number of bins in the vertical complexity histogram, and further having as each element a numeric value representing the number of pixels in the image in the corresponding vertical histogram bin.

39. The method of claim 38, wherein:

a bin b_x in the horizontal complexity histogram corresponding to a horizontal rim of length r_x is identified by a relationship b_x=floor(r_x(N−

1)/(n_x/4))+1, where N is the selected number of bins in the horizontal complexity histogram and n_x is a maximum number of pixels in any row of an image in the collection; and

a bin b_y in the vertical complexity histogram corresponding to a vertical run of length r_y is identified by a relationship b_y=floor(r_y(N−

1)/(n_y/4))+1, where N is the selected number of bins in the horizontal complexity histogram and n_y is a maximum number of pixels in any row of an image in the collection.

40. The method of claim 38, wherein the plurality of rows comprises an approximately uniformly spaced set of subsampled rows from the image, and wherein the plurality of columns comprises an approximately uniformly spaced set of subsampled columns from the image.

41. The method of claim 38, wherein:

the color model comprises a three-dimensional hue, saturation, and value color model; and

each dimension of the color model is represented by two bits of information.

42. The method of claim 38, further comprising the step of concatenating the horizontal complexity vector and the vertical complexity vector to form a complexity vector having a number of dimensions equal to the selected number of bins in the horizontal complexity histogram plus the selected number of bins in the vertical complexity histogram.

43. A system for quantitatively representing digital documents in a vector space, comprising:

comprising;

a processor adapted to execute instructions; and

a computer-readable memory storing instructions for causing the processor to quantitatively represent digital documents in a vector space;

identifying a first digital document to be processed from a plurality of digital documents;

extracting a first feature corresponding to the first document from the plurality of digital documents, the first feature comprising text surrounding an image included in the digital document, the text surrounding the image not being anchor text;

converting the first feature to a first vector; and

associating the first vector with the first digital document.

44. A system for quantitatively representing digital documents in a vector space, comprising:

comprising;

a processor adapted to execute instructions; and

a computer-readable memory storing instructions for causing the processor to quantitatively represent digital documents in a vector space;

identifying a first digital document to be processed from a plurality of digital documents;

extracting a first feature corresponding to the first digital document from the plurality of digital documents, the first feature comprising an image feature associated with non-text content of an image included in the first digital document;

converting the first feature to a first vector;

associating the first vector with the first digital document;

extracting a second feature corresponding to the digital document, the second feature comprising a one of a user feature and a text genre feature;

converting the second feature into a second vector; and

associating the second vector with the first digital document.