IP Library › Granted Patent US 9,661,066

Granted Patent B2

US 9,661,066 · App. 14/308,573 · Granted May 23, 2017

System and method for address based locations

View Patent ↗

Loading inventors, assignments & file history…

Monitor This Case

Get email alerts when status or documents change.

Order Certified Copies

Most orders are placed with the USPTO same day — all within 24 business hours.

Order via The Patent Place →

Pre-filled with this patent's details

Quick Facts

Patent No.: US 9,661,066
App. No.: 14/308,573
Granted: May 23, 2017
Kind: B2

External Links

USPTO Patent Center↗ Full Patent PDF↗

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 (98)

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: