HYBRID-DISTRIBUTION MODEL FOR SEARCH ENGINE INDEXES

• US 20120130997A1
• Filed: 11/22/2010
• Published: 05/24/2012
• Est. Priority Date: 11/22/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: RISVIK, KNUT MAGNE, HOPCROFT, MICHAEL, KALYANARAMAN, KARTHIK, CHILIMBI, TRISHUL, WALTERS, CHAD P., PARIKH, VISHESH, PEDERSEN, JAN OTTO, BENNETT, JOHN
• Granted Patent: US 9,424,351 B2
• Time in Patent Office: Days
• US Class Current: 707/723
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results

Abstract

Methods and systems are provided for using a hybrid-distribution system to identify relevant documents based on a search query. A group of documents is assigned to a particular segment. The group of documents is indexed both by atom and by document to form a reverse index and a forward index. Both indexes are divided amongst each node in that segment so that each node is responsible for storing and accessing a different portion of both the reverse and forward indexes. The reverse index portion is accessed on each of a first set of nodes to identify a first set of documents that is relevant to a particular search query. Document identifications associated with the first set of documents are used to identify a second set of nodes that access their forward index portions to limit the number of relevant documents to a second set of documents.

Claims

1. One or more computer-storage media storing computer-useable instructions that, when used by a computing device, cause the computing device to perform a method for utilizing a hybrid-distribution system for identifying relevant documents based on a search query, the method comprising:

allocating a group of documents to a segment, the group of documents being indexed by atom in a reverse index and indexed by document in a forward index;

storing a different portion of the reverse index and the forward index on each of a plurality of nodes that form the segment;

accessing the reverse index portion stored on each of a first set of nodes to identify a first set of documents that is relevant to the search query; and

based on document identifications associated with the first set of documents, accessing the forward index portion stored on each of a second set of nodes to limit a quantity of relevant documents in the first set of documents to a second set of documents.

2. The computer-storage media of claim 1, wherein a node is a machine that is capable of performing ranking computations based on its stored reverse index portion and forward index portion.

3. The computer-storage media of claim 1, wherein a quantity of nodes in the second set of nodes is greater than the quantity of nodes in the first set of nodes.

4. The computer-storage media of claim 1, wherein the first set of documents is identified as being relevant to the search query by way of a preliminary ranking process that is part of a multistage ranking process, wherein the preliminary ranking process utilizes the reverse index portion.

5. The computer-storage media of claim 4, wherein each document in the second set of documents is contained in the first set of documents.

6. The computer-storage media of claim 5, wherein the second set of documents is identified by a final ranking process that is part of the overall ranking process, wherein the final ranking process utilizes the forward index portion.

7. The computer-storage media of claim 1, further comprising:

receiving the search query;

identifying one or more atoms in the search query; and

identifying the first set of nodes in the segment that contains at least one of the one or more atoms.

8. The computer-storage media of claim 1, wherein the forward index portion stored on each node in the second set of nodes contains at least one of the document identifications associated with the first set of documents.

9. The computer-storage media of claim 1, wherein the second set of documents from multiple segments are merged to generate a final set of documents that is presented to the user in response to the search query.

10. One or more computer-storage media storing computer-useable instructions that, when used by a computing device, cause the computing device to perform a method for generating a hybrid-distribution system for a multiprocess document-retrieval system, the method comprising:

receiving an indication of a group of documents assigned to a segment, the segment comprising a plurality of nodes;

for the segment,

(1) indexing the allocated group of documents by atom to generate a reverse index, and

(2) indexing the allocated group of documents by document to generate a forward index; and

assigning a portion of the reverse index and a portion of the forward index to each of a plurality of nodes that form the segment such that each of the plurality of nodes has stored a different portion of the forward index and a different portion of the reverse index.

11. The method of claim 10, further comprising:

at the segment, receiving an indication of one or more atoms that have been identified from a search query;

identifying a first set of nodes whose reverse index portions include at least one of the one or more atoms; and

identifying a first set of documents based in part on the reverse index portions of the first set of nodes.

12. The method of claim 11, further comprising:

identifying a second set of nodes whose forward index portions include one or more document identifications corresponding to the first set of documents; and

identifying a second set of documents based at least on data in the forward index portions.

13. The method of claim 11, wherein the first set of documents is identified based on a preliminary ranking process of a multistage ranking process that utilizes the reverse index portions.

14. The method of claim 12, wherein the second set of documents is identified based on a final ranking process of a multistage ranking process that utilizes the forward index portions.

15. The method of claim 12, wherein search results communicated for presentation to a user based on the search query are based on the second set of documents received from a plurality of segments.

16. One or more computer-storage media storing computer-useable instructions that, when used by a computing device, cause the computing device to perform a method for utilizing a hybrid-distribution system for identifying relevant documents based on a search query, the method comprising:

receiving a search query;

identifying one or more atoms in the search query;

communicating the one or more atoms to a plurality of segments that have each been assigned a group of documents that is indexed both by atom and by document such that a reverse index and a forward index generated and stored at each of the plurality of segments, wherein each of the plurality of segments is comprised of a plurality of nodes that are each assigned a portion of the forward index and the reverse index;

based on the one or more atoms, identifying a first set of nodes at a first segment whose reverse index portions contain at least one of the one or more atoms from the search query;

accessing the reverse index portion stored at each of the first set of nodes to identify a first set of documents that is found to be relevant to the one or more atoms;

based on document identifications associated with the first set of documents, identifying a second set of nodes whose forward index portions contain one or more of the document identifications associated with the first set of documents; and

accessing the forward index portion stored at each of the second set of nodes to identify a second set of documents that is a subset of the first set of documents.

17. The computer-storage media of claim 16, wherein the documents in the second set of documents are found to be the most relevant from the documents in the first set of documents.

18. The computer-storage media of claim 16, further comprising communicating for presentation search results to a user based on the second set of documents.

19. The computer-storage media of claim 16, further comprising receiving the second set of documents from each of the plurality of segments.

20. The computer-storage media of claim 19, further comprising merging each of the second set of documents to generate a merged list of relevant documents.