Multiple index based information retrieval system

• US 8,560,550 B2
• Filed: 07/20/2009
• Issued: 10/15/2013
• 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): Vy, Hung T
• Application Number:
  US12/506,088
• Publication Number:
  US 20100030773A1
• Time in Patent Office: 1,548 Days
• Field of Search: 707/705, 707/706, 707/736, 707/741, 707/749, 707/748, 707/765, 707/766, 707/767, 707/999.003, 707/999.005, 715/762
• US Class Current: 707/741
• 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 comprising at least one phrase at a server that is in communication with an index server system that includes;

(a) a primary index server system that stores a primary index including primary phrase posting lists, each primary phrase posting list being associated with a phrase and including up to a maximum number of documents that contain the phrase and comprising references to documents in rank order based on relevance of the phrase to each respective document and (b) a secondary index server system including secondary phrase posting lists, each secondary phrase posting list being associated with a primary phrase posting list in the primary index, and including documents that contain the phrase that is associated with the primary phrase posting list in the primary index and which have relevance scores less than the relevance score of a lowest ranked document in the primary posting list for the 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 to provide a result set; and

ranking the common documents in the result set.

2. The method of claim 1, wherein the relevance scores are based on the relevance of the phrase to the respective document.

3. The method of claim 2, wherein the relevance scores of the documents are also based on a page rank type score for the documents.

4. The method of claim 2, wherein the relevance scores of the documents are also based on a number of inlinks in the documents.

5. The method of claim 2, wherein the relevance scores of the documents are also based on document lengths for the documents.

6. The method of claim 1, further comprising storing, for for documents of a phrase posting list of the primary index, at least one relevance attribute of the document.

7. The method of claim 6, wherein the at least one relevance attribute includes at least one of:

a total number of occurrences of the posting list 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.

8. The method of claim 6, wherein the secondary phrase posting lists store substantially only document identification information.

9. An information retrieval system for retrieving information from a corpus of documents, the system comprising:

a primary index server system comprising a primary index, the primary index including primary phrase posting lists, each primary phrase posting list being associated with a phrase and including up to a maximum number of documents of the corpus that contain the phrase, the documents being ranked relative to one another in the primary index in rank order by respective relevance scores; and

a secondary index server system comprising a secondary index, the secondary index including secondary phrase posting lists, each secondary phrase posting list being associated with a primary phrase posting list in the primary index, and including documents that contain the phrase that is associated with the primary phrase posting list in the primary index and which have relevance scores less than the relevance score of a lowest ranked document in the primary phrase posting list for the phrase,

wherein the primary index server system comprises multiple machines, and wherein each phrase is assigned an identification number and has a primary phrase posting list located on one of the machines.

10. The system of claim 9, wherein the primary index stores, for each document, at least one relevance attribute of the document.

11. The system of claim 9, wherein the secondary phrase posting lists of the secondary index store substantially only document identification information.

12. The system of claim 9, wherein each primary phrase posting list in the primary index 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 a 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.

13. The system of claim 10, wherein the at least one relevance attribute includes at least one of:

a total number of occurrences of the posting list 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.

14. The system of claim 9, wherein the identification number for a phrase is a function of a frequency of occurrence of the phrase in the corpus.

15. The system of claim 14, wherein a first phrase that occurs more frequently in the corpus that a second phrase has a lower identification number than the second phrase.

16. The system of claim 9, wherein phrase posting lists for different phrases are distributed across the machines by a hash function.

17. The system of claim 16, wherein the hash function is function of a modulus of the identification number of the phrase of the phrase posting list and a number of the machines.

18. The system of claim 9, wherein the primary phrase posting lists are ordered as a function of the number of documents in each posting list.

19. The system of claim 9, wherein for primary phrase posting lists that are associated with a secondary phrase posting list, the primary phrase posting list includes an identifier indicating a reference to the secondary index server system.

20. An information retrieval system, comprising:

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

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

a front end server configured to receive a search query that includes at least one phrase; and

a search server configured, in response 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, to intersect 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 to intersect 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 conjoin the first and second sets of common documents, and to rank the common documents.

21. The information retrieval system of claim 20, wherein the relevance scores comprise a page rank based type score.

22. The information retrieval system of claim 21, wherein for each document in a phrase posting list of the primary index, at least one relevance attribute of the document is stored in association with the phrase posting list.

23. The information retrieval system of claim 22, wherein the at least one relevance attribute includes at least one of:

a total number of occurrences of the posting list 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.

24. The information retrieval system of claim 22, wherein the secondary phrase posting lists store substantially only document identification information.

25. An information retrieval system for indexing documents with respect to a first phrase, wherein each document has a document identifier, the system comprising:

a primary index server system storing primary phrase posting lists;

a secondary index server system storing secondary phrase posting lists,

an index server system configured for;

ranking the documents in the list by a relevance score;

storing a first portion of the list comprising higher ranked documents in the primary index server system, the higher ranked documents of the first portion stored relative to one another in the primary index server system in rank order of the respective relevance scores of the ranked documents, wherein the first portion 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 a second plurality of relevance attributes that are a 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; and

storing a second portion of the list comprising lesser ranked documents in the secondary index server system, the lesser ranked documents of the second portion stored relative to one another in the secondary index server system in numerical order of the respective document identifiers of the ranked documents.

26. The system of claim 25, wherein the first portion of each list of documents includes a third section wherein each document 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.

27. The system of claim 25, 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 section of the list contains 1*n entries, wherein 1>

4.

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

receiving a search query, which includes at least one phrase, at a server that is in communication with an index server system storing a plurality of phrase posting lists, each phrase posting list being associated with a phrase and including document identifiers for documents containing the phrase, and wherein the document identifiers in at least some phrase posting lists are partitioned based on a relevance score indicating 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 for which the phrase of the posting list has more relevance than documents identified in a second portion of the posting list,

responsive to the search query containing a first phrase having a partitioned posting list and a second phrase having a partitioned posting list, intersecting the first portion of the posting list of the first phase with the first portion of the posting list of the second phrase without processing the remainders of each of the respective posting lists, to identify a result set of documents having the first phrase and the second phrase; and

ranking the documents in the result set.

29. The method of claim 28, further comprising storing, for documents of a phrase posting list, at least one relevance attribute of the document.

30. The method of claim 28, wherein the first portions of the posting lists include at least one relevance attribute of the documents identified in the first portions of the posting lists.

31. The method of claim 30, wherein the at least one relevance attribute includes at least one of:

a total number of occurrences of the posting list 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.

32. The method of claim 30, wherein the at least one relevance attribute is stored in the phrase posting list for the phrase.

33. The method of claim 28, wherein the relevance scores of the documents are based, at least in part, on a page rank type score for the documents.

34. The method of claim 28, wherein the relevance scores of the documents are based, at least in part, on a number of inlinks in the documents.

35. The method of claim 28, wherein the relevance scores of the documents are based, at least in part, on document lengths for the documents.

36. An information retrieval system for retrieving information from a corpus of documents, the system comprising:

a front end server configured for receiving a search query, which includes at least one phrase; and

an index server system storing a plurality of posting lists, each phrase posting list being associated with a phrase and including document identifiers for documents containing the phrase, wherein the document identifiers in at least some phrase posting lists are partitioned based on a relevance score indicating 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 for which the phrase of the posting list has more relevance than documents identified in a second portion of the posting list,

wherein, the index server system is configured to, responsive to the search query containing a first phrase having a partitioned posting list and a second phrase having a partitioned posting list, intersect the first portion of the posting list of the first phase with the first portion of the posting list of the second phrase without processing the remainders of each of the respective posting lists, to identify a result set of documents having the first phrase and the second phrase.

37. The information retrieval system of claim 36, further comprising a ranking server configured for ranking the documents in the result set.

38. The information retrieval system of claim 37, wherein the front end server includes the ranking server.

39. The information retrieval system of claim 36, wherein the index server system is further configured for storing, for documents of a phrase posting list, at least one relevance attribute of the document.

40. The information retrieval system of claim 36, wherein the first portions of the posting lists include at least one relevance attribute of the documents identified in the first portions of the posting lists.

41. The information retrieval system of claim 40, wherein the at least one relevance attribute includes at least one of:

a total number of occurrences of the posting list 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.

42. The information retrieval system claim 40, wherein the at least one relevance attribute is stored in the phrase posting list for the phrase.

43. The information retrieval system of claim 36, wherein the relevance scores of the documents are based, at least in part, on a page rank type score for the documents.

44. The information retrieval system of claim 36, wherein the relevance scores of the documents are based, at least in part, on a number of inlinks in the documents.

45. The information retrieval system of claim 36, wherein the relevance scores of the documents are based, at least in part, on document lengths for the documents.