Multiple index based information retrieval system

• US 10,671,676 B2
• Filed: 11/10/2017
• Issued: 06/02/2020
• Est. Priority Date: 07/26/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Patterson, Anna L.
• Primary Examiner(s): Vy, Hung T
• Application Number:
  US15/809,356
• Publication Number:
  US 20180101528A1
• Time in Patent Office: 935 Days
• Field of Search: 707736, 707741, 704 9
• 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-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 plurality of posting lists being associated with a phrase and including document identifiers for documents containing the phrase, and wherein the document identifiers in the 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 lacking a partitioned posting list;

intersecting the first portion of the posting list of the first phrase with the posting list of the second phrase to generate a first set of common documents, and

intersecting the second portion of the posting list of the first phrase with the posting list of the second phrase to generate a second set of common documents;

ranking the documents in a combination of the first set of common documents and the second set of common documents; and

providing highest ranked documents in the combination as search results for the search query.

2. The computer-based method of claim 1, wherein ranking the documents includes calculating a function of a body hit score and an anchor hit score.

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

4. The computer-based method of claim 3, wherein the posting list of the second phrase is not partitioned because a quantity of document identifiers in the posting list fails to meet the maximum quantity.

5. The computer-based method of claim 1, wherein the at least some posting lists include an indication of a frequency of occurrence for each phrase.

6. The computer-based method of claim 1, wherein the plurality of posting lists are distributed.

7. The computer-based method of claim 6, wherein the first portion of the posting list is distributed across first machines based on a hash function related to the phrase.

8. The computer-based method of claim 7, wherein the second portion of the posting list is distributed across second machines based on a second hash function related to the phrase.

9. A search system comprising:

a primary index storing a first portion for each of a plurality of posting lists, each posting list being associated with a respective phrase;

a secondary index storing a second portion for at least some of the plurality of posting lists, wherein the first portion of a posting list for a phrase includes document identifiers of documents with a higher relevance score than documents identified in the second portion of the posting list for the phrase, the relevance score indicating a respective document'"'"'s relevance to the phrase;

at least one processor; and

memory storing instructions that, when executed by the at least one processor cause the search system to perform operations including;

receive a search query that includes at least a first phrase and a second phrase,

responsive to determining that the first phrase has a posting list with a first portion and a second portion and that the second phrase has a posting list with a first portion but not a second portion;

intersect the first portion of the posting list of the first phrase with the posting list of the second phrase to generate a first set of common documents, and

intersect the second portion of the posting list of the first phrase with the posting list of the second phrase to generate a second set of common documents,

rank the documents in a combination of the first set of common documents and the second set of common documents, and

provide highest ranked documents in the combination as search results for the search query.

10. The search system of claim 9, wherein ranking the documents includes calculating a function of a body hit score and an anchor hit score.

11. The search system of claim 9, wherein the first portion has a maximum quantity of document identifiers and the second portion has a remainder of the document identifiers.

12. The search system of claim 11, wherein the posting list of the second phrase is not partitioned because a quantity of document identifiers in the posting list fails to meet the maximum quantity.

13. The search system of claim 9, wherein the primary index includes an indication of a frequency of occurrence for each phrase.

14. The search system of claim 9, wherein the plurality of posting lists are distributed.

15. The search system of claim 14, wherein the first portion of the posting list is distributed across first machines based on a hash function related to the phrase.

16. The search system of claim 15, wherein the second portion of the posting list is distributed across second machines based on a second hash function related to the phrase.