Phrase-based searching in an information retrieval system

• US 20060031195A1
• Filed: 07/26/2004
• Published: 02/09/2006
• 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
• Granted Patent: US 7,599,914 B2
• Time in Patent Office: Days
• 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 method of selecting documents in a document collection in response to a query, the method comprising:

receiving a query;

identifying a plurality of phrases in the query, wherein at least one phrase is a multiple word phrase;

identifying a phrase extension of at least one of the identified phrases; and

selecting documents from the document collection containing at one phrase from a set including phrases in the query and the phrase extension.

2. The method of claim 1, wherein selecting documents comprises:

combining a posting list of an identified phrase and a posting list of the phrase extension of the identified phrase to form a combined posting list; and

selecting documents appearing in the combined posting list and in the posting lists of the other identified phrases.

3. A 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;

replacing the incomplete phrase with a phrase extension; and

selecting documents from the document collection containing the phrase extension.

4. The method of claim 3, 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.

5. The method of claim 3, wherein a phrase extension of an incomplete phrase comprises a super-sequence of the incomplete phrase that begins with the incomplete phrase.

6. A method of selecting documents in a document collection in response to a query, the method comprising:

receiving a query including a first phrase and 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; and

responsive to the list of related phrase 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.

7. The method of claim 6, further comprising:

responsive to the list of related phrases indicating that the second phrase 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.

8. The method of claim 6, 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.

9. The method of claim 6, 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.

10. A method of ranking documents included in a search result in response to a query, the query comprising at least one query phrase, the method comprising:

for each document in the search result, accessing a related phrase bit vector for a query phrase, wherein each bit of the bit vector indicates the presence or absence of a related phrase of the query phrase; and

sorting the documents in the search results by the value of their related phrase bit vectors, such the document with the highest value related phrase bit vector is ranked highest in the search result.

11. The method of claim 10, wherein:

each bit of the related phrase bit vector is associated with a related phrase of the query phrase; and

the bits are ordered such that a most significant bit of the bit vector is associated with a related phrase having a greatest information gain with respect to the query phrase, and a least significant bit is associated with a related phrase having the least information gain with respect to the query phrase.

12. A method of ranking documents included in a search result in response to a query, the query comprising at least one query phrase, the method comprising:

for each document in the search result;

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

for each bit indicating the presence of a related phrase of the query phrase, adding a predetermined number of points associated with the bit to a score for the document; and

sorting the documents in the search results by their document scores.

13. The method of claim 12, wherein:

each bit of the related phrase bit vector is associated with a related phrase of the query phrase;

the bits are ordered such that a most significant bit of the bit vector is associated with a related phrase having a greatest information gain with respect to the query phrase, and a least significant bit is associated with a related phrase having the least information gain with respect to the query phrase; and

the predetermined number of points associated with each bit range from a most number points associated with the most significant bit to a least number of points associated with a least significant bit.

14. A method of providing an information retrieval system, the method comprising:

automatically identifying valid phrases in a document collection comprising a plurality of documents, wherein the valid phrases contain multiple word phrases;

indexing the documents according to valid phrases contained in the documents;

receiving a search query;

identifying phrases contained in the query;

selecting documents according to the identified phrases; and

ranking the selected documents according to the identified phrases.