Ranking nearby destinations based on visit likelihoods and predicting future visits to places from location history

• US 9,449,053 B2
• Filed: 11/18/2014
• Issued: 09/20/2016
• Est. Priority Date: 06/22/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Yang, Guang, Udeshi, Tushar, Kirmse, Andrew, Praun, Emil, Bellver, Pablo, Mierle, Keir Banks
• Primary Examiner(s): CHEUNG, CALVIN K
• Application Number:
  US14/546,511
• Publication Number:
  US 20150073693A1
• Time in Patent Office: 672 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/20 Ensemble learning
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation
• CPC Class Codes: G06N 5/04 Inference or reasoning models
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

In some examples, systems and techniques can determine a respective visit likelihood for each respective destination of a plurality of destinations based at least in part on a respective distance between the respective destination and a geographic location from a location history associated with a user and a comparison between a time associated with the geographic location and a visit likelihood distribution across time. The systems and techniques can then sort at least some of the plurality of destinations. In other examples, systems and techniques can determine whether a user is likely to visit a place during a future instance of a timeslot based at least in part on a location history associated with the user. The systems and techniques can then output information relating to the place prior to the beginning of the future instance of the timeslot.

Claims

1. A method comprising:

determining, by a computing system, information associated with a plurality of destinations proximate to a geographic location included in a location history associated with a user, the geographic location being associated with a time, the information associated with the plurality of destinations including, for each respective destination of the plurality of destinations, at least a name of the respective destination and a respective distance between the respective destination and the geographic location;

for each respective destination of the plurality of destinations, determining, by the computing system, based at least in part on

     1) the respective distance between the respective destination and the geographic location and

     2) a comparison between the time associated with the geographic location and a visit likelihood distribution across time, a visit likelihood associated with the respective destination, wherein the visit likelihood distribution across time comprises a plurality of visit likelihood values that each represent a respective likelihood that the user will visit the respective destination at a respective time on a respective day;

sorting, by the computing system and based at least in part on the visit likelihood associated with the respective destination, a portion of the plurality of destinations; and

outputting, by the computing system, an indication of the portion of the plurality of destinations.

2. The method of claim 1, wherein outputting, by the computing system, the indication of the portion of the plurality of destinations comprises outputting, by the computing system, to a mobile computing device, the indication of the portion of the plurality of destinations, such that the indication is output for display by the mobile computing device.

3. The method of claim 1, wherein the geographic location represents a cluster of proximate geographic location data points representing a visit to the geographic location, the visit having a visit start time and a visit end time.

4. The method of claim 3,

wherein the geographic location represents a plurality of visits to the geographic location, each respective visit of the plurality of visits having a respective visit start time and a respective visit end time, and

wherein determining the visit likelihood for the respective destination includes comparing each respective visit start time and respective visit end time to the visit likelihood distribution across time.

5. The method of claim 1,

wherein the information associated with the plurality of destinations proximate to the geographic location comprises a respective prominence score for each respective destination of the plurality of destinations, and

wherein determining the visit likelihood for the respective destination comprises determining the visit likelihood for the respective destination based at least in part on the respective distance between the respective destination and the geographic location, the comparison between the respective time associated with the geographic location and the visit likelihood distribution across time, and the respective prominence score.

6. The method of claim 1, wherein respective destinations of the plurality of destinations are associated with at least one destination category selected from a plurality of destination categories, each respective destination category having a visit likelihood distribution across time that is applied to respective destinations that are associated with the respective destination category.

7. A non-transitory computer-readable storage device storing instructions that, when executed, cause at least one processor of a computing device to:

determine, based at least in part on a plurality of proximate geographical location data points included in a location history associated with a user, a geographic location for a visit having a visit start time and a visit end time;

determine information associated with a plurality of destinations proximate to the geographic location, the information associated with the plurality of destinations including, for each respective destination of the plurality of destinations, at least a name of the destination and a respective distance between the respective destination and the geographic location;

for each respective destination of the plurality of destinations, determine, based at least in part on

     1) the respective distance between the respective destination and the geographic location,

     2) a comparison between the visit start time and a visit likelihood distribution across time, and

     3) a comparison between the visit end time and the visit likelihood distribution across time, a respective visit likelihood for the respective destination, wherein the visit likelihood distribution across time comprises a plurality of visit likelihood values that each represent a respective likelihood that the user will visit the respective destination at a respective time on a respective day;

sort, based at least in part on the respective visit likelihood associated with the respective destination, a portion of the plurality of destinations; and

output an indication of the portion of the plurality of destinations.

8. The non-transitory computer-readable storage device of claim 7, wherein the instructions that, when executed, cause at least one processor of a computing device to output the indication of the portion of the plurality of destinations comprise instructions that, when executed, cause the at least one processor of the computing device to output, to a mobile computing device, the indication of the portion of the plurality of destinations, such that the indication is output for display by the mobile computing device.

9. The non-transitory computer-readable storage device of claim 7,

wherein the geographic location represents a plurality of visits to the geographic location, with each respective visit of the plurality of visits having a respective visit start time and a respective visit end time,

further storing instructions that, when executed, cause the at least one processor of the computing device to determine the visit likelihood for the respective destination of the plurality of destinations by comparing each respective visit start time and respective visit end time to the visit likelihood distribution across time.

10. The non-transitory computer-readable storage device of claim 7,

wherein the information associated with the plurality of destinations proximate to the geographic location comprises a respective prominence score for each respective destination of the plurality of destinations,

further storing instructions that, when executed, cause the at least one processor of the computing device to determine the visit likelihood for the respective destination based at least in part on the respective distance between the respective destination and the geographic location, the comparison between the visit start time and the visit likelihood distribution across time, the comparison between the visit end time and the visit likelihood distribution across time, and the respective prominence score.

11. The non-transitory computer-readable storage device of claim 7, wherein respective destinations of the plurality of destinations are associated with at least one destination category selected from a plurality of destination categories, each respective destination category having a visit likelihood distribution across time that is applied to respective destinations that are associated with the respective destination category.