System and method for incorporating anchor text into ranking search results

• US 7,739,277 B2
• Filed: 09/30/2004
• Issued: 06/15/2010
• Est. Priority Date: 09/30/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zaragoza, Hugo, Robertson, Stephen Edward, Meyerzon, Dmitriy, Taylor, Michael J.
• Primary Examiner(s): Mofiz; Apu M
• Assistant Examiner(s): Le; Hung D
• Application Number:
  US10/955,462
• Publication Number:
  US 20060074871A1
• Time in Patent Office: 2,084 Days
• Field of Search: 715/500, 704/9, 704/231, 704/10, 709/224, 707/1, 707/204, 707/9
• US Class Current: 707/726
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results

Abstract

Search results of a search query on a network are ranked according to a scoring function that incorporates anchor text as a term. The scoring function is adjusted so that a target document of anchor text reflect the use of terms in the anchor text in the target document'"'"'s ranking. Initially, the properties associated with the anchor text are collected during a crawl of the network. A separate index is generated that includes an inverted list of the documents and the terms in the anchor text. The index is then consulted in response to a query to calculate a document'"'"'s score. The score is then used to rank the documents and produce the query results.

Claims

1. A computer-implemented method for presenting a ranking of search results, comprising:

providing an index to a plurality of documents including;

a main index associating with each of the documents a frequency of one or more terms being included in each of the documents;

an anchor text index associating with each of the documents an anchor text frequency of the one or more terms being included in anchor text in a source document referencing each of the documents;

receiving a query including at least one query term;

applying the query to the index to yield results of the query identifying one or more of the documents that include the at least one query term;

applying a scoring function to generate a score for each of the one or more documents included in the results of the query, wherein the scoring function (score) includes one of;

$\mathrm{score}=\sum <br><br>\frac{\left(\frac{\mathrm{wtf}}{B}+\frac{{\mathrm{wtf}}_{\mathrm{Anchor}}}{B_{\mathrm{Anchor}}}\right)<br><br>\left(k_1+1\right)}{k_1<br><br>\left(\left(1-b\right)+b<br><br>\frac{w<br><br>d<br><br>l}{\mathrm{avw}<br><br>d<br><br>l}\right)+\left(\mathrm{wtf}+{\mathrm{wtf}}_{\mathrm{Anchor}}\right)}\times <br><br>\log <br><br>\left(\frac{N}{n}\right);<br><br><br><br>\mathrm{and}$ $\mathrm{score}=\sum <br><br>\frac{\left(\frac{\mathrm{wtf}}{B}+\frac{{\mathrm{wtf}}_{\mathrm{Anchor}}}{B_{\mathrm{Anchor}}}\right)<br><br>\left(k_1+1\right)}{k_1+\left(\frac{\mathrm{wtf}}{B}+\frac{{\mathrm{wtf}}_{\mathrm{Anchor}}}{B_{\mathrm{Anchor}}}\right)}\times <br><br>\log <br><br>\left(\frac{N}{n}\right),$

where;

wtf is a weighted term frequency applying a weight to a frequency with which a given query term is included in the document;

wtf_Anchor is a weighted term frequency applying a weight to a frequency with which the given query term is included in anchor text referencing the document;

k₁ is a constant;

b is a constant;

wdl is a weighted document length applying a weight to a length of the document being scored;

avwdl is an average weighted document length of all documents being scored;

N is the number of documents on the network; and

n is the number of documents including at least one appearance of a given query term; and

generating an output of the ranked results of the query to be displayed to a user.

2. The computer-implemented method of claim 1, further comprising building the index by processing each of the plurality of documents to determine the frequency of the one or more terms included in the document.

3. The computer-implemented method of claim 2, further comprising building the index by processing each of the plurality of documents to identify one or more anchor text entries each referencing another document.

4. The computer-implemented method of claim 3, further comprising generating an anchor text table, wherein an entry is made for each of the documents including an anchor text entry, including one or more of:

a source identifier indicating the document including the anchor text entry;

a target identifier indicating a target document the anchor text entry references; and

one or more terms included in content of the anchor text entry.

5. The computer-implemented method of claim 4, further comprising generating the index by collecting for each of the documents:

the frequency of the one or more terms included in the document; and

for each of the anchor table entries in which the document is listed as the target document of the target identifier, a frequency of the terms listed in the content of the anchor text entry.

6. The computer-implemented method of claim 1, further comprising ranking the documents according to a scoring function (score) that is determined based on terms including:

a weighted anchor term frequency (wtf_Anchor); and

an anchor text length normalization component (B_Anchor) derived from;

a weighted document length (wdl); and

an average weighted document length (avwdl).

7. The computer-implemented method of claim 1, wherein when the document is not associated with anchor text data, the scoring function (score) includes:

$\mathrm{score}=\sum <br><br>\frac{\mathrm{wtf}<br><br>\left(k_1+1\right)}{k_1<br><br>\left(\left(1-b\right)+b<br><br>\frac{\mathrm{wdl}}{\mathrm{avwdl}}\right)+\mathrm{wtf}}\times <br><br>\log <br><br>\left(\frac{N}{n}\right).$

8. The computer-implemented method of claim 1, wherein a strength of the length normalization provided by B_Anchor is adjusted by choosing a different constant value associated with B_Anchor.

9. A computer-readable storage medium storing instructions executable on a computing system, comprising instructions to:

evaluate contents of each of a plurality of documents on a network, including;

recording a frequency of terms included within the document;

making an entry in an anchor text table for each anchor text entry referencing another document;

compile an index, including;

generating a main index that associates with each of the documents a frequency with which the at least one term is included in the document;

generating an anchor text index that associates with each of the documents a frequency of terms listed in anchor text entries in the anchor text table referencing the document;

receive a query including at least one query term;

apply the query to the index to yield results of the query identifying one or more of the documents that include the at least one query term;

apply applying a scoring function to generate a score for each of the one or more documents included in the results of the query, applying a scoring function to generate a score for each of the one or more documents included in the results of the query, wherein the scoring function (score) includes one of;

$\mathrm{score}=\sum <br><br>\frac{\left(\frac{\mathrm{wtf}}{B}+\frac{{\mathrm{wtf}}_{\mathrm{Anchor}}}{B_{\mathrm{Anchor}}}\right)<br><br>\left(k_1+1\right)}{k_1<br><br>\left(\left(1-b\right)+b<br><br>\frac{w<br><br>d<br><br>l}{\mathrm{avw}<br><br>d<br><br>l}\right)+\left(\mathrm{wtf}+{\mathrm{wtf}}_{\mathrm{Anchor}}\right)}\times <br><br>\log <br><br>\left(\frac{N}{n}\right);<br><br><br><br>\mathrm{and}$ $\mathrm{score}=\sum <br><br>\frac{\left(\frac{\mathrm{wtf}}{B}+\frac{{\mathrm{wtf}}_{\mathrm{Anchor}}}{B_{\mathrm{Anchor}}}\right)<br><br>\left(k_1+1\right)}{k_1+\left(\frac{\mathrm{wtf}}{B}+\frac{{\mathrm{wtf}}_{\mathrm{Anchor}}}{B_{\mathrm{Anchor}}}\right)}\times <br><br>\log <br><br>\left(\frac{N}{n}\right),$

where;

wtf is a weighted term frequency applying a weight to a frequency with which a given query term is included in the document;

wtf_Anchor is a weighted term frequency applying a weight to a frequency with which the given query term is included in anchor text referencing the document;

k₁ is a constant;

b is a constant;

wdl is a weighted document length applying a weight to a length of the document being scored;

avwdl is an average weighted document length of all documents being scored;

N is the number of documents on the network; and

n is the number of documents including at least one appearance of a given query term; and

generate an output of the ranked results of the query to be displayed to a user.

10. The computer-readable storage medium of claim 9, wherein making the entry in the anchor text table for each of the documents includes:

storing for a source identifier indicating the document including the anchor text entry;

storing a target identifier indicating a target document the anchor text entry references; and

storing one or more terms included in content of the anchor text entry.

11. The computer-readable storage medium of claim 9, wherein when the document is not associated with anchor text data, the scoring function (score) includes:

$\mathrm{score}=\sum <br><br>\frac{\mathrm{wtf}<br><br>\left(k_1+1\right)}{k_1<br><br>\left(\left(1-b\right)+b<br><br>\frac{\mathrm{wdl}}{\mathrm{avwdl}}\right)+\mathrm{wtf}}\times <br><br>\log <br><br>\left(\frac{N}{n}\right).$

12. The computer-readable storage medium of claim 9, wherein a strength of the length normalization provided by B_Anchor is adjusted by choosing a different constant value associated with B_Anchor.

13. The computer-readable storage medium of claim 9, further comprising causing an output of the ranked results of the query to be presented to a user.

14. A search engine system, comprising:

a processor;

an index for a plurality of documents, including;

a main index associating with each of the documents a frequency of one or more terms being included in each of the documents;

an anchor text index associating with each of the documents an anchor text frequency of the one or more terms being included in anchor text in a source document referencing each of the documents;

a ranking system, including;

a query interface configured to receive a query including at least one query term and apply the query to the index to identify one or more of the documents that include the at least one query term;

a scoring function to generate a score for each of the one or more documents included in the results of the query, wherein the scoring function (score) includes;

Score=Σ

(wtf/B+wtf<sub>—

anchor</sub>/B<sub>—

ancho</sub>r)(k1+1)*log(N/n) (k1+(wtf/B)+(wtf<sub>—

ancho</sub>r/B<sub>—

anchor</sub>)

where;

wtf is a weighted term frequency applying a weight to a frequency with which a given query term is included in the document;

wtf_Anchor is a weighted term frequency applying a weight to a frequency with which the given query term is included in anchor text referencing the document;

k1 is a constant;

wdl is a weighted document length applying a weight to a length of the document being score;

avwdl is an average weighted document length of all documents being scored;

B is a document length normalization component defined as B=((1−

b)+b*wdl/avwdl) where b is a constant;

BAnchor is an anchor text normalization component defined as B=((1−

b)+b*wdl/avwdl) where b is a constant;

N is the number of documents on the network; and

n is the number of documents including at least one appearance of a given query term;

a ranking system configured to rank the results of the query based on the score generated for each of the documents included in the results of the query.

15. The system of claim 14, further comprising a crawler configured to building the main index by processing each of the plurality of documents to determine the frequency of the one or more terms included in the document.

16. The system of claim 15, wherein the crawler is further configured to build the anchor text index by processing each of the plurality of documents to identify one or more anchor text entries each referencing another document.

17. The system of claim 16, wherein the crawler is further configured to generate an anchor text table, wherein an entry is made for each of the documents including an anchor text entry, including one or more of:

a source identifier indicating the document including the anchor text entry;

a target identifier indicating a target document the anchor text entry references; and

one or more terms included in content of the anchor text entry.

18. The system of claim 17, wherein the crawler is further configured to generate the index by collecting for each of the documents:

the frequency of the one or more terms included in the document; and

for each of the anchor table entries in which the document is listed as the target document of the target identifier, a frequency of the terms listed in the content of the anchor text entry.