Phrase-based personalization of searches in an information retrieval system

• US 7,580,929 B2
• Filed: 07/26/2004
• Issued: 08/25/2009
• Est. Priority Date: 07/26/2004
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.), ViaViente (Youngevity International, Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Patterson, Anna Lynn
• Primary Examiner(s): Vy; Hung T
• Application Number:
  US10/900,039
• Publication Number:
  US 20080319971A1
• Time in Patent Office: 1,856 Days
• Field of Search: 707/1, 707 2- 6, 707/104.1, 707/100, 715/501.1, 704/9, 455/3.04, 709/224
• US Class Current: 1/1
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

An information retrieval system uses phrases to index, retrieve, organize and describe documents. Phrases are identified that predict the presence of other phrases in documents. Documents are the indexed according to their included phrases. Related phrases and phrase extensions are also identified. Phrases in a query are identified and used to retrieve and rank documents. Phrases are also used to cluster documents in the search results, create document descriptions, and eliminate duplicate documents from the search results, and from the index.

Claims

1. A method of personalizing a search of a document collection to a user, the method comprising:

monitoring a plurality of documents accessed by a user;

identifying a plurality of first phrases present in one or more of the accessed documents;

for each of the identified first phrases, identifying one or more corresponding first related phrases, wherein the one or more first related phrases are related to the corresponding identified first phrase;

storing a user model associated with the user, and comprising a plurality of the first related phrases;

receiving a query from the user, the query including one or more second phrases;

selecting search results comprising a plurality of documents responsive to the query;

identifying, by operation of a processor configured to manipulate data within a computer system, one or more second related phrases that are related to the second phrase(s) of the query and that are present in the user model;

weighting a plurality of scores of a corresponding plurality of the search results according to the identified one or more second related phrases;

ranking the plurality of the search results for presentation to the user according to their weighted scores, to provide personalized search results; and

presenting the personalized search results to the user.

2. The method of claim 1, wherein a document accessed by the user comprises a document printed by the user.

3. The method of claim 1, wherein a document accessed by the user comprises a document saved by the user.

4. The method of claim 1, wherein a document accessed by the user comprises a document stored as a favorite or link.

5. The method of claim 1, wherein a document accessed by the user comprises a document sent by email by the user.

6. The method of claim 1, wherein a document accessed by the user comprises a document maintained in a browser window for a predetermined amount of time.

7. The method of claim 1, wherein the documents accessed by the user are substantially only those documents accessed during a current session.

8. The method of claim 1, wherein selecting search results comprising a plurality of documents responsive to the query comprises:

identifying an incomplete phrase in the query;

replacing the incomplete phrase with a phrase extension, wherein the phrase extension of the incomplete phrase is a super-sequence of the incomplete phrase that begins with the incomplete phrase, and wherein the incomplete phrase predicts the phrase extension; and

selecting documents from the document collection containing the phrase extension.

9. The method of claim 8, wherein the incomplete phrase predicts the phrase extension based on a measure of an actual frequency of the phrase extension being greater than an expected frequency of the phrase extension in the document collection.

10. The method of claim 1, wherein

a related phrase g_k is related to a phrase g_j in a document when an information gain I of g_k with respect to g_j exceeds a predetermined threshold, the information gain I being a function of A(j,k) and E(j,k), where A(j,k) is a measure of an actual co-occurrence rate of g_j and g_k in a plurality of documents in the documents collection and E(j,k) is an expected co-occurrence rate g_j and g_k in a plurality of documents in the documents collection.

11. A method of personalizing a search of a document collection to a user, the method comprising:

monitoring a plurality of documents accessed by a user;

identifying a plurality of first phrases present in one or more of the accessed documents;

for each of the identified first phrases, identifying one or more corresponding first related phrases, wherein the one or more first related phrases are related to the corresponding identified first phrase;

storing a user model associated with the user, and comprising a plurality of the first related phrases;

receiving a query from the user, the query including one or more second phrases;

selecting search results comprising a plurality of documents responsive to the query;

identifying, by operation of a processor configured to manipulate data within a computer system, one or more second related phrases that are related to the second phrase(s) of the query and that are present in the user model, comprising;

for each phrase of the query, accessing a related phrase bit vector for the phrase of the query, wherein each bit of the related phrase bit vector indicates the presence or absence of a second related phrase of the phrase of the query;

determining from the related phrase bit vector which of the second related phrases are present in the user model; and

forming a related phrase bit mask corresponding to the second related phrases that are present in the user model;

weighting a plurality of scores of a corresponding plurality of the search results according to the identified one or more second related phrases;

ranking the plurality of the search results for presentation to the user according to their weighted scores, to provide personalized search results; and

presenting the personalized search results to the user.

12. The method of claim 11, wherein weighting a plurality of scores of a corresponding plurality of the search results according to the identified one or more second related phrases, comprises:

accessing a related phrase bit vector for a document and query phrase; and

weighting the related phrase bit vector for the document using the related phrase bit mask.

13. A method of personalizing a search of a document collection to a user, the method comprising:

monitoring a plurality of documents accessed by a user;

identifying a plurality of first phrases present in one or more of the accessed documents;

for each of the identified first phrases, identifying one or more corresponding first related phrases, wherein the one or more first related phrases are related to the corresponding identified first phrase;

storing a user model associated with the user, and comprising a plurality of cluster counts, each cluster count associated with a predetermined cluster that includes a plurality of first related phrases, and storing a count of a number of instances of first related phrases of the cluster appearing in a document accessed by the user;

receiving a query from the user, the query including one or more second phrases;

selecting search results comprising a plurality of documents responsive to the query;

identifying, by operation of a processor configured to manipulate data within a computer system, one or more second related phrases that are related to the second phrase(s) of the query and that are present in the user model;

weighting a plurality of scores of a corresponding plurality of the search results according to the cluster counts of the identified one or more second related phrases;

ranking the plurality of the search results for presentation to the user according to their weighted scores, to provide personalized search results; and

presenting the personalized search results to the user.

14. The method of claim 13, wherein a document accessed by the user comprises a document printed by the user.

15. The method of claim 13, wherein the document accessed by the user comprises a document saved by the user.

16. The method of claim 13, wherein the document accessed by the user comprises a document stored as a favorite or link.

17. The method of claim 13, wherein the document accessed by the user comprises a document sent by email by the user.

18. The method of claim 13, wherein the document accessed by the user comprises a document maintained in a browser window for a predetermined amount of time.

19. The method of claim 13, wherein selecting search results comprising a plurality of documents responsive to the query comprises:

identifying an incomplete phrase in the query;

replacing the incomplete phrase with a phrase extension, wherein the phrase extension of the incomplete phrase is a super-sequence of the incomplete phrase that begins with the incomplete phrase, and wherein the incomplete phrase predicts the phrase extension; and

selecting documents from the document collection containing the phrase extension.

20. The method of claim 19, wherein the incomplete phrase predicts the phrase extension based on a measure of an actual frequency of the phrase extension being greater than an expected frequency of the phrase extension in the document collection.

21. A computer readable storage medium storing a computer program executable by a processor for personalizing a search of a document collection to a user, the operations of the computer program comprising:

monitoring a plurality of documents accessed by a user;

identifying a plurality of first phrases present in one or more of the accessed documents;

for each of the identified first phrases, identifying one or more corresponding first related phrases, wherein the one or more first related phrases are related to the corresponding identified first phrase;

storing a user model associated with the user, and comprising a plurality of the first related phrases;

receiving a query from the user, the query including one or more second phrases;

selecting search results comprising a plurality of documents responsive to the query;

identifying, by operation of a processor configured to manipulate data within a computer system, one or more second related phrases that are related to the second phrase(s) of the query and that are present in the user model;

weighting a plurality of scores of a corresponding plurality of the search results according to the cluster counts of the identified one or more second related phrases;

ranking the plurality of the search results for presentation to the user according to their weighted scores, to provide personalized search results; and

presenting the personalized search results to the user.

22. The computer readable storage medium of claim 21, wherein identifying one or more second related phrases that are related to the second phrase(s) of the query and that are present in the user model, comprises:

for each phrase of the query, accessing a related phrase bit vector for the phrase of the query, wherein each bit of the related phrase bit vector indicates the presence or absence of a related phrase of the phrase of the query;

determining from the related phrase bit vector which of the second related phrases are present in the user model; and

forming a related phrase bit mask corresponding to the related phrases that are present in the user model.

23. A computer readable storage medium storing a computer program executable by a processor for personalizing a search of a document collection to a user, the operations of the computer program comprising:

monitoring a plurality of documents accessed by a user;

identifying a plurality of first phrases present in one or more of the accessed documents;

for each of the identified first phrases, identifying one or more corresponding first related phrases, wherein the one or more first related phrases are related to the corresponding identified first phrase;

storing a user model associated with the user, and comprising a plurality of cluster counts, each cluster count associated with a predetermined cluster that includes a plurality of the first related phrases, and storing a count of a number of instances of the first related phrases of the cluster appearing in a document accessed by the user;

receiving a query from the user, the query including one or more second phrases;

selecting search results comprising a plurality of documents responsive to the query;

identifying, by operation of a processor configured to manipulate data within a computer system, one or more second related phrases that are related to the second phrase(s) of the query and that are present in the user model;

weighting a plurality of scores of a corresponding plurality of the search results according to the cluster counts of the identified one or more second related phrases;

ranking the plurality of the search results for presentation to the user according to their weighted scores, to provide personalized search results; and

presenting the personalized search results to the user.

24. The computer readable storage medium of claim 23, wherein selecting search results comprising a plurality of documents responsive to the query comprises:

identifying an incomplete phrase in the query;

replacing the incomplete phrase with a phrase extension, wherein the phrase extension of the incomplete phrase is a super-sequence of the incomplete phrase that begins with the incomplete phrase, and wherein the incomplete phrase predicts the phrase extension based on a measure of an actual frequency of the phrase extension being greater than an expected frequency of the phrase extension in the document collection; and

selecting documents from the document collection containing the phrase extension.

25. A computer implemented system for personalizing a search of a document collection to a user, comprising:

a user model associated with the user, stored in a storage medium and comprising a plurality of first related phrases contained in documents accessed by the user, wherein the first related phrases are identified as related to one or more first phrases in documents that have been accessed by a user; and

a query processing system executed by a computer and configured to;

receive a query from the user, wherein the query includes one or more second phrases;

select search results comprising a plurality of documents responsive to the query,

identify one or more second related phrases that are related to the second phrase(s) of the query and that are present in the user model,

weight a plurality of scores of a corresponding plurality of the search results according to the identified one or more second related phrases,

rank the plurality of the search results for presentation to the user according to their weighted scores, to provide personalized search results, and

present the personalized search results to the user.

26. The system of claim 25, wherein the query processing system identifies phrases that are related to the query and present in the user model by:

for each phrase of the query, accessing a related phrase bit vector for the query phrase, wherein each bit of the related phrase bit vector indicates the presence or absence of a related phrase of the phrase of the query;

determining from the related phrase bit vector which of the related phrases are present in the user model; and

forming a related phrase bit mask corresponding to the related phrases that are present in the user model.

27. A computer implemented system for personalizing a search of a document collection to a user, comprising:

a user model associated with the user, stored in storage medium and comprising a plurality of cluster counts, each cluster count associated with a predetermined cluster that includes a plurality of related first phrases, and storing a count of a number of instances of related first phrases of the cluster appearing in a document accessed by the user; and

a query processing system executed by a computer and configured to;

receive a query from the user, wherein the query includes one or more second phrases;

select search results comprising a plurality of documents responsive to the query,

identify one or more second related phrases that are related to the second phrase(s) of the query and associated with cluster counts in the user model,

weight a plurality of scores of a corresponding plurality of the search results according to the cluster counts of the identified one or more second related phrases,

rank the plurality of the search results for presentation to the user according to their weighted scores, to provide personalized search results, and

present the personalized search results to the user.

28. The system of claim 27, wherein the query processing system selects search results comprising a plurality of documents responsive to the query by:

identifying an incomplete phrase in the query;

replacing the incomplete phrase with a phrase extension, wherein the phrase extension of the incomplete phrase is a super-sequence of the incomplete phrase that begins with the incomplete phrase, and wherein the incomplete phrase predicts the phrase extension based on a measure of an actual frequency of the phrase extension being greater than an expected frequency of the phrase extension in the document collection; and

selecting documents from the document collection containing the phrase extension.