Multiple index based information retrieval system

• US 20060106792A1
• Filed: 01/25/2005
• Published: 05/18/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 L.
• Granted Patent: US 7,567,959 B2
• Time in Patent Office: Days
• 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 for indexing documents with respect to a phrase, wherein each document as a document identifier, the method comprising:

establishing a list of documents that contain the phrase;

ranking the documents in the list by a relevance score;

storing a first portion of the list comprising higher ranked documents in a primary index in rank order of the relevance scores; and

storing a second portion of the list comprising lesser ranked documents in a secondary index in numerical order of the document identifiers.

2. The method of claim 1, wherein the relevance score comprises a page rank based type score.

3. The method of claim 1, further comprising storing for each document in the primary index 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 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 flag indicating a format of the occurrence or a portion of the document containing the occurrence.

5. The method of claim 3, wherein storing the second portion of the list in the secondary index comprises storing substantially only document identification information.

6. The method of claim 1, wherein storing the first portion of the list in a primary index comprises storing the first portion of the list on a physical storage device in rank order of the relevance scores.

7. The method of claim 1, wherein storing a second portion of the list in a secondary index comprises storing the second portion of the list on a physical storage device in numerical order of the document identifiers.

8. The method of claim 1, wherein the first portion of each list of documents includes a first section wherein each document listed in the first section includes a first plurality of relevance attributes, and a second section wherein each document listed in the second section comprises second plurality of relevance attributes that are subset of the first set of relevance attributes, and wherein the documents listed in the first section are ranked higher than the documents listed in the second section.

9. The method of claim 8, wherein the first portion of each list of documents includes a third section wherein each documents listed in the third section includes a third plurality of relevance attributes that are a subset of the second plurality of relevance attributes, and wherein the documents listed in the second section are ranked higher than the documents listed in the third section.

10. The method of claim 8, wherein the first portion of each list contain n entries, wherein the second portion of the list contain m*n entries, wherein m>

2, and the third portion of the list contains l*n entries, wherein 1>

4.

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

storing a primary index including primary phrase posting lists, each posting list associated with a phrase and including up to a maximum number documents that contain the phrase, the documents rank ordered by respective relevance scores;

storing a secondary index including secondary phrase posting lists, each posting list associated with a primary phrase posting list in the primary index, and including documents that contain the phrase and which have relevance scores less than the relevance score of a lowest ranked document in the primary posting list for the phrase, the documents ordered by document identifier;

receiving a search query comprising at least one phrase;

responsive to the search query containing a first phrase having a primary posting list and a secondary posting list and a second phrase having only a primary posting list, intersecting the primary posting list of the first phrase with the primary posting list of the second phrase to obtain a first set of common documents, and intersecting the secondary posting list of the first phrase with the primary posting list of the second phrase to obtain a second set of common documents, and conjoining the first and second sets of common documents; and

ranking the common documents.

12. An information retrieval system, comprising:

a primary index including primary phrase posting lists, each posting list associated with a phrase and including up to a maximum number documents that contain the phrase, the documents rank ordered by respective relevance scores; and

a secondary index including secondary phrase posting lists, each posting list associated with a primary phrase posting list in the primary index, and including documents that contain the phrase and which have relevance scores less than the relevance score of a lowest ranked document in the primary posting list for the phrase, the documents ordered by document identifier.