Identifying internet protocol addresses for internet hosting entities

• US 8,688,681 B1
• Filed: 06/17/2010
• Issued: 04/01/2014
• Est. Priority Date: 06/17/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Xiao, Li, Mukherjee, Arup
• Primary Examiner(s): Nguyen, Loan T
• Application Number:
  US12/817,695
• Time in Patent Office: 1,384 Days
• Field of Search: None
• US Class Current: 707/709
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/955 using information identifiers, e.g. uniform resource locators [URL]
• CPC Class Codes: G06F 7/00 Methods or arrangements for processing data by operating upon the order or content of the data handled logic circuits H03K19/00
• CPC Class Codes: H04L 61/4511 using domain name system [DNS]

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for identifying web hosting entities. In one aspect, a system includes one or more computers programmed to perform operations including maintaining an Internet Protocol (IP) address history for each hostname in a plurality of hostnames. Each IP address history is a time series of IP addresses. The operations further include organizing the hostnames into a collection of groups so that each hostname of the plurality of hostnames is a member of exactly one group in the collection of groups. Each group has a kernel calculated from the IP address histories of the members of the group, and the IP address history of each member of the group is within a threshold distance of the kernel of the group.

Claims

1. A system comprising one or more computers programmed to perform operations comprising:

maintaining an Internet Protocol (IP) address history for each hostname in a plurality of hostnames, where each IP address history is a time series of IP addresses;

organizing the hostnames into a collection of groups so that each hostname of the plurality of hostnames is a member of exactly one group in the collection of groups, where each group has a kernel calculated from the IP address histories of the members of the group, and where the IP address history of each member of the group is within a threshold distance of the kernel of the group;

providing to a crawler, for use in scheduling a crawl of the plurality of hostnames, data describing the collection of groups;

receiving an update to an IP address history for a first hostname of the plurality of hostnames, the first hostname being a member of a first group of the collection of groups, and recalculating a first kernel of the first group using the updated IP address history of the first hostname;

receiving an update to an IP address history for a second hostname, the second hostname being a member of a second group of the collection of groups, and recalculating a second kernel of the second group using the updated IP address history of the second hostname; and

determining that the first kernel is within the threshold distance of the second kernel and, as a result, merging the first group and the second group into a single group in the collection of groups.

2. The system of claim 1, wherein the operations further comprise:

selecting a crawling schedule of the first group or the second group for use with the merged single group, where hostnames of the first and second groups are associated with respective numbers of Uniform Resource Locators (URLs) and the selected crawling schedule is chosen to minimize a total number of URLs that are changed to a new crawling schedule as a result of the selection.

3. The system of claim 1, wherein the operations further comprise selecting the first group and the second group for merging based on the first group having a highest number of edges in a star topology, the edges connecting the first group to one or more candidate groups that are candidates for merging with the first group, the candidate groups including the second group.

4. The system of claim 3, wherein the candidate groups include a candidate group that does not have a threshold amount of data within the IP address histories, and, as a result, the candidate group does not contribute to the number of edges for the first group.

5. The system of claim 1, wherein the operations further comprise determining from the IP address histories that the first group and the second group include dynamic IP addresses, and wherein determining that the first kernel is within the threshold distance of the second kernel comprises comparing a longer portion of the first kernel and the second kernel than is compared for groups having static IP addresses.

6. The system of claim 1, wherein the operations further comprise determining from the IP address histories that the first group includes static IP addresses and, as a result, the merging is performed after a predetermined delay.

7. The system of claim 1, wherein the operations further comprise determining that the first group includes more than a predetermined number of sitenames and, as a result, the combining is performed without delay.

8. The system of claim 1, wherein the operations further comprise performing the step of receiving the updates to the IP address histories for the first and second hostnames at a first network location and at a second network location.

9. A computer-implemented method comprising:

maintaining an Internet Protocol (IP) address history for each hostname in a plurality of hostnames, where each IP address history is a time series of IP addresses;

organizing the hostnames into a collection of groups so that each hostname of the plurality of hostnames is a member of exactly one group in the collection of groups, where each group has a kernel calculated from the IP address histories of the members of the group, and where the IP address history of each member of the group is within a threshold distance of the kernel of the group;

providing to a crawler, for use in scheduling a crawl of the plurality of hostnames, data describing the collection of groups;

receiving an update to an IP address history for a first hostname of the plurality of hostnames, the first hostname being a member of a first group of the collection of groups, and recalculating a first kernel of the first group using the updated IP address history of the first hostname;

receiving an update to an IP address history for a second hostname, the second hostname being a member of a second group of the collection of groups, and recalculating a second kernel of the second group using the updated IP address history of the second hostname; and

determining that the first kernel is within the threshold distance of the second kernel and, as a result, merging the first group and the second group into a single group in the collection of groups.

10. The method of claim 9, wherein the operations further comprise:

selecting a crawling schedule of the first group or the second group for use with the merged single group, where hostnames of the first and second groups are associated with respective numbers of Uniform Resource Locators (URLs) and the selected crawling schedule is chosen to minimize a total number of URLs that are changed to a new crawling schedule as a result of the selection.

11. The method of claim 9, wherein the operations further comprise selecting the first group and the second group for merging based on the first group having a highest number of edges in a star topology, the edges connecting the first group to one or more candidate groups that are candidates for merging with the first group, the candidate groups including the second group.

12. The method of claim 11, wherein the candidate groups include a candidate group that does not have a threshold amount of data within the IP address histories, and, as a result, the candidate group does not contribute to the number of edges for the first group.

13. The method of claim 9, wherein the operations further comprise determining from the IP address histories that the first group and the second group include dynamic IP addresses, and wherein determining that the first kernel is within the threshold distance of the second kernel comprises comparing a longer portion of the first kernel and the second kernel than is compared for groups having static IP addresses.

14. The method of claim 9, wherein the operations further comprise determining from the IP address histories that the first group includes static IP addresses and, as a result, the merging is performed after a predetermined delay.

15. A non-transitory computer storage medium having instructions stored thereon that, when executed by data processing apparatus, cause the data processing apparatus to perform operations comprising:

maintaining an Internet Protocol (IP) address history for each hostname in a plurality of hostnames, where each IP address history is a time series of IP addresses;

organizing the hostnames into a collection of groups so that each hostname of the plurality of hostnames is a member of exactly one group in the collection of groups, where each group has a kernel calculated from the IP address histories of the members of the group, and where the IP address history of each member of the group is within a threshold distance of the kernel of the group;

providing to a crawler, for use in scheduling a crawl of the plurality of hostnames, data describing the collection of groups;

receiving an update to an IP address history for a first hostname of the plurality of hostnames, the first hostname being a member of a first group of the collection of groups, and recalculating a first kernel of the first group using the updated IP address history of the first hostname;

receiving an update to an IP address history for a second hostname, the second hostname being a member of a second group of the collection of groups, and recalculating a second kernel of the second group using the updated IP address history of the second hostname; and

determining that the first kernel is within the threshold distance of the second kernel and, as a result, merging the first group and the second group into a single group in the collection of groups.

16. The non-transitory computer storage medium of claim 15, wherein the operations further comprise:

selecting a crawling schedule of the first group or the second group for use with the merged single group, where hostnames of the first and second groups are associated with respective numbers of Uniform Resource Locators (URLs) and the selected crawling schedule is chosen to minimize a total number of URLs that are changed to a new crawling schedule as a result of the selection.

17. The non-transitory computer storage medium of claim 15, wherein the operations further comprise selecting the first group and the second group for merging based on the first group having a highest number of edges in a star topology, the edges connecting the first group to one or more candidate groups that are candidates for merging with the first group, the candidate groups including the second group.

18. The non-transitory computer storage medium of claim 17, wherein the candidate groups include a candidate group that does not have a threshold amount of data within the IP address histories, and, as a result, the candidate group does not contribute to the number of edges for the first group.

19. The non-transitory computer storage medium of claim 15, wherein the operations further comprise determining from the IP address histories that the first group and the second group include dynamic IP addresses, and wherein determining that the first kernel is within the threshold distance of the second kernel comprises comparing a longer portion of the first kernel and the second kernel than is compared for groups having static IP addresses.

20. The non-transitory computer storage medium of claim 15, wherein the operations further comprise determining from the IP address histories that the first group includes static IP addresses and, as a result, the merging is performed after a predetermined delay.

21. The non-transitory computer storage medium of claim 15, wherein the operations further comprise determining that the first group includes more than a predetermined number of sitenames and, as a result, the combining is performed without delay.

22. The non-transitory computer storage medium of claim 15, wherein the operations further comprise performing the step of receiving the updates to the IP address histories for the first and second hostnames at a first network location and at a second network location.