Resolving location criteria using user location data

• US 9,888,347 B1
• Filed: 04/17/2014
• Issued: 02/06/2018
• Est. Priority Date: 04/17/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Tan, Mervyn
• Primary Examiner(s): Hammonds, Marcus
• Application Number:
  US14/255,590
• Time in Patent Office: 1,391 Days
• Field of Search: 4554041-4042, 4554561-457
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences
• CPC Class Codes: H04W 4/023 using mutual or relative location information between multiple location based services [LBS] targets or of distance thresholds

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for resolving location criteria using user location data. One of the methods includes receiving data identifying an action to be performed in response to received user requests and data identifying location criteria for performing the action; determining a cover sets for possible confidence radii; receiving a plurality of requests, each request being associated with a respective location and a confidence radius for the location; determining, for each of the plurality of requests, whether the location associated with the request is in the cover set corresponding to the confidence radius for the location associated with the request; and for each request for which the location associated with the request is in the cover set for the confidence radius corresponding to the location associated with the request, determining that the location criteria for performing the action are satisfied.

Claims

1. A method performed by one or more computers, the method comprising:

receiving data that identifies an action and location criteria for performing the action, wherein the location criteria specifies;

(i) a target geographic region, and

(ii) a confidence threshold that indicates a threshold level of confidence that a location is within the target geographic region in order for the action to be performed;

determining a respective cover set for each of a plurality of possible confidence radii,

wherein each possible confidence radius in the plurality of possible confidence radii defines a size of a geographic region that is proportional to a level of locational uncertainty for a possible location that is associated with the possible confidence radius,

wherein the respective cover set for each of the plurality of possible confidence radii identifies a set of locations that each have a level of confidence for being within the target geographic region that satisfies the confidence threshold when the location is associated with the possible confidence radius;

after determining the respective cover set for each of the plurality of possible confidence radii;

receiving a plurality of requests, each request being associated with a respective location and a confidence radius that represents a level of locational uncertainty for the respective location;

determining, for each of the plurality of requests, whether the respective location associated with the request is in the set of locations identified by the respective cover set for the possible confidence radius that corresponds to the confidence radius that represents the level of locational uncertainty for the respective location associated with the request;

for each request for which the respective location associated with the request is in the set of locations identified by the respective cover set for the possible confidence radius that corresponds to the confidence radius that represents the level of locational uncertainty for the respective location associated with the request, determining that the location criteria for performing the action are satisfied; and

for each request for which the respective location associated with the request is not in the set of locations identified by the respective cover set for the possible confidence radius that corresponds to the confidence radius that represents the level of locational uncertainty for the respective location associated with the request, determining that the location criteria for performing the action are not satisfied.

2. The method of claim 1, wherein determining a respective cover set for each of the plurality of possible confidence radii comprises:

partitioning the possible confidence radii into a plurality of intervals;

selecting a respective representative radius from each of the plurality of intervals;

determining a respective cover set for each representative radius; and

for each interval, associating the cover set for the representative radius selected from the interval with the interval.

3. The method of claim 2, wherein, for each of the plurality of requests, determining whether the respective location associated with the request is in the set of locations identified by the respective cover set for the possible confidence radius that corresponds to the confidence radius that represents the level of locational uncertainty for the respective location associated with the request comprises:

determining an interval that contains the respective location associated with the request; and

determining whether the respective location associated with the request is in the respective cover set associated with the interval that contains the location associated with the request.

4. The method of claim 2, wherein determining a respective cover set for each representative radius comprises:

determining, for the representative radius, a probability density function for a candidate geographic region, wherein the probability density function takes as an input an input location from the candidate geographic region and outputs a probability that the input location is in the target geographic region when associated with the representative radius;

identifying qualifying locations, wherein an output of the probability density function exceeds the confidence threshold for each qualifying location; and

generating a cover set for the representative radius that contains each qualifying location.

5. The method of claim 4, wherein determining the probability density function comprises:

obtaining data partitioning the target geographic region into a plurality of disjoint target geographic region partitions;

for each location in the candidate geographic region and for each target geographic region partition, determining a respective probability that the location in the candidate geographic region is in the target geographic region partition when the location is associated with the representative radius; and

determining the probability density function by, for each location, aggregating the respective probabilities for each target geographic region partition.

6. The method of claim 5, wherein determining the respective probability that the location in the candidate geographic region is in the target geographic region partition when associated with the representative radius comprises:

determining a ratio between (1) an area of an intersection between a region of confidence centered at the location and having a radius equal to the representative radius and the target geographic region partition and (2) an area of the region of confidence.

7. The method of claim 1, wherein the action to be performed comprises providing geographically-relevant information for presentation to a user.

21. The method of claim 1, further comprising, for at least one request and in response to determining that the location criteria are satisfied for the at least one request, performing the action.

8. A system comprising one or more computers and one or more storage devices storing instructions that when executed by the one or more computers cause the one or more computers to perform operations comprising:

receiving data that identifies an action and location criteria for performing the action, wherein the location criteria specifies;

(i) a target geographic region, and

(ii) a confidence threshold that indicates a threshold level of confidence that a location is within the target geographic region in order for the action to be performed;

determining a respective cover set for each of a plurality of possible confidence radii,

wherein each possible confidence radius in the plurality of possible confidence radii defines a size of a geographic region that is proportional to a level of locational uncertainty for a possible location that is associated with the possible confidence radius,

wherein the respective cover set for each of the plurality of possible confidence radii identifies a set of locations that each have a level of confidence for being within the target geographic region that satisfies the confidence threshold when the location is associated with the possible confidence radius;

after determining the respective cover set for each of the plurality of possible confidence radii;

receiving a plurality of requests, each request being associated with a respective location and a confidence radius that represents a level of locational uncertainty for the respective location;

determining, for each of the plurality of requests, whether the respective location associated with the request is in the set of locations identified by the respective cover set for the possible confidence radius that corresponds to the confidence radius that represents the level of locational uncertainty for the respective location associated with the request;

for each request for which the respective location associated with the request is in the set of locations identified by the respective cover set for the possible confidence radius that corresponds to the confidence radius that represents the level of locational uncertainty for the respective location associated with the request, determining that the location criteria for performing the action are satisfied; and

for each request for which the respective location associated with the request is not in the set of locations identified by the respective cover set for the possible confidence radius that corresponds to the confidence radius that represents the level of locational uncertainty for the respective location associated with the request, determining that the location criteria for performing the action are not satisfied.

9. The system of claim 8, wherein determining a respective cover set for each of the plurality of possible confidence radii comprises:

partitioning the possible confidence radii into a plurality of intervals;

selecting a respective representative radius from each of the plurality of intervals;

determining a respective cover set for each representative radius; and

for each interval, associating the cover set for the representative radius selected from the interval with the interval.

10. The system of claim 9, wherein, for each of the plurality of requests, determining whether the respective location associated with the request is in the set of locations identified by the respective cover set for the possible confidence radius that corresponds to the confidence radius that represents the level of locational uncertainty for the respective location associated with the request comprises:

determining an interval that contains the respective location associated with the request; and

determining whether the respective location associated with the request is in the respective cover set associated with the interval that contains the location associated with the request.

11. The system of claim 9, wherein determining a respective cover set for each representative radius comprises:

determining, for the representative radius, a probability density function for a candidate geographic region, wherein the probability density function takes as an input an input location from the candidate geographic region and outputs a probability that the input location is in the target geographic region when associated with the representative radius;

identifying qualifying locations, wherein an output of the probability density function exceeds the confidence threshold for each qualifying location; and

generating a cover set for the representative radius that contains each qualifying location.

12. The system of claim 11, wherein determining the probability density function comprises:

obtaining data partitioning the target geographic region into a plurality of disjoint target geographic region partitions;

for each location in the candidate geographic region and for each target geographic region partition, determining a respective probability that the location in the candidate geographic region is in the target geographic region partition when the location is associated with the representative radius; and

determining the probability density function by, for each location, aggregating the respective probabilities for each target geographic region partition.

13. The system of claim 12, wherein determining the respective probability that the location in the candidate geographic region is in the target geographic region partition when associated with the representative radius comprises:

determining a ratio between (1) an area of an intersection between a region of confidence centered at the location and having a radius equal to the representative radius and the target geographic region partition and (2) an area of the region of confidence.

14. The system of claim 8, wherein the action to be performed comprises providing geographically-relevant information for presentation to a user.

15. A non-transitory computer storage medium encoded with instructions that, when executed by one or more computers, cause the one or more computers to perform operations comprising:

receiving data that identifies an action and location criteria for performing the action, wherein the location criteria specifies;

(i) a target geographic region, and

(ii) a confidence threshold that indicates a threshold level of confidence that a location is within the target geographic region in order for the action to be performed for the target region;

determining a respective cover set for each of a plurality of possible confidence radii,

wherein each possible confidence radius in the plurality of possible confidence radii defines a size of a geographic region that is proportional to a level of locational uncertainty for a possible location that is associated with the possible confidence radius,

wherein the respective cover set for each of the plurality of possible confidence radii identifies a set of locations that each have a level of confidence for being within the target geographic region that satisfies the confidence threshold when the location is associated with the possible confidence radius;

after determining the respective cover set for each of the plurality of possible confidence radii;

receiving a plurality of requests, each request being associated with a respective location and a confidence radius that represents a level of locational uncertainty for the respective location;

determining, for each of the plurality of requests, whether the respective location associated with the request is in the set of locations identified by the respective cover set for the possible confidence radius that corresponds to the confidence radius that represents the level of locational uncertainty for the respective location associated with the request;

for each request for which the respective location associated with the request is in the set of locations identified by the respective cover set for the possible confidence radius that corresponds to the confidence radius that represents the level of locational uncertainty for the respective location associated with the request, determining that the location criteria for performing the action are satisfied; and

for each request for which the respective location associated with the request is not in the set of locations identified by the respective cover set for the possible confidence radius that corresponds to the confidence radius that represents the level of locational uncertainty for the respective location associated with the request, determining that the location criteria for performing the action are not satisfied.

16. The non-transitory computer storage medium of claim 15, wherein determining a respective cover set for each of the plurality of possible confidence radii comprises:

partitioning the possible confidence radii into a plurality of intervals;

selecting a respective representative radius from each of the plurality of intervals;

determining a respective cover set for each representative radius; and

for each interval, associating the cover set for the representative radius selected from the interval with the interval.

17. The non-transitory computer storage medium of claim 16, wherein, for each of the plurality of requests, determining whether the respective location associated with the request is in the set of locations identified by the respective cover set for the possible confidence radius that corresponds to the confidence radius that represents the level of locational uncertainty for the respective location associated with the request comprises:

determining an interval that contains the respective location associated with the request; and

determining whether the respective location associated with the request is in the respective cover set associated with the interval that contains the location associated with the request.

18. The non-transitory computer storage medium of claim 16, wherein determining a respective cover set for each representative radius comprises:

determining, for the representative radius, a probability density function for a candidate geographic region, wherein the probability density function takes as an input an input location from the candidate geographic region and outputs a probability that the input location is in the target geographic region when associated with the representative radius;

identifying qualifying locations, wherein an output of the probability density function exceeds the confidence threshold for each qualifying location; and

generating a cover set for the representative radius that contains each qualifying location.

19. The non-transitory computer storage medium of claim 18, wherein determining the probability density function comprises:

obtaining data partitioning the target geographic region into a plurality of disjoint target geographic region partitions;

for each location in the candidate geographic region and for each target geographic region partition, determining a respective probability that the location in the candidate geographic region is in the target geographic region partition when the location is associated with the representative radius; and

determining the probability density function by, for each location, aggregating the respective probabilities for each target geographic region partition.

20. The non-transitory computer storage medium of claim 19, wherein determining the respective probability that the location in the candidate geographic region is in the target geographic region partition when associated with the representative radius comprises:

determining a ratio between (1) an area of an intersection between a region of confidence centered at the location and having a radius equal to the representative radius and the target geographic region partition and (2) an area of the region of confidence.