Systems and methods for inferring uniform resource locator (URL) normalization rules

• US 7,680,785 B2
• Filed: 03/25/2005
• Issued: 03/16/2010
• Est. Priority Date: 03/25/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Najork, Marc Alexander
• Primary Examiner(s): Cottingham; John R
• Assistant Examiner(s): Liu; Hexing
• Application Number:
  US11/089,988
• Publication Number:
  US 20060218143A1
• Time in Patent Office: 1,817 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9566 URL specific, e.g. using aliases, detecting broken or misspelled links
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

Different URLs that actually reference the same web page or other web resource are detected and that information is used to only download one instance of a web page or web resource from a web site. All web pages or web resources downloaded from a web server are compared to identify which are substantially identical. Once identical web pages or web resources with different URLs are found, the different URLs are then analyzed to identify what portions of the URL are essential for identifying a particular web page or web resource, and what portions are irrelevant. Once this has been done for each set of substantially identical web pages or web resources (also referred to as an “equivalence class” herein), these per-equivalence-class rules are generalized to trans-equivalence-class rules. There are two rule-learning steps: step (1), where it is learned for each equivalence class what portions of the URLs in that class are relevant for selecting the page and what portions are not; and step (2), where the per-equivalence-class rules constructed during step (1) are generalized to rules that cover many equivalence classes. Once a rule is determined, it is applied to the class of web pages or web resources to identify errors. If there are no errors, the rule is activated and is then used by the web crawler for future crawling to avoid the download of duplicative web pages or web resources.

Claims

1. A method for determining a rule applicable to uniform resource locators (URLs) corresponding to a plurality of web resources, comprising:

analyzing the content of web resources from at least one web site;

grouping web resources by content so that each group comprises all of the web resources from the at least one web site that have substantially identical content, wherein each group of substantially identical web resources is referred to as an equivalence class;

analyzing URLs corresponding to all substantially identical web resources in an equivalence class to determine a per equivalence class URL rewrite rule applicable to the URLs;

analyzing the per equivalence class URL rewrite rule compared to at least one other per equivalence class URL rewrite rule for at least one different equivalence class to determine a trans-equivalence class URL rewrite rule; and

applying the trans-equivalence class URL rewrite rule to additional web resources from the at least one website to predict that different URLs reference substantially identical web resources, thereby avoiding a plurality of references to or downloads of substantially identical web resources.

2. The method of claim 1, wherein analyzing the URLs corresponding to an equivalence class comprises identifying what portions of the URLs are essential to identify the substantially identical content, and what portions are irrelevant.

3. The method of claim 1, wherein analyzing URLs corresponding to an equivalence class to determine a per equivalence class rule comprises determining what portions of the URLs corresponding to the substantially identical web resources in the equivalence class are relevant to select the substantially identical content and what portions are not.

4. The method of claim 1, further comprising:

testing the trans-equivalence class rule by applying it to the plurality of equivalence classes to identify errors, and if there are no errors, then activating it for use by a web crawler to avoid downloading duplicative web resources.

5. The method of claim 1, wherein the per equivalence class rule is based on a recurring pattern in the URLs corresponding to the substantially identical web resources in the equivalence class.

6. The method of claim 1, wherein analyzing the content comprises comparing the content in the web resources.

7. The method of claim 6, wherein analyzing the content comprises at least one of shingling, check-summing, and lexical comparison.

8. The method of claim 1, further comprising testing the per equivalence class rule.

9. The method of claim 1, further comprising receiving the web resources from a web server prior to analyzing.

10. A system for determining a rule applicable to uniform resource locators (URLs) corresponding to a plurality of web resources, comprising:

a web crawler to receive the web resources from at least one web site on a web server; and

a processor to receive the content of the web resources, grouping web resources by content so that each group comprises all of the web resources from the at least one web site that have substantially identical content, wherein each group of substantially identical web resources is referred to as an equivalence class, analyzing URLs corresponding to all substantially identical web resources in an equivalence class to determine a per equivalence class URL rewrite rule applicable to the URLs;

analyzing the per equivalence class URL rewrite rule compared to at least one other per equivalence class URL rewrite rule for at least one different equivalence class to determine a trans-equivalence class URL rewrite rule; and

applying the trans-equivalence class URL rewrite rule to additional web resources from the at least one website to predict that different URLs reference substantially identical web resources, thereby avoiding receipt by the web crawler of substantially identical web resources.

11. The system of claim 10, wherein the processor is adapted to analyze the URLs corresponding to an equivalence class to identify what portions of the URLs are essential to identify the substantially identical content, and what portions are irrelevant.

12. The system of claim 10, wherein analyzing URLs corresponding to an equivalence class to determine a per equivalence class rule comprises determining what portions of the URLs corresponding to the substantially identical web resources in the equivalence class are relevant to select the substantially identical content and what portions are not.

13. The system of claim 12, wherein the processor is further adapted to:

test the trans-equivalence class rule by applying it to the plurality of equivalence classes to identify errors, and if there are no errors, then activate it for use by the web crawler to avoid downloading duplicative web resources.

14. The system of claim 10, wherein the processor is adapted to search for a recurring pattern in the URLs corresponding to the substantially identical web resources in the equivalence class.

15. The system of claim 14, wherein the processor is adapted to perform at least one of shingling, check-summing, and lexical comparison.

16. A method for determining a rule applicable to uniform resource locators (URLs), comprising:

grouping web resources on a web server according to substantially identical content, wherein each group of substantially identical web resources is referred to as an equivalence class;

analyzing URLs addressing all substantially identical web resources in an equivalence class;

constructing a per equivalence class URL normalization rule applicable to the URLs corresponding to all substantially identical web resources in the equivalence class;

analyzing the per equivalence class URL normalization rule compared to at least one other per equivalence class URL normalization rule for at least one different equivalence class to determine a trans-equivalence class URL normalization rule; and

applying the trans-equivalence class URL normalization rule to additional web resources to predict that different URLs reference substantially identical web resources, thereby avoiding a plurality of references to or downloads of substantially identical web resources.

17. The method of claim 16, wherein constructing the per equivalence class URL normalization rule comprises pattern matching.

18. The method of claim 16, further comprising validating the per equivalence class URL normalization rule.

19. The method of claim 16, wherein grouping web resources on a web server according to substantially identical content comprises at least one of shingling, check-summing, and lexical comparison.