System and method for address based locations

• US 9,661,066 B2
• Filed: 06/18/2014
• Issued: 05/23/2017
• Est. Priority Date: 06/18/2014
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Seth, Abhishek, Kumar, Mahendra
• Primary Examiner(s): Chacko, Joe
• Application Number:
  US14/308,573
• Publication Number:
  US 20150372966A1
• Time in Patent Office: 1,070 Days
• CPC Class Codes: H04L 2101/69 using geographic information, e.g. room number
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences

Abstract

Techniques are provided for identifying a locations of application users based on originating address. Techniques to generate a set of address-to-location mappings include a system configured to receive information about a plurality of location-known requests that originated from an address, wherein the information indicates a plurality of locations for the originating address. The system is further configured to identify a geographical area based, at least in part, on the plurality of distinct locations; map the geographical area to a corresponding geographical locality; and associate the address to the geographical area and the corresponding geographical locality generating an address-to-location mapping. Address-to-location mappings may be further clustered into address-range-to-location mappings and stored as a data pack. Using these techniques, location information may be determined for a received location-unknown request that originated from a particular address.

Claims

1. A computer-implemented method comprising:

generating a set of address-to-location mappings by performing the following steps for each of a plurality of network addresses;

receiving information about a plurality of location-known requests that originated from one or more requesting devices,

wherein, when each location-known request of the plurality of location-known requests was sent, the requesting device that sent the location-known request was uniquely identified by a network address,

wherein the information indicates a plurality of distinct locations associated with the network address,

identifying a geographical area based, at least in part, on the plurality of distinct locations,

mapping the geographical area to at least one geographical locality, and

generating an address-to-location mapping that associates the network address with the at least one geographical locality; and

generating a plurality of address-range-to-location mappings by combining address-to-location mappings, from the set of address-to-location mappings, based on;

addresses specified in the address-to-location mappings, and

locations specified in the address-to-location mappings.

2. The method in claim 1, further comprising:

receiving a location-unknown request that originated from a particular network address, wherein the location-unknown request is not associated with any location information; and

determining location-relevant information for the location-unknown request based, at least in part, on the particular network address and the set of address-to-location mappings.

3. The method of claim 1, wherein the step of identifying a geographical area includes:

determining a first subset of the plurality of distinct locations that qualify as outliers;

wherein a second subset of the plurality of distinct locations do not qualify as outliers; and

identifying the geographical area that encompasses the second subset of the plurality of distinct locations and does not encompass the first subset of the plurality of distinct locations.

4. The method in claim 3, wherein the geographical area is based on a minimum longitude coordinate, a maximum longitude coordinate, a minimum latitude coordinate, and a maximum latitude coordinate, determined based on the second subset of locations.

5. The method in claim 1, further comprising:

sorting the set of address-to-location mappings based on network addresses;

comparing locations in an adjoining subset address-to-location mappings from the set of address-to-location mappings;

based, at least in part, on proximity of the locations, combining the adjoining subset of address-to-location mappings into an address-to-range mapping.

6. The method in claim 5, wherein the adjoining subset of address-to-location mappings includes network addresses that share a subnet.

7. The method in claim 2, wherein the step of determining location information for the request comprises:

based on a prefix of the particular network address, selecting an index entry in an index table;

retrieving index data from the index entry in the index table, wherein the index data indicates an offset into a data table;

starting at an initial entry indicated by the offset into the data table, selecting each data entry from the data table that is subsequent to the initial entry;

comparing data in the data entry to the particular network address;

if the particular network address is within a range indicated in the data, then selecting location information indicated by the data.

8. The method of claim 7, wherein

the index entry comprises a count that indicates a number of the data entries that exists for the particular network addresses with said prefix;

and

the step of selecting the data entries includes ceasing to select after selecting the number of data entries that exceeds the count.

9. The method in claim 3, wherein the step of identifying a geographical area further comprises:

determining a central location from the plurality of distinct locations;

calculating distances between the plurality of distinct locations to the central location; and

identifying the second subset of the plurality of distinct locations based on the distances.

10. The method in claim 9, wherein each location in the plurality of distinct locations is represented by a longitude coordinate and a latitude coordinate, and the central location has a longitude coordinate equal to an average of longitude coordinates of the plurality of distinct locations and has a latitude coordinate equal to an average of latitude coordinates of the plurality of distinct locations.

11. The method of claim 9, wherein the step of identifying the second subset of the plurality of distinct locations further comprises:

calculating a mean distance by averaging the distances from the central location;

calculating a standard deviation of the distances from the central location;

calculating a preferred distance based on the mean distance and the standard deviation; and

identifying the second subset of the plurality of distinct locations that are within the preferred distance from the central location.

12. The method in claim 1, wherein:

the plurality of location-known requests further comprise of a timestamp associated with each location; and

the step of generating address-to-location mappings uses a subset of the plurality of location-known requests, wherein each particular location-known request in the subset has a timestamp that is within a particular time period.

13. The method in claim 2, wherein the location-known request originates from a first set of applications to which users have granted permission to access location information;

and

the location-unknown request originates from a second set of applications, to which users have not granted permission to access location information.

14. The method in claim 2, wherein the location-unknown request is from a certain network address that does not match any network address within the set of address-to-location mappings.

15. One or more non-transitory storage media storing instructions which, when executed by one or more computing devices, cause performance of a method comprising:

generating a set of address-to-location mappings by performing the following steps for each of a plurality of network addresses;

receiving information about a plurality of location-known requests that originated from one or more requesting devices,

wherein, when each location-known request of the plurality of location-known requests was sent, the requesting device that sent the location-known request was uniquely identified by a network address,

wherein the information indicates a plurality of distinct locations associated with the network address,

identifying a geographical area based, at least in part, on the plurality of distinct locations,

mapping the geographical area to at least one geographical locality, and

generating an address-to-location mapping that associates the network address with the at least one geographical locality; and

generating a plurality of address-range-to-location mappings by combining address-to-location mappings, from the set of address-to-location mappings, based on;

addresses specified in the address-to-location mappings, and

locations specified in the address-to-location mappings.

16. The one or more non-transitory storage media storing instructions of claim 15, wherein the method further comprises:

receiving a location-unknown request that originated from a particular network address, wherein the location-unknown request is not associated with any location information; and

determining location-relevant information for the location-unknown request based, at least in part, on the particular network address and the set of address-to-location mappings.

17. The one or more non-transitory storage media storing instructions of claim 15, wherein the step of identifying a geographical area includes:

determining a first subset of the plurality of distinct locations that qualify as outliers;

wherein a second subset of the plurality of distinct locations do not qualify as outliers; and

identifying the geographical area that encompasses the second subset of the plurality of distinct locations and does not encompass the first subset of the plurality of distinct locations.

18. The one or more non-transitory storage media storing instructions of claim 17, wherein the geographical area is based on a minimum longitude coordinate, a maximum longitude coordinate, a minimum latitude coordinate, and a maximum latitude coordinate, determined based on the second subset of locations.

19. The one or more non-transitory storage media storing instructions of claim 15, wherein the method further comprises:

sorting the set of address-to-location mappings based on network addresses;

comparing locations in an adjoining subset address-to-location mappings from the set of address-to-location mappings;

based, at least in part, on proximity of the locations, combining the adjoining subset of address-to-location mappings into an address-to-range mapping.

20. The one or more non-transitory storage media storing instructions of claim 19, wherein the adjoining subset of address-to-location mappings includes network addresses that share a subnet.

21. The one or more non-transitory storage media storing instructions of claim 16, wherein the step of determining location information for the request comprises:

based on a prefix of the particular network address, selecting an index entry in an index table;

retrieving index data from the index entry in the index table, wherein the index data indicates an offset into a data table;

starting at an initial entry indicated by the offset into the data table, selecting each data entry from the data table that is subsequent to the initial entry;

comparing data in the data entry to the particular network address;

if the particular network address is within a range indicated in the data, then selecting location information indicated by the data.

22. The one or more non-transitory storage media storing instructions of claim 21, wherein

the index entry comprises a count that indicates a number of the data entries that exists for the particular network addresses with said prefix;

and

the step of selecting the data entries includes ceasing to select after selecting the number of data entries that exceeds the count.

23. The one or more non-transitory storage media storing instructions of claim 17, wherein the step of identifying a geographical area further comprises:

determining a central location from the plurality of distinct locations;

calculating distances between the plurality of distinct locations to the central location; and

identifying the second subset of the plurality of distinct locations based on the distances.

24. The one or more non-transitory storage media storing instructions of claim 23, wherein each location in the plurality of distinct locations is represented by a longitude coordinate and a latitude coordinate, and the central location has a longitude coordinate equal to an average of longitude coordinates of the plurality of distinct locations and has a latitude coordinate equal to an average of latitude coordinates of the plurality of distinct locations.

25. The one or more non-transitory storage media storing instructions of claim 23, wherein the step of identifying the second subset of the plurality of distinct locations further comprises:

calculating a mean distance by averaging the distances from the central location;

calculating a standard deviation of the distances from the central location;

calculating a preferred distance based on the mean distance and the standard deviation; and

identifying the second subset of the plurality of distinct locations that are within the preferred distance from the central location.

26. The one or more non-transitory storage media storing instructions of claim 15, wherein:

the plurality of location-known requests further comprise of a timestamp associated with each location; and

the step of generating address-to-location mappings uses a subset of the plurality of location-known requests, wherein each particular location-known request in the subset has a timestamp that is within a particular time period.

27. The one or more non-transitory storage media storing instructions of claim 16, wherein the location-known request originates from a first set of applications to which users have granted permission to access location information;

and

the location-unknown request originates from a second set of applications, to which users have not granted permission to access location information.

28. The one or more non-transitory storage media storing instructions of claim 16, wherein the location-unknown request is from a certain network address that does not match any network address within the set of address-to-location mappings.