Point-of-interest latency prediction using mobile device location history

• US 9,329,047 B2
• Filed: 10/22/2013
• Issued: 05/03/2016
• Est. Priority Date: 07/17/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Jackson, Dean Kenneth, Klein, Daniel Victor
• Primary Examiner(s): Khatib, Rami
• Assistant Examiner(s): BOOMER, JEFFREY C
• Application Number:
  US14/060,337
• Publication Number:
  US 20150025799A1
• Time in Patent Office: 924 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• CPC Class Codes: G01C 21/3617 using user history, behaviour, conditions or preferences, e.g. predicted or inferred from previous use or current movement
• CPC Class Codes: G01C 21/3679 Retrieval, searching and output of POI information, e.g. hotels, restaurants, shops, filling stations, parking facilities G01C21/3611 takes precedence
• CPC Class Codes: G01C 21/3691 Retrieval, searching and output of information related to real-time traffic, weather, or environmental conditions arrangements for giving variable traffic instructions G08G1/09
• CPC Class Codes: G01C 21/3811 Point data, e.g. Point of Interest [POI]
• CPC Class Codes: G06Q 30/0639 Item locations
• CPC Class Codes: H04W 4/029 Location-based management or tracking services

Abstract

A latency analysis system determines a latency period, such as a wait time, at a user destination. To determine the latency period, the latency analysis system receives location history from multiple user devices. With the location histories, the latency analysis system identifies points-of-interest that users have visited and determines the amount of time the user devices were at a point-of-interest. For example, the latency analysis system determines when a user device entered and exited a point-of-interest. Based on the elapsed time between entry and exit, the latency analysis system determines how long the user device was inside the point-of-interest. By averaging elapsed times for multiple user devices, the latency analysis system determines a latency period for the point-of-interest. The latency analysis system then uses the latency period to provide latency-based recommendations to a user. For example, the latency analysis system may determine a shopping route for a user.

Claims

1. A computer-implemented method for latency determination for points-of-interest, comprising:

receiving, by one or more computing devices, location history for a plurality of user computing devices, wherein the location history comprises information identifying a plurality of locations for each of the plurality of user computing devices and a time corresponding to when each of the plurality of user computing devices was at each location;

identifying, by the one or more computing devices, a location of a queue associated with a first point-of-interest from the location history received from the plurality of user computing devices based on a match of the location for at least a portion of the plurality of the user computing devices, wherein the location of the queue comprises a particular area at a location of the first point-of-interest;

determining, by the one or more computing devices and for one or more of the plurality of the user computing devices having a location corresponding to the location of the first point-of-interest, a first time associated with the user computing device arriving at the location of the queue associated with the first point-of-interest and a second time associated with the user computing device leaving the location of the queue associated with the first point-of-interest, wherein the arriving at the location of the queue and the leaving the location of the queue is determined based on fine-grain location data for the one or more of the plurality of the user computing devices having a location corresponding to the location of the first point-of-interest;

comparing, by the one or more computing devices and for one or more of the user computing devices arriving at the location of the queue associated with the first point-of-interest and leaving the location of the queue associated with the first point-of-interest, the determined first time to the determined second time to determine a latency interval at the first point-of-interest;

determining, by the one or more computing devices, a latency period for the first point-of-interest, wherein the latency period is a function of a plurality of latency intervals for the first point-of-interest;

receiving, by the one or more computing devices, a request from a particular user computing device for a route comprising a plurality of points-of-interest;

determining, by the one or more computing devices, one or more routes comprising at least two points of interest, wherein at least one of the one or more routes comprises the first point-of-interest and one or more second points of interest;

selecting, by the one or more computing devices, a particular route having a shortest time of the one or more routes, wherein the shortest time is based at least in part on the latency period of the first point-of-interest, and wherein the selected route comprises the first point-of-interest and one or more second points of interest; and

communicating, by the one or more computing devices, a response to the particular user computing device, wherein the response includes displaying the selected route on the particular user computing device.

2. The computer-implemented method of claim 1, wherein communicating the response to the particular user computing device further comprises:

reading, by the one or more computing devices, the request from the particular user computing device to determine a content for the request;

determining, by the one or more computing devices and based on the content of the request, latency-period information that is responsive to the request; and

,

incorporating, by the one or more computing devices, the responsive latency-period information into the communication to the particular user computing device.

3. The computer-implemented method of claim 2, wherein the response comprises qualitative or quantitative latency-period information.

4. The computer-implemented method of claim 2, wherein in the latency-period information is included in a total time determination for the point-of-interest comprising a drive time for the particular user computing device to move from its current location to the location of the first point-of-interest and the latency period for the first point-of-interest.

5. The computer-implemented method of claim 1, wherein the length of the latency period is determined as a function of the mean, median, or mode for the latency intervals for a plurality of first user computing devices.

6. The computer-implemented method of claim 1, further comprising:

determining, by the one or more computing devices, a population of users at or near the first point-of-interest; and

,

adjusting, by the one or more computing devices, the length of the latency period in response to determining the population of users at or near the first point-of-interest.

7. The computer-implemented method of claim 6, wherein the length of the latency period is increased in response to determining an increase in the population of users at or near the first point-of-interest.

8. The computer-implemented method of claim 1, further comprising:

determining, by the one or more computing devices, the latency period for two or more points-of-interest;

determining, by the one or more computing devices, a current location of the particular user computing device;

estimating, by the one or more computing devices, a travel time for the particular user computing device to move from its current location to the location of each of the points-of-interest;

determining, by the one or more computing devices, a total experience time for each of the points-of-interest as a function of the latency period for each of the points-of-interest and the corresponding travel time for each of the points-of-interest; and

,

presenting, by the one or more computing devices, information via the particular user device for the points-of-interest based on the total experience time for each of the points-of-interest.

9. The computer-implemented method of claim 8, wherein presenting the information for the points-of-interest comprises presenting the total experience time for each of the points-of-interest.

10. The computer-implemented method of claim 8, wherein presenting the information for the points-of-interest comprises ordering the points-of-interest based on the total experience time for each of the points-of-interest.

11. A system for latency period determination, comprising:

a storage device;

a processor communicatively coupled to the storage device, wherein the processor executes application code instructions that are stored in the storage device to cause the system to;

receive location history for a plurality of user computing devices, wherein the location history comprises information identifying a plurality of locations for each of the plurality of user computing devices and a time corresponding to when each of the plurality of user computing devices was at each location;

identify a location of a queue associated with a first point-of-interest from the location history received from the plurality of user computing devices based on a match of the location for at least a portion of the plurality of the user computing devices, wherein the location of the queue comprises a particular area at a location of a first point-of-interest;

determine, for one or more of the plurality of the user computing devices having a location corresponding to the location of the first point-of-interest, a first time associated with the user computing device arriving at the location of the queue associated with the first point-of-interest and a second time associated with the user computing device leaving the location of the queue associated with the first point-of-interest, wherein the arriving at the location of the queue and the leaving the location of the queue is determined based on fine-grain location data for the one or more of the plurality of the user computing devices having a location corresponding to the location of the first point-of-interest; and

compare, for one or more of the user computing devices arriving at the location of the queue associated with the first point-of-interest and leaving the location of the queue associated with the first point-of-interest, the determined first time to the determined second time to determine a latency interval at the first point-of-interest; and

determine, by the one or more of the user computing devices, a latency period for the first point-of-interest, wherein the latency period is a function of a plurality of latency intervals for the first point-of-interest;

receive, by the one or more of the user computing devices, a request from a particular user computing device for a route comprising a plurality of points-of-interest;

determine, by the one or more of the user computing devices, one or more routes comprising at least two points of interest, wherein at least one of the one or more routes comprises the first point-of-interest and one or more second points of interest;

select, by the one or more user computing devices, a particular route having a shortest time of the one or more routes, wherein the shortest time is based at least in part on the latency period of the first point-of-interest, and wherein the selected route comprises the first point-of-interest and one or more second points of interest; and

communicate, by the one or more user computing devices, a response to the particular user computing device, wherein the response includes displaying the selected route on the particular user computing device.

12. The system of claim 11, wherein communicating the response to the particular user computing device further comprises:

determining latency-period information that is responsive to the request; and

, incorporating the responsive latency-period information into the communication to the particular user computing device.

13. The system of claim 11, further comprising:

determining a population of users at or near the point-of-interest; and

, adjusting the length of the latency period in response to determining the population of users at or near the point-of-interest.

14. The system of claim 11, further comprising:

determining the latency period for two or more points-of-interest;

determining a current location of the particular user computing device;

estimating a travel time for the particular user computing device to move from its current location to the location of each of the points-of-interest;

determining a total experience time for each of the points-of-interest as a function of the latency period for each of the points-of-interest and the corresponding travel time for each of the points-of-interest; and

, presenting information via the particular user device for the points-of-interest based on the total experience time for each of the points-of-interest.

15. A non-transitory computer-readable storage medium having computer-executable program instructions embodied thereon that when executed by a computer cause the computer to determine a latency period for points-of-interest, the computer-executable program instructions comprising:

computer-executable program instructions to receive location history for a plurality of user computing devices, wherein the location history comprises information identifying a plurality of locations for each of the plurality of user computing devices and a time corresponding to when each of the plurality of user computing devices was at each location;

computer-executable program instructions to identify a location of a queue associated with a first point-of-interest from the location history received from the plurality of user computing devices based on a match of the location for at least a portion of the plurality of the user computing devices, wherein the location of the queue comprises a particular area at a location of the first point-of-interest;

computer-executable program instructions to determine, for one or more of the plurality of the user computing devices having a location corresponding to the location of the first point-of-interest, a first time associated with the user computing device arriving at the location of the queue associated with the first point-of-interest and a second time associated with the user computing device leaving the location of the queue associated with the first point-of-interest, wherein the arriving at the location of the queue and the leaving the location of the queue is determined based on fine-grain location data for the one or more of the plurality of the user computing devices having a location corresponding to the location of the first point-of-interest;

computer-executable program instructions to compare, for one or more of the user computing devices arriving at the location of the queue associated with the first point-of-interest and leaving the location of the queue associated with the first point-of-interest, the determined first time to the determined second time to determine a latency interval at the first point-of-interest;

computer-executable program instructions to determine a latency period for the first point-of-interest, wherein the latency period is a function of a plurality of latency intervals for the first point-of-interest; and

computer-executable program instructions to receive, by the one or more of the plurality of the user computing devices, a request from a particular user computing device for a route comprising a plurality of points-of-interest;

computer-executable program instructions to determine, by the one or more of the plurality of the user computing devices, one or more routes comprising at least two points of interest, wherein at least one of the one or more routes comprises the first point-of-interest and one or more second points of interest;

computer-executable program instructions to select, by the one or more of the plurality of the user computing devices, a particular route having a shortest time of the one or more routes, wherein the shortest time is based at least in part on the latency period of the first point-of-interest, and wherein the selected route comprises the first point-of-interest and one or more second points of interest; and

computer-executable program instructions to communicate by the one or more of the plurality of the user computing devices, a response to the particular user computing device, wherein the response includes displaying the selected route on the particular user computing device, wherein the response includes displaying the selected route on the particular user computing device.

16. The non-transitory computer-readable storage medium of claim 15, wherein the computer program instructions to communicate a response to the particular user computing device is provided in response to receiving a request from the particular user computing device.

17. The non-transitory computer-readable storage medium of claim 15, further comprising:

determining a population of users at or near the point-of-interest; and

, adjusting the length of the latency period in response to determining the population of users at or near the point-of-interest.

18. The non-transitory computer-readable storage medium of claim 15, further comprising:

determining the latency period for two or more points-of-interest;

determining a current location of the particular user computing device;

estimating a travel time for the particular user computing device to move from its current location to the location of each of the points-of-interest;

determining a total experience time for each of the points-of-interest as a function of the latency period for each of the points-of-interest and the corresponding travel time for each of the points-of-interest; and

, presenting information via the particular user device for the points-of-interest based on the total experience time for each of the points-of-interest.

19. The non-transitory computer-readable storage medium of claim 18, wherein presenting the information for the points-of-interest comprises presenting the total experience time for each of the points-of-interest.