Multiple index based information retrieval system

• US 9,361,331 B2
• Filed: 03/13/2013
• Issued: 06/07/2016
• Est. Priority Date: 07/26/2004
• Status: Active Grant

• 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/801,108
• Publication Number:
  US 20140095511A1
• Time in Patent Office: 1,182 Days
• Field of Search: 707/709, 707/705, 707/706, 707/736, 707/741, 707/749, 707/748, 707/765
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9538 Presentation of query results
• 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. The document index is partitioned into multiple indexes, including a primary index and a secondary index. The primary index stores phrase posting lists with relevance rank ordered documents. The secondary index stores excess documents from the posting lists in document order.

Claims

1. A computer implemented method of indexing documents of a document collection, wherein each indexed document has a document identifier, the method comprising:

storing a posting list of identifiers of documents of the document collection that contain a phrase;

partitioning the posting list, by operation of at least one processor, into at least a first portion including identifiers of higher ranked documents and a second portion including identifiers of lesser ranked documents, the partitioning being based on a relevance score for a document identified in the posting list indicating the document'"'"'s relevance to the phrase;

storing the first portion in a primary index; and

storing the second portion in a secondary index.

2. The method of claim 1, wherein the identifiers of the lesser ranked documents of the second portion being stored relative to one another in the secondary index in numerical order of the respective document identifiers of the ranked documents.

3. The method of claim 1, further comprising storing, for each identifier of a document in the first portion of the posting list relevance attributes of the document.

4. The method of claim 3, wherein the relevance attributes include at least one of the following:

a total number of occurrences of the phrase in the document, a rank ordered list of anchor documents that also contain the phrase and that point to the document, a position of each phrase occurrence in the document, a set of one or more flags indicating a format of the occurrence or a portion of the document containing the occurrence.

5. The method of claim 1, wherein storing the first portion in the primary index includes storing the first portion on a primary server, and wherein storing the second portion in the secondary index, includes storing the first portion on a secondary server that is different from the primary server.

6. The method of claim 1, further comprising:

receiving a query that relates to the phrase;

determining a result using the primary index and not the secondary index;

determining the result includes a sufficient set; and

ranking the documents in the result.

7. A non-transitory computer-readable storage medium storing a computer program executable by at least one processor for indexing documents, actions of the computer program comprising:

determining a set of documents related to a first phrase;

determining a relevance score for each of the documents in the set, the relevance score for a document indicating the document'"'"'s relevance to the first phrase;

partitioning the set of documents by the relevance scores into at least a first sub-set and a second sub-set, the first sub-set having relevance scores higher than the second sub-set;

generating a posting list for the first phrase partitioned across at least two tiers, the posting list comprising document entries that include a document identifier and the relevance score for the document, wherein a first tier stores document entries from the first sub-set and a second tier stores document entries from the second sub-set;

repeating the determining, partitioning, and generating for a second phrase; and

storing the posting lists in an index.

8. The computer-readable storage medium of claim 7, wherein the relevance score includes a page rank-based score.

9. The computer-readable storage medium of claim 7, wherein the posting lists of the index are distributed amongst a plurality of computing devices by a hash of a phrase for the posting list.

10. A computer based method executed by one or more processors, the method comprising:

receiving a search query, which includes at least a first phrase and a second phrase, at a server that is in communication with an index server system storing a plurality of posting lists, at least some of the posting lists being associated with a phrase and including document identifiers for documents containing the phrase, and

wherein the document identifiers in at least some posting lists are partitioned based on a relevance score that indicates a respective document'"'"'s relevance to the phrase of the posting list, such that a first portion of the posting list contains document identifiers of documents with a higher relevance score than documents identified in a second portion of the posting list;

responsive to the first phrase having a partitioned posting list and the second phrase having a partitioned posting list, intersecting the first portion of the posting list of the first phrase with the first portion of the posting list of the second phrase;

determining that the intersection includes a sufficient result set; and

ranking the documents in the result set.

11. The computer based method of claim 10, further comprising:

determining that the intersection fails to include a sufficient result set; and

intersecting the second portion of the posting list for the first phrase with the first portion of the posting list for the second phrase; and

including the intersection of the second portion and the first portion in the result set.

12. The computer based method of claim 10, wherein the first portion has a maximum quantity of document identifiers and the second portion has a remainder of the document identifiers.

13. The computer based method of claim 12, wherein when a quantity of document identifiers in a posting list fails to meet the maximum, the posting list is not partitioned.

14. The method of claim 10, wherein the intersection occurs without accessing the second portion of the posting list of the first phrase or the second portion of the posting list of the second phrase.

15. The method of claim 10, wherein the posting lists are distributed intersection occurs without accessing the second portion of the posting list of the first phrase or the second portion of the posting list of the second phrase.