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

• US 9,470,538 B2
• Filed: 03/11/2015
• Issued: 10/18/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
• Application Number:
  US14/644,982
• Publication Number:
  US 20150185032A1
• Time in Patent Office: 587 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, a shopping list from a first user computing device, wherein the shopping list comprises a plurality of products;

determining, by the one or more computing devices, a location of the first user computing device relative to a location of a plurality of merchants offering one or more of the products for sale;

determining, by the one or more computing devices, a latency period for each of the plurality of merchant locations offering one or more of the products for sale, wherein determining the latency period each merchant location comprises;

receiving, by one or more computing devices, 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, by the one or more computing devices and for each of the second user computing devices, a latency interval for the merchant location comprising the amount of time that elapses between a first time at which a particular one of the second user computing device arrives at a particular geographic area at the merchant location comprising a queue and a second time at which the particular one of the second user computing device leaves the particular geographic area comprising the queue;

identifying, by the one or more computing devices and based on the determined latency intervals, a latency period for the particular merchant location; and

determining, by the one or more computing devices and in response to determining the latency period for each of the determined merchant locations, a shopping route for the user to obtain one or more of the products on the shopping list, wherein the shopping route identifies at least a portion of the merchants offering the one or more products for sale.

2. The computer-implemented method of claim 1, further comprising, providing, by the one or more computing devices, the shopping route to the first user computing device, wherein the shopping route is displayed on the first user computing device.

3. The computer-implemented method of claim 1, wherein determining the location of the first user computing device relative to the location of a plurality of merchants offering the plurality of products for sale comprises determining, by the one or more computing devices, merchant locations that are near the first user computing device.

4. The computer-implemented method of claim 3, wherein merchant locations that are near the first user computing device comprise merchant locations that are within a defined radius encompassing the user first computing device.

5. The computer-implemented method of claim 3, wherein one or more of the merchant locations near the first user computer device are identified by the first user.

6. The computer-implemented method of claim 3, further comprising, determining, by the one or more computing devices, a departure time for the first user to begin the shopping route.

7. The computer-implemented method of claim 1, wherein determining a shopping route for the first user to obtain the products on the shopping list comprises determining, by the one or more computing devices, a travel time associated with each of the merchant locations identified in the shopping route.

8. The computer-implemented method of claim 7, further comprising, determining a total experience time for the first user to obtain the plurality of products on the shopping list, the total experience time determined based on the travel time associated with each of the merchant locations and the latency period for each of the identified merchant locations of the shopping route.

9. The computer-implemented method of claim 8, wherein determining the shopping route further comprises ordering the merchant locations to minimize the total experience time.

10. The computer-implemented method of claim 1, further comprising receiving, by the one or more computing devices, an indication that the first user has purchased one or more of the products on the shopping list.

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

determine a location of the first user computing device relative to a location of a plurality of merchants offering one or more of the products for sale;

determine a latency period for each of the plurality of merchant locations offering one or more of the products for sale, wherein determining the latency period each merchant 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 of the second user computing devices, a latency interval for the merchant location comprising the amount of time that elapses between a first time at which a particular one of the second user computing device arrives at a particular geographic area at the merchant location comprising a queue and a second time at which the particular one of the second user computing device leaves the particular geographic area comprising the queue;

identifying, based on the determined latency intervals, a latency period for the particular merchant location; and

determine, in response to determining the latency period for each of the determined merchant locations, a shopping route for the user to obtain one or more of the products on the shopping list, wherein the shopping route identifies at least a portion of the merchants offering the one or more products for sale.

12. The system of claim 11, wherein the processor is further configured to execute application code instructions that are stored in the storage device to cause the system to provide the shopping route to the first user computing device, wherein the shopping route is displayed on the first user computing device.

13. The system of claim 11, 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 the first user to begin the shopping route.

14. The system of claim 11, wherein determining a shopping route for the first user to obtain the products on the shopping list comprises determining a travel time associated with each of the merchant locations identified in the shopping route.

15. The system of claim 11, 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 first user to obtain the plurality of products on the shopping list, the total experience time determined based on the travel time associated with each of the merchant locations and the latency period for each of the identified merchant locations of the shopping route.

16. The system of claim 15, wherein determining the shopping route further comprises ordering the merchant locations to minimize the total experience time.

17. A computer program product, comprising:

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 latency periods, the computer-executable program instructions comprising;

computer-executable program instructions to receive a shopping list from a first user computing device, wherein the shopping list comprises a plurality of products;

computer-executable program instructions to determine a location of the first user computing device relative to a location of a plurality of merchants offering one or more of the products for sale;

computer-executable program instructions to determine a latency period for each of the plurality of merchant locations offering one or more of the products for sale, wherein the computer-executable program instructions to determine the latency period each merchant location comprises;

computer-executable program instructions to receive 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;

computer-executable program instructions to determine, for each of the second user computing devices, a latency interval for the merchant location comprising the amount of time that elapses between a first time at which a particular one of the second user computing device arrives at a particular geographic area at the merchant location comprising a queue and a second time at which the particular one of the second user computing device leaves the particular geographic area comprising the queue;

computer-executable program instructions to identify, based on the determined latency intervals, a latency period for the particular merchant location; and

computer-executable program instructions to determine, in response to determining the latency period for each of the determined merchant locations, a shopping route for the user to obtain one or more of the products on the shopping list, wherein the shopping route identifies at least a portion of the merchants offering the one or more products for sale.

18. The computer program product of claim 17, further comprising computer-executable program instructions to provide the shopping route to the first user computing device, wherein the shopping route is displayed on the first user computing device.

19. The computer program product of claim 17, wherein determining a shopping route for the first user to obtain the products on the shopping list comprises determining a travel time associated with each of the merchant locations identified in the shopping route.

20. The computer program product of claim 17, further comprising computer-executable program instructions to determine a total experience time for the first user to obtain the plurality of products on the shopping list, the total experience time determined based on the travel time associated with each of the merchant locations and the latency period for each of the identified merchant locations of the shopping route.