Phrase-based searching in an information retrieval system

• US 7,599,914 B2
• Filed: 07/26/2004
• Issued: 10/06/2009
• Est. Priority Date: 07/26/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Patterson, Anna Lynn
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): CAO, PHUONG THAO
• Application Number:
  US10/900,041
• Publication Number:
  US 20060031195A1
• Time in Patent Office: 1,898 Days
• Field of Search: 707/2, 707/3, 707/4
• US Class Current: 1/1
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

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 computer-implemented method of selecting documents in a document collection in response to a query, the method comprising:

receiving a query;

identifying an incomplete phrase in the query, wherein other phrases predicted by the incomplete phrase in the document collection include only phrase extensions of the incomplete phrase;

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 co-occurrence rate of the phrase extension and the incomplete phrase exceeding an expected co-occurrence rate of the phrase extension and the incomplete phrase in the document collection, the expected co-occurrence rate of the phrase extension and the incomplete phrase being a function of a plurality of occurrences of the phrase extension and the incomplete phrase in the document collection;

selecting documents from the document collection containing the phrase extension; and

storing the selected documents in a memory as part of a search result.

2. The method of claim 1, wherein identifying an incomplete phrase and replacing the incomplete phrase comprise:

identifying a candidate phrase in the query;

matching the candidate phrase to an incomplete phrase in a list of incomplete phrases; and

replacing the candidate phrase with a phrase extension associated with the incomplete phrase.

3. A computer-implemented method of selecting documents in a document collection in response to a query, the method comprising:

receiving a query including a first phrase and a second phrase;

retrieving a posting list of documents containing the first phrase;

for each document in the posting list;

accessing a list indicating related phrases of the first phrase that are present in the document, the first phrase predicting the occurrence of each of the related phrases in the document collection, wherein the first phrase predicts a related phrase based on a measure of an actual co-occurrence rate of the related phrase and the first phrase exceeding an expected co-occurrence rate of the related phrase and the first phrase in the document collection, the expected co-occurrence rate of the related phrase and the first phrase being a function of a plurality of occurrences of the related phrase and the first phrase in the document collection;

responsive to the list of related phrases indicating that the second phrase is present in a document, selecting the document to include in a result to the query, without retrieving a posting list of documents containing the second phrase; and

storing the selected documents in a memory as part of a search result.

4. The method of claim 3, further comprising:

responsive to the list of related phrases indicating that the second phrase is a related phrase of the first phrase and is not present in a document, excluding the document from the result to the query, without retrieving a posting list of documents containing the second phrase.

5. The method of claim 3, further comprising:

responsive to the list of related phrases indicating that the second phrase is not a related phrase of the first phrase, intersecting the posting list of documents for the first phrase and with a posting list of documents for the second phrase to select documents containing both the first phrase and the second phrase.

6. The method of claim 3, further comprising:

storing the list of related phrases for a first phrase with respect to a document in a bit vector, wherein a bit of the bit vector is set for each related phrase of the first phrase that is present in the document, and a bit of the vector is unset for each related phrase of the first phrase that is not present in the document, wherein the bit vector has a numerical value; and

scoring a selected document by determining an adjusted value of the bit vector according to the bits set for related phrases of the first phrase that are present in the document.

7. A computer readable storage medium storing a computer program executable by a processor for selecting documents in a document collection in response to a query, the actions of the computer program comprising:

receiving a query;

identifying an incomplete phrase in the query, wherein other phrases predicted by the incomplete phrase in the document collection include only phrase extensions of the incomplete phrase;

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 co-occurrence rate of the phrase extension and the incomplete phrase exceeding an expected co-occurrence rate of the phrase extension and the incomplete phrase in the document collection, the expected co-occurrence rate of the phrase extension and the incomplete phrase being a function of a plurality of occurrences of the phrase extension and the incomplete phrase in the document collection;

selecting documents from the document collection containing the phrase extension; and

storing the selected documents in a memory as part of a search result.

8. A computer readable storage medium storing a computer program executable by a processor for selecting documents in a document collection in response to a query, the actions of the computer program comprising:

receiving a query including a first phrase and a second phrase;

retrieving a posting list of documents containing the first phrase;

for each document in the posting list;

accessing a list indicating related phrases of the first phrase that are present in the document, the first phrase predicting the occurrence of each of the related phrases in the document collection, wherein the first phrase predicts a related phrase based on a measure of an actual co-occurrence rate of the related phrase and the first phrase exceeding an expected co-occurrence rate of the related phrase and the first phrase in the document collection, the expected co-occurrence rate of the related phrase and the first phrase being a function of a plurality of occurrences of the related phrase and the first phrase in the document collection;

responsive to the list of related phrases indicating that the second phrase is present in a document, selecting the document to include in a result to the query, without retrieving a posting list of documents containing the second phrase; and

storing the selected documents in a memory as part of a search result.

9. A system for selecting documents in a document collection in response to a query, comprising:

a memory configured for storing a phrase data repository, comprising a list of incomplete phrases; and

a processor configured for operating a query processing module configured to cause an apparatus to;

receive a query;

identify, in the query, an incomplete phrase from the list of incomplete phrases, wherein other phrases predicted by the incomplete phrase in the document collection include only phrase extensions of the incomplete phrase;

replace 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 co-occurrence rate of the phrase extension and the incomplete phrase exceeding an expected co-occurrence rate of the phrase extension and the incomplete phrase in the document collection, the expected co-occurrence rate of the phrase extension and the incomplete phrase being a function of a plurality of occurrences of the phrase extension and the incomplete phrase in the document collection;

select documents from the document collection containing the phrase extension; and

store the selected documents in a memory as part of a search result.

10. A system for selecting documents in a document collection in response to a query, comprising:

a memory configured for storing a phrase-based index comprising a list of phrases and a plurality of phrase posting lists associated with a phrase from the list of phrases; and

a processor configured for operating a query processing module configured to cause an apparatus to;

receive a query including a first phrase and a second phrase;

retrieve, from the phrase-based index, a posting list of documents containing the first phrase;

for each document in the posting list;

access a list indicating related phrases of the first phrase that are present in the document, the first phrase predicting the occurrence of each of the related phrases in the document collection, wherein the first phrase predicts a related phrase based on a measure of an actual co-occurrence rate of the related phrase and the first phrase exceeding an expected co-occurrence rate of the related phrase and the first phrase in the document collection, the expected co-occurrence rate of the related phrase and the first phrase being a function of a plurality of occurrences of the related phrase and the first phrase in the document collection;

responsive to the list of related phrases indicating that the second phrase is present in a document, select the document to include in a result to the query, without retrieving a posting list of documents containing the second phrase; and

store the selected documents in a memory as part of a search result.