Phase-based personalization of searches in an information retrieval system

• US 9,037,573 B2
• Filed: 06/17/2013
• Issued: 05/19/2015
• Est. Priority Date: 07/26/2004
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Patterson, Anna L.
• Primary Examiner(s): Vy, Hung T
• Application Number:
  US13/919,830
• Publication Number:
  US 20140156647A1
• Time in Patent Office: 701 Days
• Field of Search: 707/754, 707/705, 707/706, 707/709, 707/711, 707/741, 707/758, 707/722, 707/723, 715/705
• US Class Current: 707/722
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06Q 10/10 Office automation; Time management

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 the user;

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

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

selecting a plurality of documents selected from the document collection that are responsive to the query;

identifying one or more of the first phrases as related phrases that are related to the one or more second phrases, wherein a particular related phrase is related to a particular second phrase when an information gain exceeds a threshold, the information gain being a ratio of an actual co-occurrence rate of the particular related phrase and the particular second phrase in documents of the document collection and an expected occurrence rate of the particular related phrase and the particular second phrase in the documents;

weighting a plurality of scores, each score corresponding to a respective document of the plurality of selected documents responsive to the query, wherein the score of the respective document that includes the one or more related phrases is boosted by the weighting;

ranking the plurality of selected documents for presentation to the user based on their corresponding 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 at least 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 the 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, the phrase extension being one of the second phrases.

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, the identifying one or more related phrases including:

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

determining from the related phrase bit vector which of the related phrases are also first phrases; and

forming a related phrase bit mask corresponding to the related phrases that are also first phrases.

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

a processor; and

memory storing instructions that, when executed by the processor, cause the computer system to;

monitor a plurality of documents accessed by the user,

identify a plurality of first phrases present in one or more of the accessed documents,

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

select a plurality of documents responsive to the query as a search result,

identify one or more of the first phrases as related phrases that are related to the one or more second phrases, wherein a particular related phrase is related to a particular second phrase when an information gain exceeds a threshold, the information gain being a ratio of an actual co-occurrence rate of the particular related phrase and the particular second phrase in documents of the document collection and an expected occurrence rate of the particular related phrase and the particular second phrase in the documents,

weight a plurality of scores, each score corresponding to a respective document in the plurality of documents responsive to the query, wherein the score of the respective document that includes the one or more related phrases is boosted,

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

present the personalized search results to the user.

12. The system of claim 11, wherein selecting the 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, the phrase extension being one of the second phrases.

13. The system of claim 12, 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.

14. The system of claim 11 wherein the related phrases are second related phrases and the memory also stores a plurality of first related phrases contained in the documents accessed by the user, wherein the first related phrases are identified as related to one or more of the plurality of first phrases.

15. The system of claim 11, wherein identifying the one or more related phrases includes:

for a particular second phrase of the one or more second phrases, accessing a related phrase bit vector for the particular second phrase, wherein each bit of the related phrase bit vector indicates the presence or absence of a related phrase of the particular second phrase;

determining from the related phrase bit vector which of the related phrases are also first phrases; and

forming a related phrase bit mask corresponding to the related phrases that are also first phrases.