Where to go next via mined trails

• US 9,367,589 B1
• Filed: 11/14/2013
• Issued: 06/14/2016
• Est. Priority Date: 11/14/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Swietlicka, Joanna Franciszka, Mansoor, Hassan, Farrell, Richard Michael, Dhillon, Samreen, Asara, Federico, Stuttle, Matthew Nicholas, Drner, Sebastian, Gherghina, Alexandra, Brunschen, Christian, Kim, Evelyn, Nicholas, Tyrone
• Primary Examiner(s): Choi, Yuk Ting
• Application Number:
  US14/080,772
• Time in Patent Office: 943 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

A system and method for providing destination recommendations to a user based on mining of a location history. The location history provides information on locations visited by users of the system over time. The system mines the location history to identify location pairs. Each location pair comprises an originating location visited by a user and a next location that was visited by the user within a defined time threshold of visiting the originating location. The system aggregates location pairs by common originating location. The system then takes into account the current location of a requesting user. The system uses the current location information to identify a corresponding originating location in a location history index. The system provides recommendations based at least in part on how frequently certain next locations were visited after visiting the originating location.

Claims

1. A computer-implemented method running on one or more computing devices comprising:

receiving one or more next locations from one or more other remote computing devices for an origination location;

receiving a location-based signal from a remote computing device associated with a user, the location-based signal indicating a current location of the remote computing device and comprising one of a check-in signal, a post to a social network account associated with the user, and a time-stamped set of GPS coordinates;

identifying the originating location in a location history index corresponding to the current location, wherein the originating location has the one or more next locations associated with the originating location, the one or more next locations corresponding to locations where the one or more other remote computing devices were located within a time threshold after being located in the originating location;

generating a destination recommendation list comprising the one or more next destinations ranked based at least in part on a visit frequency, the visit frequency indicating how frequently a next location was visited after visiting the originating location by the other remote computing devices;

identifying a user profile associated with the user comprising personal preference categories;

determining a confidence value for each next destination on the destination recommendation list by;

comparing one or more categories associated with each respective next destination with the personal preference categories; and

increasing the respective confidence value for the respective next destination when one of the one or more categories associated with each respective next destination matches one of the personal preference categories; and

determining if the confidence value for each next destination exceeds a confidence threshold value, wherein the next destination is removed from destination recommendation list if the confidence value for the next destination does not exceed the confidence threshold; and

transmitting the destination recommendation list to the remote computing device consequent to determining if the confidence value for each next destination exceeds the confidence threshold value for presentation via the remote computing device.

2. The method of claim 1, further comprising annotating, by the one or more computing devices each respective next destination in the destination recommendation list based on the preference profile associated with the user prior to transmitting the destination recommendation list.

3. The method of claim 1, further comprising annotating, by the one or more computing devices, the one or more next destinations with one or more of a distance from the current location to the next location, a route from the current location to the next location, transit options, reviews or ratings of the next location, and a promotional offer for the next location.

4. The method of claim 1, wherein only a top ranked destination recommendation from the destination recommendation list is transmitted to the remote computing device.

5. The method of claim 1, wherein next locations with a visit frequency below a frequency threshold are not included in the destination recommendation list.

6. A computer program product, comprising:

a non-transitory computer-executable storage device having computer-executable program instructions embodied thereon that when executed by a computer cause the computer to provide destination recommendations, the computer-executable program instructions comprising;

computer-executable program instructions to receive one or more next locations from one or more other remote computing devices for an originating location;

computer-executable program instructions to receive a location-based signal from a remote computing device associated with a user, the location-based signal indicating a current location of the remote computing device and comprising one of a check-in signal, a post to a social network account associated with the user, and a time-stamped set of GPS coordinates;

computer-executable program instruction to identify the originating location in a location history index corresponding to the current location, wherein the originating location has the one or more next locations associated with the originating location, the one or more next locations corresponding to locations where the one or more other remote computing devices were located-within a time threshold after being located in the originating location;

computer-executable program instructions to generate a destination recommendation list comprising the one or more next destinations;

computer-executable program instructions to identify a user profile associated with the user comprising personal preference categories;

computer-executable program instructions to determine a confidence value for each next destination on the destination recommendation list by;

comparing one or more categories associated with each respective next destination with the personal preference categories; and

increasing the respective confidence value for the respective next destination when one of the one or more categories associated with each respective next destination matches one of the personal preference categories; and

computer-executable program instructions to determine if the confidence value for each next destination exceeds a confidence threshold value, wherein the next destination is removed from the destination recommendation list if the confidence value for the next destination does not exceed the confidence threshold; and

computer-executable program instructions to transmit the destination recommendation list to the remote computing device consequent to determining if the confidence value for each next destination exceeds the confidence threshold value.

7. The computer program product of claim 6, wherein the recommendation list comprises the one or more next destinations ranked based at least in part on a visit frequency, the visit frequency indicating how frequently a next location was visited after visiting the originating location.

8. The computer program product of claim 6, the computer-executable program instructions further comprising:

computer-executable program instructions to further increase the respective confidence value for the respective next destination based on reviews or ratings from members of a social graph of the user.

9. The computer program product of claim 6, further comprising computer-executable program instructions to annotate each respective next destination in the recommendation list based on preference profile associated with the user prior to transmitting the destination recommendation list.

10. The computer program product of claim 6, further comprising computer-executable program instructions to annotate the one or more next destinations with one or more of a distance from the current location to the next location, a route from the current location to the next location, transit options, reviews or ratings of the next location, and a promotional offer for the next location.

11. The computer program product of claim 6, wherein only a top ranked destination recommendation from the destination recommendation list is transmitted to the remote computing device.

12. The computer program product of claim 6, wherein next locations with a visit frequency below a frequency threshold are not included in the destination recommendation list.

13. A system to provide destination recommendations, comprising:

a storage device; and

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

receive one or more next locations from one or more other remote computing devices for an originating location;

receive a location-based signal from a remote computing device associated with a user, the location-based signal indicating a current location of the remote computing device and comprising one of a check-in signal, a post to a social network account associated with the user, and a time-stamped set of GPS coordinates or a combination thereof;

identify the originating location in a location history index corresponding to the current location, wherein the originating location has the one or more next locations associated with the originating location, the one or more next locations corresponding to locations where the one or more other remote computing devices were located within a time threshold after being located in the originating location;

generate a destination recommendation list comprising the one or more next destinations;

identify a user profile associated with the user comprising personal preference categories;

determine a confidence value for each next destination on the destination recommendation list by;

comparing one or more categories associated with each respective next destination with the personal preference categories; and

increasing the respective confidence value for the respective next destination when one of the one or more categories associated with each respective next destination matches one of the personal preference categories; and

determine if the confidence value for each next destination exceeds a confidence threshold value, wherein the next destination is removed from the destination recommendation list if the confidence value for the next destination does not exceed the confidence threshold; and

transmit the destination recommendation list to the remote computing device consequent to determining if the confidence value for each next destination exceeds the confidence threshold value.

14. The system of claim 13, wherein the processor further executes application code instructions that cause the system to:

further increase the respective confidence value for the respective next destination based on reviews or ratings from members of a social graph of the user.

15. The system of claim 13, wherein the recommendation list comprises the one or more next destinations ranked based at least in part on a visit frequency, the visit frequency indicating how frequently a next location was visited after visiting the originating location.

16. The system of claim 13, wherein the processor further executes application code instructions that cause the system to annotate each respective next destination in the destination recommendation list based on the preference profile associated with the user prior to transmitting the destination recommendation list.

17. The system of claim 13, wherein the processor further executes application code instructions to annotate the one or more next destinations with one or more of a distance from the current location to the next location, a route from the current location to the next location, transit options, reviews or ratings of the next location, and a promotional offer for the next location.

18. The system of claim 13, wherein only a top ranked destination recommendation from the destination recommendation list is transmitted to the remote computing device, and is displayed on a general user interface of the remote computing device.

19. The system of claim 13, wherein next locations with a visit frequency below a frequency threshold are not included in the destination recommendation list.