Efficient forward ranking in a search engine

• US 8,713,024 B2
• Filed: 11/22/2010
• Issued: 04/29/2014
• 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, Bennett, John G., Kalyanaraman, Karthik, Chilimbi, Trishul, Walters, Chad P., Parikh, Vishesh, Pedersen, Jan Otto
• Primary Examiner(s): Saeed, Usmaan
• Assistant Examiner(s): Kim, Paul
• Application Number:
  US12/951,747
• Publication Number:
  US 20120130995A1
• Time in Patent Office: 1,254 Days
• Field of Search: 707/741, 707/706, 707/736, 707/737
• US Class Current: 707/741
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Methods and computer storage media are provided for generating entries for documents in a forward index. A document and its document identification are received, in addition to static features that are query-independent. The document is parsed into tokens to form a token stream corresponding to the document. Relevant data used to calculate rankings of document is identified and a position of the data is determined. The entry is then generated from the document identification, the token stream of the document, the static features, and the positional information of the relevant data. The entry is stored in the forward index.

Claims

1. A computer-implemented method for generating an entry in a forward index, the method being performed by one or more computing devices including at least one processor and one or more computer storage media, the method comprising:

receiving a document and a corresponding document identification;

receiving one or more static features associated with the document, wherein the one or more static features are unrelated to a search query;

parsing the document into tokens to form a token stream of the document;

determining positional information from a position in the document of one or more relevant data, wherein the positional information is a relative location of an atom in the document

identifying one or more context streams corresponding to the document, wherein the one or more context streams represent individual sections of the document;

calculating stream offsets for the one or more context streams parsed from the document, wherein each stream offset provides a specific location of a context stream of the document;

generating the entry from the document identification, the stream offsets, the token stream of the document, the static features, and the positional information, wherein the document identification is a pointer to the starting point of the document that corresponds to the token stream of the document, the stream offsets, the static features, and the positional information for the document; and

storing the entry in the forward index.

2. The method of claim 1, wherein the one or more context streams include one or more of a title, anchor, header, body, traffic, class, attributes, and uniform resource locator (URL).

3. The method of claim 1, wherein the one or more relevant data are frequently used in calculating rankings of documents in response to receiving a search query.

4. The method of claim 1, wherein the entry is a data structure.

5. The method of claim 1, wherein the positional data is determined so that the one or more relevant data can be easily accessed when a search query is submitted and results are determined.

6. The method of claim 1, further comprising:

receiving a search query;

receiving an indication that the document associated with the generated entry in the forward index is relevant to the search query, wherein the relevancy is determined by using a reverse index that is indexed by atoms;

creating a token map of the search query, the token map including query tokens;

scanning the token stream of the document to identify if any document tokens match any of the query tokens; and

updating a data structure with a position in the token stream of any matches.

7. One or more computer storage media having stored thereon a data structure for storing data representing a forward index that is used to rank search results based on a search query, the data structure comprising:

a first data field containing document identification information that identifies a particular document;

a second data field containing a compressed token stream of the document, wherein the compressed token stream is a second token stream based on a first token stream, the compressed token stream is a compressed version of the token stream comprising context streams of the document selected from the first token stream, wherein the one or more context streams represent individual portions of the document;

a third data field containing document-specific data representing static features of the document that are used to rank the document when a query is received; and

a fourth data field containing positional information that indicates the position of one or more relevant data associated with the document that is frequently used to calculate a ranking of the document.

8. The one or more computer storage media of claim 7, wherein the static features are unrelated to the query.

9. The one or more computer storage media of claim 7, wherein the static features include one or more of page rank, language, total anchor count, and type of page.

10. The one or more computer storage media of claim 7, wherein the second data field further contains separate token streams of one or more portions of the document.

11. The one or more computer storage media of claim 10, wherein the one or more portions of the document include one or more of a title, anchor, header, body, traffic, class, attributes, and uniform resource locator (URL).

12. A computer-implemented method for generating an entry in a forward index, the method being performed by one or more computing devices including at least one processor and one or more computer storage media, the method comprising:

receiving a document and a corresponding document identification, wherein the document identification is configured to point to a starting location of the document in the forward index;

receiving one or more static features associated with the document, wherein the one or more static features are supplementary features associated with document and are unrelated to a potential search query;

parsing the document into tokens to form a token stream of the document;

creating a compressed token stream based on the formed token stream, wherein the compressed token stream is a second token stream based on the token stream, the compressed token stream is a compressed version of the token stream comprising context streams of the document selected from the first token stream, wherein the one or more context streams represent individual sections of the document;

upon creating the compressed token stream, calculating stream offsets for the context streams in the compressed token, wherein each stream offset provides a specific location of a context stream of the document;

determining positional information from a position in the document of one or more relevant data, wherein the positional information is the relative location of an atom in the document

generating the entry from the document identification, the token stream of the document, the compressed token stream, the stream offsets, the static features, and the positional information, wherein the document identification is a pointer to the starting location of the document that corresponds to at least the compressed token stream; and

storing the entry in the forward index.

13. The method of claim 12, wherein the one or more relevant data are frequently used in calculating rankings of documents in response to receiving a search query.

14. The method of claim 12, further comprising:

receiving a search query;

receiving an indication that the document associated with the generated entry in the forward index is relevant to the search query, wherein the relevancy is determined by using a reverse index that is indexed by atoms;

creating a token map of the search query, the token map including query tokens;

scanning the compressed token stream of the document to identify if any document tokens match any of the query tokens; and

updating a data structure with a position in the token stream of any matches.