LINK BASED RANKING OF SEARCH RESULTS USING SUMMARIES OF RESULT NEIGHBORHOODS

• US 20090234829A1
• Filed: 03/11/2008
• Published: 09/17/2009
• Est. Priority Date: 03/11/2008
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Gollapudi, Sreenivas, Panigrahy, Rina, Najork, Marc A.
• Application Number:
  US12/045,716
• Publication Number:
  US 20090234829A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A summary of the neighborhood of a page may be determined offline and used at query time to approximate the neighborhood graph of the result set and to compute scores using the approximate neighborhood graph. The summary of the neighborhood graph may include a Bloom filter containing a limited size subset of ancestors or descendants of the page. A web page identifier may also be included in the summary. Consistent sampling is used, where a consistent unbiased sample of a number of elements from the set is determined. At query time, given a result set, the summaries for all the results may be used to create a cover set. An approximate neighborhood graph consisting of the vertices in the cover set is created. Ranking technique scores may be determined based on the approximate neighborhood graph.

Claims

1. A computer-implemented method, comprising:

using consistent sampling to determine a summary of the neighborhood of each webpage of a plurality of webpages; and

estimating the relevance of results to a query using the summaries of the webpages corresponding to the results.

2. The method of claim 1, wherein the summary of each web page is based on a summary of the pages that link to a first page and a summary of pages that the first page links to.

3. The method of claim 2, further comprising:

consistently sampling x elements from a set of pages that link to the first page wherein the same x elements are sampled from the set each time the set is sampled; and

consistently sampling y elements from a set of pages that the first page links to wherein the same y elements are sampled from the set each time the set is sampled.

4. The method of claim 3, further comprising:

sampling x of the pages that link to the first page and y of the pages that the first page links to using min-wise independent hashing.

5. The method of claim 3, further comprising:

subsampling z elements from the consistent sample of x elements and the consistent sample of y elements.

6. The method of claim 5, further comprising:

representing the sampled elements using compact identifiers to denote web pages.

7. The method of claim 6, further comprising:

storing the sampled x elements from the set of pages that link to the first page in a first Bloom filter;

storing the sampled y elements from the set of pages that the first page links to in a second Bloom filter; and

storing the subsampled z elements in a list.

8. The method of claim 5, further comprising:

receiving a result set for the query;

determining summaries for the results within the result set;

determining a cover set as the union of the subsampled z elements contained in each summary;

determining an approximate neighborhood graph in accordance with vertices in the cover set; and

determining an authority score.

9. The method of claim 8, wherein the summaries are determined in advance of receiving the query.

10. The method of claim 8, wherein the authority score is determined using a Stochastic Approach for Link-Structure Analysis (SALSA) technique.

11. A computer-implemented method, comprising:

receiving a result set for a query;

determining a plurality of summaries for a plurality of results within the result set;

determining a cover set;

determining an approximate neighborhood graph; and

determining an authority score.

12. The method of claim 11, further comprising:

consistently sampling elements of an inlinking set to a uniform resource locator (URL) in the results and elements of an outlinking set from the URL in the results to determine the summaries.

13. The method of claim 12, further comprising:

determining a Bloom Filter for elements of the inlinking set and elements of the outlinking set; and

adding an edge to the approximate neighborhood graph if the Bloom filter of the inlinking set includes a vertex or if the Bloom filter of the outlinking set includes the vertex.

14. The method of claim 12, further comprising:

determining the approximate neighborhood graph using an approximation of the inlinking set and an approximation of the outlinking set to the URL; and

applying a Bloom filter to a subset of the inlinking set and to a subset of the outlinking set to determine the approximation of the inlinking set and the approximation of the outlinking set.

15. A computing system, comprising:

a search engine that determines a summary for each page in a web graph based on an approximation of an inlinking set and an approximation of an outlinking set, the search engine receiving a query containing a search term and providing a result set responsive to the query;

a database that stores the summary for each page; and

a scoring engine that determines an authority score based on an approximate neighborhood graph determined based on the summary for each page.

16. The computing system of claim 15, wherein consistently sampled elements of an inlinking set to a uniform resource locator (URL) associated with each page and consistently sampled elements of an outlinking set from the URL associated with each page are used to determine the summaries.

17. The computing system of claim 15, wherein a Bloom filter for elements of the approximation of the inlinking set and a Bloom filter of the elements of the approximation of the outlinking set is determined.

18. The computing system of claim 17, wherein an edge is added to the approximated neighborhood graph if the Bloom filter of the inlinking set includes a vertex or if the Bloom filter of the outlinking set includes the vertex.

19. The computing system of claim 15, wherein a Bloom filter is applied to a subset of the inlinking set and to a subset of the outlinking set to determine the approximation of the inlinking set and the approximation of the outlinking set.

20. The computing system of claim 19, wherein a web page identifier is added to the approximation of the inlinking set and to the approximation of the outlinking set.