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

• US 10,436,596 B2
• Filed: 08/12/2016
• Issued: 10/08/2019
• Est. Priority Date: 07/17/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Jackson, Dean Kenneth, Klein, Daniel Victor
• Primary Examiner(s): Boomer, Jeffrey C
• Application Number:
  US15/236,373
• Publication Number:
  US 20160349064A1
• Time in Patent Office: 1,152 Days
• 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, comprising, by one or more computing devices:

receiving a list from a first user computing device, wherein the list comprises a plurality of items;

determining a latency period for each of a plurality of point of interest locations at which one or more of the items is available, wherein determining the latency period for each point of interest location comprises;

receiving fine-grained location data for a plurality of second user computing devices, wherein the fine-grained location data comprises information identifying a plurality of locations for each of the plurality of second user computing devices and a corresponding time at which each of the plurality of user computing devices was at each location;

determining, for each second user computing device, a latency interval for the point of interest location comprising an amount of time that elapses between a first time at which the fine-grained location data indicates that the second user computing device arrives at a queue and a second time at which the fine-grained location data indicates that the second user computing device leaves the queue, the queue comprising a particular area within an area comprising the point of interest location;

identifying, based on the determined latency intervals, a latency period for the particular point of interest location;

determining, in response to determining the latency period for each of the determined point of interest locations, a route identifying at least a portion of the point of interest locations at which one or more of the plurality of items on the list is available; and

transmitting, to the first user computing device, the route identifying at least a portion of the point of interest locations at which one or more of the plurality of items on the list is available causing the first user computing device to display the route.

2. The computer-implemented method of claim 1, further comprising determining, by the one or more computing devices, a location of the first user computing device relative to a location for each of the one or more point of interest locations at which one or more of the items is available, wherein determining the location of the first user computing device relative to the location of the plurality of point of interest locations comprises determining, by the one or more computing devices, point of interest locations at which one or more of the items are available that are within a defined radius encompassing the first user computing device.

3. The computer-implemented method of claim 2, wherein one or more of the point of interest locations within the defined radius encompassing the first user computer device are identified by a first user associated with the first user computing device.

4. The computer-implemented method of claim 2, further comprising, determining, by the one or more computing devices, a departure time for a first user associated with the first user computing device to begin the route.

5. The computer-implemented method of claim 1, wherein determining a route identifying at least a portion of the point of interest locations at which one or more items on the list can be acquired comprises determining, by the one or more computing devices, a travel time associated with each of the point of interest locations identified in the route.

6. The computer-implemented method of claim 5, further comprising, determining a total experience time for a first user associated with the first user computing device to complete the route, the total experience time determined based on the travel time associated with each of the point of interest locations and the latency period for each of the identified point of interest locations of the route.

7. The computer-implemented method of claim 6, wherein determining the route further comprises ordering the point of interest locations at which one or more of the items can be acquired to minimize the total experience time.

8. The computer-implemented method of claim 1, further comprising receiving, by the one or more computing devices, an indication that a first user associated with the first user computing device has acquired one or more of the items on the list.

9. The computer-implemented method of claim 1, wherein one or more of the plurality of items on the list comprise an item that can be purchased.

10. 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 a list from a first user computing device, wherein the list comprises a plurality of items;

determine a latency period for each of a plurality of point of interest locations at which one or more of the items can be acquired, wherein determining the latency period for each point of interest location comprises;

receiving fine-grained location data for a plurality of second user computing devices, wherein the fine-grained location data comprises information identifying a plurality of locations for each of the plurality of second user computing devices and a corresponding time at which each of the plurality of user computing devices was at each location;

determining, for each second user computing device, a latency interval for the point of interest location comprising an amount of time that elapses between a first time at which the fine-grained location data indicates that the second user computing device arrives at a queue and a second time at which the fine-grained location data indicates that the second user computing device leaves the queue, the queue comprising a particular area within an area comprising the point of interest location;

identifying, based on the determined latency intervals, a latency period for the particular point of interest location; and

determine, in response to determining the latency period for each of the determined point of interest locations, a route identifying at least a portion of the point of interest locations at which the one or more items is available.

11. The system of claim 10, wherein the processor is further configured to execute application code instructions that are stored in the storage device to cause the system to determine a departure time for a first user associated with the first user computing device to begin the route.

12. The system of claim 10, wherein the processor is further configured to execute application code instructions that are stored in the storage device to cause the system to determine a total experience time for the route, the total experience time determined based on the travel time associated with each of the point of interest locations and the latency period for each of the identified point of interest locations of the route.

13. The computer-implemented method of claim 12, wherein determining the route further comprises ordering the point of interest locations to minimize the total experience time.

14. The system of claim 10, wherein one or more of the plurality of items on the list comprise an item that can be purchased.

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:

a non-transitory computer-readable storage medium having computer-executable program instructions embodied thereon that when executed by a computer cause the computer to;

receive a list from a first user computing device, wherein the list comprises a plurality of items;

determine a latency period for each of a plurality of point of interest locations offering at which one or more of the items can be acquired, wherein determining the latency period for each point of interest location comprises;

receiving fine-grained location data for a plurality of second user computing devices, wherein the fine-grained location data comprises information identifying a plurality of locations for each of the plurality of second user computing devices and a corresponding time at which each of the plurality of user computing devices was at each location;

determining, for each second user computing device, a latency interval for the point of interest location comprising the amount of time that elapses between a first time at which the fine-grained location data indicates that second user computing device arrives at a queue and a second time at which the fine-grained location data indicates that second user computing device leaves the queue, the queue comprising a particular area within an area comprising the point of interest location; and

identifying, based on the determined latency intervals, a latency period for the particular point of interest location; and

determine, in response to determining the latency period for each of the determined point of interest locations, a route identifying at least a portion of the point of interest locations at which one or more of the plurality of items on the list is available.

16. The non-transitory computer-readable storage medium of claim 15, further comprising computer-executable program instructions embodied thereon that when executed by the computer cause the computer to provide the route to the first user computing device, wherein the route is displayed on the first user computing device.

17. The non-transitory computer-readable storage medium of claim 15, further comprising computer-executable program instructions embodied thereon that when executed by the computer cause the computer to determine a total experience time for the route, the total experience time determined based on the travel time associated with each of the point of interest locations and the latency period for each of the identified point of interest locations of the route.

18. The non-transitory computer-readable storage medium of claim 15 wherein one or more of the plurality of items on the list comprise an item that can be purchased.