Evaluating IP-location mapping data

• US 9,197,595 B1
• Filed: 05/04/2012
• Issued: 11/24/2015
• Est. Priority Date: 05/04/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Sandler, Mark M., Duleba, Krzysztof, van Dijk, Luuk, Erdei, Andras
• Primary Examiner(s): Wasel, Mohamed
• Assistant Examiner(s): WU, TSUNG YIN
• Application Number:
  US13/464,797
• Time in Patent Office: 1,299 Days
• Field of Search: 705 731- 737, 706 45- 62, 709/245, 709/246
• US Class Current: 1/1
• CPC Class Codes: H04L 61/5007 Internet protocol [IP] addresses
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal

Abstract

Among other disclosed subject matter, a computer-implemented method includes receiving a first, a second and a third network address mapping. The method includes mapping each of the network addresses in the first, second and third network address mappings to respective first, second and third locations. The method includes determining, for each of the network addresses in the first, second and third network address mappings, location agreements. The method includes determining a first and second network address mapping agreement rate, a first and third network address mapping agreement rate, and a second and third network address mapping agreement rate, respectively based on location agreements determined for each of the network addresses. The method includes determining a confidence level associated with the first network address mapping based on the agreement rates.

Claims

1. A computer-implemented method comprising:

receiving, by one or more processors, a first, a second and a third network address mapping, each of the first, second and third network address mappings containing a plurality of common network addresses and one or more associated geographical locations to which each network address is mapped;

mapping, by the one or more processors, each of the network addresses in the first, second and third network address mappings to respective first, second and third geographical locations;

determining, by the one or more processors, for each of the network addresses in the first, second and third network address mappings, a first and second location agreement, a first and third location agreement, and a second and third location agreement;

for each network address mapping pair, determining, by the one or more processors, a pair-wise agreement rate including a first and second network address mapping agreement rate, a first and third network address mapping agreement rate, and a second and third network address mapping agreement rate, respectively based on the first and second location agreements, the first and third location agreements, and the second and third location agreements determined for each of the network addresses, wherein each agreement rate for the pairs of network address mappings represents a probability that, for each common network address in the pair, first geographical locations associated with the common network addresses in a first network address mapping in the pair are equal to or substantially equal to second geographical locations associated with the common network addresses in a second network address mapping in the pair;

determining, by the one or more processors, a confidence level associated with the first network address mapping based on the first and second network address mapping agreement rate, the first and third network address mapping agreement rate, and the second and third network address mapping agreement rate; and

when the confidence level is less than a predetermined threshold, providing, by the one or more processors, an indication to adjust the first network address mapping.

2. The computer-implemented method of claim 1, further comprising determining a confidence level for at least one of the second or third network address mappings based on the first and second network address mapping agreement rate, the first and third network address mapping agreement rate, and the second and third network address mapping agreement rate.

3. The computer-implemented method of claim 1, wherein the network addresses in each of the network address mappings are IP addresses or MAC addresses, and wherein the first, second, and third network address mapping are generated from three different respective server-side sources communicating with user devices at the IP addresses or MAC addresses, and wherein the respective agreement rates are based on an amount of mappings that agree between respective pairs of network address mappings per common mapping between the respective pairs of network address mappings.

4. The computer-implemented method of claim 1, wherein determining, for each of the network addresses in the first, second and third network address mappings, a first and second location agreement, a first and third location agreement, and a second and third location agreement further comprises respectively determining that the first and second geographical locations, the first and third geographical locations, and the second and third geographical locations are at least one of (a) the same geographical location, (b) adjacent geographical locations, or (c) geographical locations separated by a threshold distance.

5. The computer-implemented method of claim 1, wherein the first network address mapping maps each of the plurality of network addresses to a plurality of geographical locations at a respective plurality of probabilities, and wherein mapping each of the plurality of network addresses in the first network address mapping to a first geographical location comprises mapping each of the plurality of network addresses to the most probable of the plurality of geographical locations.

6. The computer implemented method of claim 1, wherein the first network address mapping maps each of the plurality of network addresses to a plurality of geographical locations at a respective plurality of probabilities, and wherein mapping each of the plurality of network addresses in the first network address mapping to a first geographical location comprises mapping each of the plurality of network addresses to a random one of the plurality of geographical locations.

7. The computer-implemented method of claim 1, wherein the first network address mapping, the second network address mapping, and the third network address mapping are statistically independent, and wherein the agreement rates are determined, at least in part, by counting numbers of mappings that agree between respective pairs of network address mappings and dividing the numbers of mappings that agree by respective numbers of common IP-addresses that were mapped in the respective pairs of network address mappings.

8. The computer-implemented method of claim 1, wherein the first, second and third geographical locations comprise longitude and latitude coordinates, zip code information, town information, neighborhood information, county information, street address information, or country information.

9. The computer-implemented method of claim 1, wherein the confidence level associated with the first network address mapping is based on

10. The computer-implemented method of claim 1, wherein the second network address mapping and the third network address mapping are derived from user account information, advertiser account information, wireless Internet access point information or licensed data.

11. A system comprising:

memory; and

one or more processors coupled to the memory and perform operations comprising;

receiving a first, a second and a third network address mapping, each of the first, second and third network address mappings containing a plurality of common network addresses and one or more associated geographical locations to which each network address is mapped;

mapping each of the network addresses in the first, second and third network address mappings to respective first, second and third geographical locations;

determining, for each of the network addresses in the first, second and third network address mappings, a first and second location agreement, a first and third location agreement, and a second and third location agreement;

for each network address mapping pair, determining a pair-wise agreement rate including a first and second network address mapping agreement rate, a first and third network address mapping agreement rate, and a second and third network address mapping agreement rate, respectively based on the first and second location agreements, the first and third location agreements, and the second and third location agreements determined for each of the network addresses, wherein each agreement rate for the pairs of network address mappings represents a probability that, for each common network address in the pair, first geographical locations associated with the common network addresses in a first network address mapping in the pair are equal to or substantially equal to second geographical locations associated with the common network addresses in a second network address mapping in the pair;

determining a confidence level associated with the first network address mapping based on the first and second network address mapping agreement rate, the first and third network address mapping agreement rate, and the second and third network address mapping agreement rate; and

when the confidence level is less than a predetermined threshold, providing an indication to adjust the first network address mapping.

12. The system of claim 11, wherein the operations further comprise:

determining a confidence level for at least one of the second or third network address mappings based on the first and second network address mapping agreement rate, the first and third network address mapping agreement rate, and the second and third network address mapping agreement rate.

13. The system of claim 11, wherein the network addresses in each of the network address mappings are IP addresses or MAC addresses, and wherein the first, second, and third network address mapping are generated from three different respective server-side sources communicating with user devices at the IP addresses or MAC addresses, and wherein the respective agreement rates are based on an amount of mappings that agree between respective pairs of network address mappings per common mapping between the respective pairs of network address mappings.

14. The system of claim 11, wherein determining, for each of the network addresses in the first, second and third network address mappings, a first and second location agreement, a first and third location agreement, and a second and third location agreement further comprises respectively determining that the first and second geographical locations, the first and third geographical locations, and the second and third geographical locations are at least one of (a) the same geographical location, (b) adjacent geographical locations, or (c) geographical locations separated by a threshold distance.

15. The system of claim 11, wherein the first network address mapping maps each of the plurality of network addresses to a plurality of geographical locations at a respective plurality of probabilities, and wherein mapping each of the plurality of network addresses in the first network address mapping to a first geographical location comprises mapping each of the plurality of network addresses to the most probable of the plurality of geographical locations.

16. The system of claim 11, wherein the first network address mapping maps each of the plurality of network addresses to a plurality of geographical locations at a respective plurality of probabilities, and wherein mapping each of the plurality of network addresses in the first network address mapping to a first geographical location comprises mapping each of the plurality of network addresses to a random one of the plurality of geographical locations.

17. The system of claim 11, wherein the first network address mapping, the second network address mapping, and the third network address mapping are statistically independent, and wherein the agreement rates are determined, at least in part, by counting numbers of mappings that agree between respective pairs of network address mappings and dividing the numbers of mappings that agree by respective numbers of common IP-addresses that were mapped in the respective pairs of network address mappings.

18. The system of claim 11, wherein the first, second and third geographical locations comprise longitude and latitude coordinates, zip code information, town information, neighborhood information, county information, street address information, or country information.

19. The system of claim 11, wherein the confidence level associated with the first network address mapping is based on

20. The system of claim 11, wherein the second network address mapping and the third network address mapping are derived from user account information, advertiser account information, wireless Internet access point information or licensed data.

21. A non-transitory computer-readable medium storing instructions that upon execution by a processing device cause the processing device to perform operations, comprising:

receiving a first, a second and a third network address mapping, each of the first, second and third network address mappings containing a plurality of common network addresses and one or more associated geographical locations to which each network address is mapped;

mapping each of the network addresses in the first, second and third network address mappings to respective first, second and third geographical locations;

determining, for each of the network addresses in the first, second and third network address mappings, a first and second location agreement, a first and third location agreement, and a second and third location agreement;

for each network address mapping pair, determining a pair-wise agreement rate including a first and second network address mapping agreement rate, a first and third network address mapping agreement rate, and a second and third network address mapping agreement rate, respectively based on the first and second location agreements, the first and third location agreements, and the second and third location agreements determined for each of the network addresses, wherein each agreement rate for the pairs of network address mappings represents a probability that, for each common network address in the pair, first geographical locations associated with the common network addresses in a first network address mapping in the pair are equal to or substantially equal to second geographical locations associated with the common network addresses in a second network address mapping in the pair;

determining a confidence level associated with the first network address mapping based on the first and second network address mapping agreement rate, the first and third network address mapping agreement rate, and the second and third network address mapping agreement rate; and

when the confidence level is less than a predetermined threshold, providing an indication to adjust the first network address mapping.

22. The computer-readable medium of claim 21, wherein the operations further comprise determining a confidence level for at least one of the second or third network address mappings based on the first and second network address mapping agreement rate, the first and third network address mapping agreement rate, and the second and third network address mapping agreement rate.

23. The computer-readable medium of claim 21, wherein the network addresses in each of the network address mappings are IP addresses or MAC addresses, and wherein the first, second, and third network address mapping are generated from three different respective server-side sources communicating with user devices at the IP addresses or MAC addresses, and wherein the respective agreement rates are based on an amount of mappings that agree between respective pairs of network address mappings per common mapping between the respective pairs of network address mappings.

24. The computer-readable medium of claim 21, wherein determining, for each of the network addresses in the first, second and third network address mappings, a first and second location agreement, a first and third location agreement, and a second and third location agreement further comprises respectively determining that the first and second geographical locations, the first and third geographical locations, and the second and third geographical locations are at least one of (a) the same geographical location, (b) adjacent geographical locations, or (c) geographical locations separated by a threshold distance.

25. The computer-readable medium of claim 21, wherein the first network address mapping maps each of the plurality of network addresses to a plurality of geographical locations at a respective plurality of probabilities, and wherein mapping each of the plurality of network addresses in the first network address mapping to a first geographical location comprises mapping each of the plurality of network addresses to the most probable of the plurality of geographical locations.

26. The computer-readable medium of claim 21, wherein the first network address mapping maps each of the plurality of network addresses to a plurality of geographical locations at a respective plurality of probabilities, and wherein mapping each of the plurality of network addresses in the first network address mapping to a first geographical location comprises mapping each of the plurality of network addresses to a random one of the plurality of geographical locations.

27. The computer-readable medium of claim 21, wherein the first network address mapping, the second network address mapping, and the third network address mapping are statistically independent, and wherein the agreement rates are determined, at least in part, by counting numbers of mappings that agree between respective pairs of network address mappings and dividing the numbers of mappings that agree by respective numbers of common IP-addresses that were mapped in the respective pairs of network address mappings.

28. The computer-readable medium of claim 21, wherein the first, second and third geographical locations comprise longitude and latitude coordinates, zip code information, town information, neighborhood information, county information, street address information, or country information.

29. The computer-readable medium of claim 21, wherein the confidence level associated with the first network address mapping is based on

30. The computer-readable medium of claim 21, wherein the second network address mapping and the third network address mapping are derived from user account information, advertiser account information, wireless Internet access point information or licensed data.

31. A computer-implemented method comprising:

receiving, at one or more processors, a first evaluation set, a second evaluation set and a first data set,

wherein the first data set comprises a first set of IP addresses and geographical locations, wherein each IP address is associated with a respective geographical location,

wherein the first evaluation set comprises a second set of IP addresses and geographical locations, wherein each IP address in the second set of IP addresses is associated with a respective geographical location, and

wherein the second evaluation set comprises a third set of IP addresses and geographical locations, wherein each IP address in the third set of IP addresses is associated with a respective geographical location;

selecting, by the one or more processors, an IP address from the first evaluation set;

forming, by the one or more processors, a first subset from the first data set, a first evaluation subset from the first evaluation set and a second evaluation subset from the second evaluation set based on the selected IP address;

determining, by the one or more processors a confidence level associated with the first data set based on agreement rates associated with the first subset and the first and second evaluation subsets, wherein the confidence level is based on a probability that a geographical location associated with a particular IP address included in the first data set is accurate, wherein each agreement rate represents, for each pair of subsets from the first subset, the first evaluation subset, and the second evaluation subset, a probability that, for each common IP address in the pair, first geographical locations associated with the common IP addresses in a first subset in the pair are equal to or substantially equal to second geographical locations associated with the common IP addresses in a second subset in the pair; and

generating, by the one or more processors, a report based on the confidence level associated with the first data set, wherein when the confidence level is less than a predetermined threshold the report includes an indication to adjust the first data set.

32. The computer-implemented method of claim 31, wherein the first set of IP addresses, the second set of IP addresses and the third set of IP addresses all have a subset of IP addresses in common.

33. The computer-implemented method of claim 31, further comprising:

analyzing the first evaluation set and the second evaluation set to determine whether the first evaluation set is smaller than the second evaluation set; and

selecting the IP address from the first evaluation set based on a determination that the first evaluation set is smaller than the second evaluation set.

34. The computer-implemented method of claim 33, wherein forming the first subset, the first evaluation subset and the second evaluation subset comprises:

determining whether the selected IP address is included in the second evaluation set and in the first data set; and

based on a determination that the selected IP address is included in the second evaluation set and in the first data set;

adding the selected IP address and the corresponding geographical location from the first evaluation set to the first evaluation subset;

adding the selected IP address and the corresponding geographical location from the second evaluation set to the second evaluation subset; and

adding the selected IP address and the corresponding geographical location from the first data set to the first subset.

35. The computer-implemented method of claim 34, wherein forming the first subset, the first evaluation subset and the second evaluation subset comprises:

based on a determination that the selected IP address is not included in the second evaluation set;

analyzing the second evaluation set to identify a substitute IP address, wherein the substitute IP address comprises a closest IP address based on a prefix match criteria and wherein the substitute IP address is associated with an Internet service provider associated with the selected IP address;

adding the substitute IP address and the corresponding geographical location from the second evaluation set to the second evaluation subset; and

adding the selected IP address and the corresponding geographical location from the first evaluation set to the first evaluation subset.

36. The computer-implemented method of claim 31, wherein the first data set, the first evaluation set and the second evaluation set are statistically independent.

37. The computer-implemented method of claim 31, wherein the geographical location comprises longitude and latitude information, zip code information, town information, neighborhood information, street address information, or country information.

38. The computer-implemented method of claim 31, wherein the confidence level associated with the first data set is based on

39. The computer-implemented method of claim 38, wherein the confidence level associated with the first data set is based on:

40. The computer-implemented method of claim 31, wherein the confidence level associated with the first data set is based on:

Agreement(X,Y)=P(X_is_right and Y_is_right|IP)+P(X_is_wrong and Y_is_wrong and the geolocations are equal|IP);

Agreement(X,Z)=P(X_is_right and Z_is_right|IP)+P(X_is_wrong and Z_is_wrong and the geolocations are equal|IP); and

Agreement(Y,Z)=P(Y_is_right and Z_is_right|IP)+P(Y_is_wrong and Z_is_wrong and the geolocations are equal|IP), wherein

Agreement (X, Y) represents an agreement rate between the first subset and the first evaluation subset,

Agreement (X, Z) represents an agreement rate between the first subset and the second evaluation subset,

Agreement (Y, Z) represents an agreement rate between the first evaluation subset and the second evaluation subset,

P(X_is_right and Y_is_right|IP) represents a probability that the geographical locations associated with the IP addresses in the first subset and the first evaluation subset are equal and are correct,

P(X_is_right and Z_is_right|IP) represents a probability that the geographical locations associated with the IP addresses in the first subset and the second evaluation subset are equal and are correct,

P(Y_is_right and Z_is_right|IP) represents a probability that the geographical locations associated with the IP addresses in the first evaluation subset and the second evaluation subset are equal and are correct,

P(X_is_wrong and Y_is_wrong and the geolocations are equal|IP) represents a probability that the geographical locations associated with the IP addresses in the first subset and the first evaluation subset are equal and are incorrect,

P(X_is_wrong and Z_is_wrong and the geolocations are equal|IP) represents a probability that the geographical locations associated with the IP addresses in the first subset and the second evaluation subset are equal and are incorrect, and

P(Y_is_wrong and Z_is_wrong and the geolocations are equal|IP) represents a probability that the geographical locations associated with the IP addresses in the first evaluation subset and the second evaluation subset are equal and are incorrect.

41. The computer-implemented method of claim 31, wherein the first evaluation set and second evaluation set are derived from user account information, advertiser account information, wireless Internet access point information or licensed data.