Method and apparatus for finding mirrored hosts by analyzing urls

• US 6,286,006 B1
• Filed: 05/07/1999
• Issued: 09/04/2001
• Est. Priority Date: 05/07/1999
• Status: Expired due to Term

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: AltaVista Company (Apollo Global Management, Inc.)
• Inventors: Broder, Andrei, Dean, Jeffrey, Bharat, Krishna A., Glassman, Steven C., Henzinger, Monika R.
• Primary Examiner(s): Breene, John
• Assistant Examiner(s): Le, Debbie M
• Application Number:
  US09/307,320
• Time in Patent Office: 851 Days
• Field of Search: 707/5, 707/100, 707/10, 709/230, 709/203
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method and apparatus that detects mirrored host pairs using information about a large set of pages, including URLs. The identities of the detected mirrored hosts are then saved so that browsers, crawlers, proxy servers, or the like can correctly identify mirrored web sites. The described embodiments of the present invention look at the URLs of pages hosts to determine whether the hosts are potentially mirrored.

Claims

1. A method of determining mirrored web hosts, comprising:

receiving information about the addresses of a plurality of web sites stored on a plurality of hosts;

determining a plurality of terms of the URLs associated with every host;

weighting the terms in inverse proportion to frequency;

determining a similarity score for host pair in accordance with the weighted terms; and

outputting a list of potential pairs of mirrored hosts in accordance with their similarity scores.

2. The method of claim 1, wherein the terms include “

n-grams”

having two or more contiguous tokens from the URLs.

3. The method of claim 1, wherein the terms include “

n-grams”

having two or more continuous tokens from the URLs and URL depth information for the tokens.

4. The method of claim 1, wherein the terms include paths of the URLs.

5. The method of claim 1, wherein the terms include substrings of the paths of the URLs.

6. The method of claim 1, wherein the terms are placed in a <

term,host>

tuple and the tuples are sorted by the terms.

7. The method of claim 1, wherein the terms include prefixes of the URLs.

8. The method of claim 1, wherein the similarity scores are normalized.

9. The method of claim 1, further comprising accessing pages on each host corresponding to paths selected from both hosts to determine whether the hosts are mirrored hosts.

10. The method of claim 9, wherein the hosts are mirrored if at least a predetermined number of path matches occurs for the selected paths.

11. The method of claim 1, further comprising:

attempting to access selected pages on each host of a host pair, the pages corresponding to paths selected from each host, to determine whether the hosts are mirrored hosts;

categorizing the pages as having various matching categories; and

categorizing the host pairs in one of a plurality of similarity categories in accordance with the matching categories of the selected pages.

12. The method of claim 11, wherein the matching categories indicate one of:

access of the path on a source host failed;

access of the path on a target host failed;

content is byte-wise identical;

documents are 100% similar after removal of;

common content above a threshold for high similarity; and

path is valid but no similarity.

13. The method of claim 11, wherein the host pairs are divided into five similarity categories in accordance with the matching categories of the pages.

14. An apparatus that determines mirrored web hosts, comprising:

software configured to receive information about the addresses of a plurality of web sites stored on a plurality of hosts;

software configured to determine a plurality of terms of the URLs associated with every host;

software configured to weight the terms in inverse proportion to frequency;

software configured to determine a similarity score for host pair in accordance with the weighted terms; and

software configured to output a list of potential pairs of mirrored hosts in accordance with their similarity scores.

15. The apparatus of claim 14, wherein the terms include “

n-grams”

having pairs of contiguous tokens from the URLs.

16. The apparatus of claim 14, wherein the terms include “

n-grams”

having pairs of continuous tokens from the URLs and URL depth information for the tokens.

17. The apparatus of claim 14, wherein the terms include paths of the URLs.

18. The apparatus of claim 14, wherein the terms include substrings of the paths of the URLS.

19. The apparatus of claim 14, wherein the terms include prefixes of the URLs.

20. The apparatus of claim 14, wherein the similarity scores are normalized.

21. A computer program product, comprising:

computer program code devices configured to receive information about the addresses of a plurality of web sites stored on a plurality of hosts;

computer program code devices configured to determine a plurality of terms of the URLs associated with every host;

computer program code devices configured to weight the terms in inverse proportion to frequency;

computer program code devices configured to determine a similarity score for host pair in accordance with the weighted terms; and

computer program code devices configured to output a list of potential pairs of mirrored hosts in accordance with their similarity scores.