Techniques for web site integration

• US 8,862,565 B1
• Filed: 01/05/2012
• Issued: 10/14/2014
• Est. Priority Date: 05/08/2000
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Chipalkatti, Renu, Getchius, Jeffrey, Ponte, Jay
• Primary Examiner(s): PANNALA, SATHYANARAYA R
• Application Number:
  US13/344,566
• Time in Patent Office: 1,013 Days
• Field of Search: 707/999.004, 707/706
• US Class Current: 707/706
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: Y10S 707/955 Object-oriented
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

Disclosed is a method and device for finding documents, such as Web pages, for presentation to a user, automatically or in response to a user expression of interest, which documents are part of a Web site being accessed by the user, and which documents relate to a document, such as a Web page, being accessed in the Web site. The method takes advantage of information retrieval techniques. The method generates the search query to use to find documents by reference to the text of the document in the Web site being accessed by the user. The method further uses a weighting function to weigh the terms used in the search query.

Claims

1. A system, comprising:

a computer system coupled to one or more storage devices storing instructions that, when executed by the computer system, cause the computer system to perform operations comprising;

identifying an initial document accessed by a user, wherein the initial document is in a Web site, and wherein the initial document includes a plurality of terms;

selecting documents contained in the Web site that are related to the initial document, comprising;

identifying a respective compressed document surrogate for each of a plurality of other documents in the Web site, wherein each of the compressed document surrogates includes data identifying a plurality of terms that occur in the other document and, for each of the plurality of terms, a respective frequency of occurrence of the term in the other document;

assigning a respective score to each of the plurality of other documents in the web site based at least in part on frequencies of occurrence identified in the compressed document surrogate for the other document for terms from the plurality terms included in the initial document; and

selecting one or more other documents as related documents based on the scores; and

presenting data identifying the related documents to the user.

2. The system of claim 1, wherein the data identifying the related documents is presented to the user automatically when the user accesses the initial document in the Web site.

3. The system of claim 1, wherein the data identifying the related documents is presented to the user in response to a request from the user.

4. The system of claim 1, wherein the Web site comprises one or more Web pages and wherein the other documents are Web pages or subdivisions of the Web site.

5. The system of claim 1, wherein a predetermined number of other documents is selected.

6. The system of claim 5, wherein the predetermined number of other documents is 100.

7. The system of claim 1, wherein all other documents with scores exceeding a predetermined cutoff value are selected.

8. The system of claim 1, wherein a score S_D of an other document D in the Web site is determined by crediting the document D, for each term T in the document accessed by the user which is identified in the compressed document surrogate for the document D, with an amount proportional to Robertson'"'"'s term frequency TF_TD and to IDF_T where

TF_TD=N_TD/(N_TD+K₁+K₂*(L_D/L₀)), and

N_TD is the number of times the term T occurs in document D,

L_D is the length of document D,

L₀ is the average length of a document in the Web site,

K₁ and K₂ are constants, and

IDF_T=log((N+K₃)/N_T)/log(N+K₄), and

N is the number of documents in the Web site,

N_T is the number of documents containing the term T in the Web site, and

K₃ and K₄ are constants.

9. The system of claim 8, wherein K₁ is 0.5, K₂ is 1.5, K₃ is 0.5, and K₄ is 1.0.

10. The system of claim 1, wherein the score assigned to an other document depends upon how often a term that is identified in the compressed document surrogate for the other document occurs in the initial document accessed by the user;

compared to how often the term occurs in the documents in the Web site.

11. The system of claim 10, wherein a score S_D of an other document D in the Web site is determined by crediting the document D, for each term T in the initial document accessed by the user which is identified in the compressed document surrogate for the document D, with an amount proportional to W_T, to Robertson'"'"'s term frequency TF_TD and to IDF_T where

W_T=log(P_T(R)/P_T(R)), where

P_T(R)=a probability that the term T occurs in the initial document accessed by the user,

=N_TR/(Σ

_R N_tR), where

N_TR=a number of occurrences of the term T in the initial document accessed by the user,

Σ

_R N_tR=a total number of occurrences of terms in the initial document accessed by the user,

P_T(R)=a probability that the term T occurs in the Web site,

=N_TR/(Σ

_R N_tR), where

N_TR=a number of occurrences of the term T in the Web site,

Σ

_R N_tR=a total number of occurrences of terms in the Web site,

TF_TD=N_TD/(N_TD+K₁+K₂*(L_D/L₀)), and

N_TD is the number of times the term T occurs in document D,

L_D is the length of document D,

L₀ is the average length of a document in the Web site,

K₁ and K₂ are constants, and

IDF_T=log((N+K₃)/N_T)/log(N+K₄), and

N is the number of documents in the Web site,

N_T is the number of documents containing the term T in the Web site, and

K₃ and K₄ are constants.

12. The system of claim 11, wherein K₁ is 0.5, K₂ is 1.5, K₃ is 0.5, and K₄ is 1.0.

13. The system of claim 11, wherein assigning a respective score to each of the plurality of other documents in the web site comprises assigning a respective score to each of the plurality of other documents in the web site based at least in part on an occurrence in the other document of index terms manually assigned to the initial document accessed by the user.

14. The system of claim 13, wherein the score assigned to the other document, as a result of containing an index term assigned to the initial document depends upon how often the term occurs in the initial document accessed by the user compared to how often the term occurs in the documents in the Web site.

15. The system of claim 13, wherein the score assigned to the other document depends upon a weight assigned to the index terms.

16. A system, comprising:

a computer system coupled to one or more storage devices storing instructions that, when executed by the computer system, cause the computer system to perform operations comprising;

identifying an initial document accessed by a user, wherein the initial document is in a Web site, and wherein the initial document includes a plurality of terms

presenting data identifying other documents contained in the Web site that are related to the initial document to the user; and

a search engine configured to select the other documents that are related to the initial document, comprising;

identifying a respective compressed document surrogate for each of a plurality of other documents in the Web site, wherein each of the compressed document surrogates includes data identifying a plurality of terms that occur in the other document and, for each of the plurality of terms, a respective frequency of occurrence of the term in the other document;

assigning a respective score to each of the plurality of other documents in the web site based at least in part on frequencies of occurrence identified in the compressed document surrogate for the other document for terms from the plurality terms included in the initial document; and

selecting one or more other documents as related documents based on the scores.

17. The system of claim 16, wherein the data identifying the related documents is presented to the user automatically when the user accesses the initial document in the Web site.

18. The system of claim 16, wherein the data identifying the related documents is presented to the user in response to a request from the user.

19. The system of claim 16, wherein the Web site comprises one or more Web pages and wherein the other documents are Web pages or subdivisions of the Web site.

20. The system of claim 16, wherein a predetermined number of other documents is selected.

21. The system of claim 20, wherein the predetermined number of other documents is 100.

22. The system of claim 16, wherein all other documents with scores exceeding a predetermined cutoff value are selected.

23. The system of claim 16, wherein a score S_D of an other document D in the collection may be determined by crediting the document D, for each term T in the document accessed by the user which is identified in the compressed document surrogate for the document D, with an amount proportional to Robertson'"'"'s term frequency TF_TD and to IDF_T where

TF_TD=N_TD/(N_TD+K₁+K₂*(L_D/L₀)), and

N_TD is the number of times the term T occurs in document D,

L_D is the length of document D,

L₀ is the average length of a document in the Web site,

K₁ and K₂ are constants, and

IDF_T=log((N+K₃)/N_T)/log(N+K₄), and

N is the number of documents in the Web site,

N_T is the number of documents containing the term T in the Web site, and

K₃ and K₄ are constants.

24. The system of claim 23, wherein K₁ is 0.5, K₂ is 1.5, K₃ is 0.5, and K₄ is 1.0.

25. The system of claim 16, wherein the score assigned to an other document depends upon how often a term that is identified in the compressed document surrogate for the other document occurs in the initial document accessed by the user compared to how often the term occurs in the documents in the Web site.

26. The system of claim 25, wherein a score S_D of an other document D in the Web site is determined by crediting the document D, for each term T in the document accessed by the user which is identified in the compressed document surrogate for the document D, with an amount proportional to W_T, to Robertson'"'"'s term frequency TF_TD and to IDF_T where

W_T=log(P_T(R)/P_T(R)), where

P_T(R)=a probability that the term T occurs in the initial document accessed by the user,

=N_TR/(Σ

_R N_tR), where

N_TR=a number of occurrences of the term T in the initial document accessed by the user,

Σ

_R N_tR=a total number of occurrences of terms in the document accessed by the user,

P_T(R)=a probability that the term T occurs in the Web site,

=N_TR/(Σ

_R N_tR), where

N_TR=a number of occurrences of the term T in the Web site,

Σ

_R N_tR=a total number of occurrences of terms in the Web site,

TF_TD=N_TD/(N_TD+K₁+K₂*(L_D/L₀)), and

N_TD is the number of times the term T occurs in document D,

L_D is the length of document D,

L₀ is the average length of a document in the Web site,

K₁ and K₂ are constants, and

IDF_T=log((N+K₃)/N_T)/log(N+K₄), and

N is the number of documents in the Web site,

N_T is the number of documents containing the term T in the Web site, and

K₃ and K₄ are constants.

27. The system of claim 26, wherein K₁ is 0.5, K₂ is 1.5, K₃ is 0.5, and K₄ is 1.0.

28. The system of claim 16, wherein assigning a respective score to each of the plurality of other documents in the web site comprises assigning a respective score to each of the plurality of other documents in the web site based at least in part on an occurrence in the other document of index terms manually assigned to the initial document accessed by the user.

29. The system of claim 28, wherein the score assigned to the other document, as a result of containing an index term assigned to the initial document depends upon how often the term occurs in the initial document accessed by the user, compared to how often the term occurs in the documents in the Web site.

30. The system of claim 28, wherein the score assigned to the other document depends upon a weight assigned to the index terms.

31. A system, comprising:

a computer system coupled to a storage device, wherein a computer program stored on the storage device is operable, when executed by the computer system, to cause the computer system to perform operations comprising;

receiving an input from a user identifying an initial document in a collection of documents;

identifying other documents in the collection of documents that are related to the initial document, comprising;

assigning scores to a plurality of compressed document surrogates corresponding to the collection of documents, the scores depending on an occurrence in the compressed document surrogates of at least one term in the initial document, wherein a score S_D of a compressed document surrogate D in the plurality of compressed document surrogates is determined by crediting the compressed document surrogate D, for each term T in the initial document which occurs in the compressed document surrogate D, with an amount proportional to Robertson'"'"'s term frequency TF_TD and IDF_T where

TF_TD=N_TD/(N_TD+K₁+K₂*(L_D/L₀)), and

N_TD is the number of times the term T occurs in compressed document surrogate D,

L_D is the length of compressed document surrogate D,

L₀ is the average length of a document in the collection of documents,

K₁ and K₂ are constants, and

IDF_T=log((N+K₃)/N_T)/log(N+K₄), and

N is the number of documents in the collection of documents,

N_T is the number of documents containing the term T in the collection of documents, and

K₃ and K₄ are constants;

selecting a set of documents from the collection of documents, the set of documents comprising documents corresponding to those of the plurality of compressed document surrogates assigned the highest scores; and

presenting information identifying the set of documents to the user.

32. The system of claim 31, wherein assigning the scores, selecting the set of documents, and presenting the information identifying the set of documents to the user are performed automatically when a user accesses the initial document, without user intervention.

33. The system of claim 31, wherein assigning the scores, selecting the set of documents, and presenting the information identifying the set of documents to the user are performed in response to a request from the user to obtain the set of documents.

34. The system of claim 31, wherein the Web site comprises one or more Web pages and wherein the documents are Web pages or subdivisions of the Web site.

35. The system of claim 31, wherein the set of documents comprises documents corresponding to those of the plurality of compressed document surrogates assigned scores above a threshold.

36. The system of claim 31, wherein the set of documents comprises documents corresponding to those of the plurality of compressed document surrogates assigned the highest N scores, where N is a predetermined value of one or more.

37. The system of claim 31, wherein the score assigned to a particular one of the plurality of compressed document surrogates depends upon how often the at least one term occurs in the initial document compared to how often the at least one term occurs in the plurality of compressed document surrogates.

38. The system of claim 31, wherein the initial document includes at least one index term manually assigned to the initial document, the at least one term includes the at least one index term, and the score assigned to a particular one of the plurality of compressed document surrogates depends upon an occurrence of the at least one index term.

39. The system of claim 38, wherein the score assigned to the particular one of the plurality of compressed document surrogates depends upon how often the at least one term occurs in the initial document compared to how often the at least one term occurs in the plurality of compressed document surrogates, and depends upon a weight assigned to the at least one index term.

40. A system, comprising:

a computer system coupled to a storage device, wherein a computer program stored on the storage device is operable, when executed by the computer system, to cause the computer system to perform operations comprising;

receiving a request for an initial document in a plurality of documents from a user;

identifying documents in the plurality of documents that are related to the initial document comprising;

assigning scores to a plurality of documents, including;

determining, for each other document in the plurality of documents, if the document has an associated compressed document surrogate; and

when the document has an associated compressed document surrogate, assigning a score to the document based on occurrences of at least one term included in the initial document in the associated compressed document surrogate, wherein a score of S_D assigned to a document D in the plurality of documents is determined by crediting the document D, for each term T in the initial document which occurs in the compressed document surrogate associated with the document D, with an amount proportional to Robertson'"'"'s term frequency TF_TD and to IDF_T where

TF_TD=N_TD/(N_TD+K₁+K₂*(L_D/L₀)), and

N_TD is the number of times the term T occurs in compressed document surrogate D,

L_D is the length of compressed document surrogate D,

L₀ is the average length of a document in the collection of documents,

K₁ and K₂ are constants, and

IDF_T=log((N+K₃)/N_T)/log(N+K₄), and

N is the number of documents in the collection of documents,

N_T is the number of documents containing the term T in the collection of and

K₃ and K₄ are constants;

selecting a set of documents from the plurality of documents based on the assigned scores; and

presenting information identifying the set of documents to the user.

41. The system of claim 40, wherein assigning the scores, selecting the set of documents, and presenting the information identifying the set of documents to the user are performed automatically in response to receiving the request for the initial document, without user intervention.

42. The system of claim 40, wherein assigning the scores, selecting the set of documents, and presenting the information identifying the set of documents to the user are performed in response to an additional request from the user to obtain the set of documents.

43. The system of claim 40, wherein the Web site comprises one or more Web pages and wherein the documents are Web pages or subdivisions of the Web site.

44. The system of claim 40, wherein selecting the set of documents comprises selecting those of the plurality of documents assigned scores higher than a predetermined threshold.

45. The system of claim 40, wherein selecting the set of documents comprises selecting those of the plurality of documents assigned the highest N scores, where N is a predetermined value of one or more.

46. The system of claim 40, wherein assigning the scores further includes when the document does not have an associated compressed document surrogate, assigning a score to the document based on occurrences of the at least one term in the document.

47. The system of claim 40, wherein the initial document includes at least one index term manually assigned to the initial document, the at least one term includes the at least one index term, and the score assigned to a particular one of the plurality of documents depends upon an occurrence of the at least one index term.

48. The system of claim 47, wherein the score assigned to the particular one of the plurality of documents depends upon how often the at least one term occurs in the initial document compared to how often the at least one term occurs in the plurality of documents, and depends upon a weight assigned to the at least one index term.