SYSTEM AND METHOD FOR ADDRESS BASED LOCATIONS

• US 20150372966A1
• Filed: 06/18/2014
• Published: 12/24/2015
• 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
• Granted Patent: US 9,661,066 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 method comprising:

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

receiving information about a plurality of location-known requests that originated from the address;

wherein the information indicates a plurality of distinct locations associated with the 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 address with the at least one geographical locality.

2. The method in claim 1 further comprising:

receiving a location-unknown request that originated from a particular 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 address and the set of address-to-location mappings.

3. The method of claim 1 wherein 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 a 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 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.

6. The method in claim 5 further comprising:

sorting the set of address-to-location mappings based on 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 the proximity of the locations combining the adjoining subset of address-to-location mappings into an address-to-range mapping.

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

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

based on a prefix of the particular 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 entries to the particular address;

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

9. The method of claim 8, wherein

the index entry comprises a count that indicates a number of the data entries that exists for the particular 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.

10. 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.

11. The method in claim 10, 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.

12. The method of claim 10, 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.

13. 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 location-known requests in the subset has a timestamp that is within a particular time period.

14. 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.

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

16. A method comprising:

generating a set of address-to-location mappings based on information obtained from location-known requests sent by devices interacting with one or more location-aware applications; and

using said address-to-location mappings to provide location-relevant information in response to location-unknown requests sent by devices interacting with one or more location-unaware applications;

wherein the method is performed by one or more computing devices.

17. The method of claim 16 wherein generating the set of address-to-location mappings includes:

within the information obtained from the location-known requests, identifying a set of locations associated with a particular address;

determining that one or more locations in the set of locations qualify as outliers; and

generating an address-to-location mapping for the particular address based on only those locations, within the set, that do not qualify as outliers.

18. 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 addresses;

receiving information about a plurality of location-known requests that originated from the address;

wherein the information indicates a plurality of distinct locations associated with the 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 address with the at least one geographical locality.

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

receiving a location-unknown request that originated from a particular 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 address and the set of address-to-location mappings.

20. The one or more non-transitory storage media storing instructions of claim 18 wherein 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 a 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.

21. The one or more non-transitory storage media storing instructions of claim 20, 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.

22. The one or more non-transitory storage media storing instructions of claim 18, wherein the method further comprises 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.

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

sorting the set of address-to-location mappings based on 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 the proximity of the locations combining the adjoining subset of address-to-location mappings into an address-to-range mapping.

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

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

based on a prefix of the particular 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 entries to the particular address;

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

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

the index entry comprises a count that indicates a number of the data entries that exists for the particular 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.

27. The one or more non-transitory storage media storing instructions of claim 20, 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.

28. The one or more non-transitory storage media storing instructions of claim 27, 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.

29. The one or more non-transitory storage media storing instructions of claim 27, 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.

30. The one or more non-transitory storage media storing instructions of claim 18, 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 location-known requests in the subset has a timestamp that is within a particular time period.

31. The one or more non-transitory storage media storing instructions of claim 19, 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.

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

33. 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 based on information obtained from location-known requests sent by devices interacting with one or more location-aware applications; and

using said address-to-location mappings to provide location-relevant information in response to location-unknown requests sent by devices interacting with one or more location-unaware applications;

wherein the method is performed by one or more computing devices.

34. The one or more non-transitory storage media storing instructions of claim 33 wherein generating the set of address-to-location mappings includes:

within the information obtained from the location-known requests, identifying a set of locations associated with a particular address;

determining that one or more locations in the set of locations qualify as outliers; and

generating an address-to-location mapping for the particular address based on only those locations, within the set, that do not qualify as outliers.