Systems and methods to suggest travel itineraries based on users' current location

• US 8,818,715 B2
• Filed: 03/29/2012
• Issued: 08/26/2014
• Est. Priority Date: 03/29/2012
• Status: Expired due to Fees

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Hepworth, Guy, Mahapatro, Arun, Sao, Anshul, Klein, Matt
• Primary Examiner(s): Shafi, Muhammad
• Application Number:
  US13/434,074
• Publication Number:
  US 20130261957A1
• Time in Patent Office: 880 Days
• Field of Search: 701/426, 701/436, 701/437, 701/438, 340/995.24, 340/995.19
• US Class Current: 701/426
• 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/3476 using point of interest [POI] information, e.g. a route passing visible POIs
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 50/01 Social networking

Abstract

Data relating to points-of-interest for a geographical area are retrieved from, for example, a travel site. Geo-tagged data relating to the points-of-interest are retrieved, for example, images from an image sharing service. Travel times between the points-of-interest are determined, for example, using a mapping service. The data relating to the points of interest, the geo-tagged data and the travel times are used to create a travel graph for the geographical area, such that the geo-tagged data is used to determine time users spend at specific points of interest. If a user requests a travel itinerary for a beginning and ending location within the geographical area, the travel graph is used to create a travel itinerary that maximizes a prize score for the itinerary within a time constraint. The prize score can reflect the popularity, number of users and time spent by users at the points-of-interest in the itinerary.

Claims

1. A method comprising:

receiving, using a computing device, from a user device, a request for a travel itinerary, the request comprising a starting location and an ending location within a geographic area and a time constraint;

retrieving, using the computing device, a travel graph for the geographic area, the travel graph comprising a plurality of nodes, each respective node corresponding to a respective one point-of-interest of a plurality of points of interest, where each respective node of the plurality of nodes is associated with respective node level data comprising a respective location, a plurality of travel times between the respective node and at least a subset of the plurality of nodes, a respective popularity score for the node, a respective number of users visiting the node and a respective average time spent by users at the respective node;

calculating, using the computing device, respective prize score for each node of the plurality of nodes;

selecting, using the computing device, a first node of the plurality of nodes that is nearest to the starting location;

selecting, using the computing device, a second node of the plurality of nodes that is nearest to the ending location;

determining, using the computing device, a travel itinerary using the travel graph and the respective prize scores for each of the plurality of nodes, such that the travel itinerary comprises the first node of the plurality of nodes, the second node of the plurality of nodes and a plurality of additional nodes selected from the plurality of nodes, where the plurality of additional nodes are selected from the plurality of nodes such that a total prize score for the plurality of additional nodes is maximized within the time constraint; and

communicating, using the computing device, a representation of the travel itinerary to the user device.

2. The method of claim 1, wherein the respective prize scores for each of the plurality of nodes is determined using the respective popularity score for the node, the respective number of users visiting the node and the respective average time spent by users at the respective node.

3. The method of claim 2, wherein the respective prize scores for each of the plurality of nodes is determined utilizing an algorithm of the form:

(the respective popularity score of the node)*

(the respective number of users visiting node)*

(the respective average time spent by users in minutes visiting the node)/100.

4. The method of claim 1 wherein the plurality of additional nodes are selected using a recursive greedy algorithm.

5. The method of claim 4 wherein the recursive greedy algorithm identifies shortest paths between nodes.

6. The method of claim 1 wherein the time constraint reflects a time available to the user and a desired start time and a desired end time.

7. A method comprising:

retrieving, using a computing device, point-of-interest data relating to a plurality of points of interest within a geographic area, the point-of-interest data comprising, for each point-of-interest of the plurality of points of interest, a respective popularity score and a respective location;

retrieving, using the computing device, geo-tagged data comprising a plurality of geo-tagged objects, each geo-tagged object of the plurality of geo-tagged objects relating to a respective one point-of-interest of the plurality of points of interest and comprising a respective date and time and a respective one user of a plurality of users;

determining, using the computing device, using the geo-tagged data, for each point-of-interest of the plurality of points of interest, a respective average time spent by the plurality of users at the respective point-of-interest;

determining, using the computing device, a plurality of travel times, each respective travel time of the plurality of travel times comprising a travel time between a respective first one point-of-interest of the plurality of points-of-interest and a respective second one point-of-interest of the plurality of points-of-interest; and

creating, using the computing device, a travel graph for the geographical location based on the point-of-interest data, the respective average time spent by the plurality of users at each respective point-of-interest and the plurality of travel times, such that the travel graph comprises a plurality of nodes, each respective node corresponding to a respective one point-of-interest of the plurality of points of interest, where each respective node of the plurality of nodes is associated with respective node level data, comprising a respective location, a plurality of travel times between the respective node and at least a subset of the plurality of nodes, a respective popularity score for the node, a respective number of users visiting the node and a respective average time spent by users at the respective node.

8. The method of claim 7,

where the respective average time spent by users at the respective point-of-interest is calculated by dividing a respective total time spent by the plurality of users at the respective point-of-interest by a respective total number of users visiting the respective point-of-interest,

where, for each user of the plurality of users visiting the respective point-of-interest, the respective time spent by the respective user is determined by time is determined by a subtracting a respective date and time of an earliest respective geo-tagged object of the plurality of geo-tagged objects associated with a respective user and a respective point-of-interest and a respective date and time of a latest respective geo-tagged object associated with the respective user and the respective point-of-interest.

9. The method of claim 7, further comprising:

filtering, using the computing device, the plurality of geo-tagged objects utilizing a filtration technique, such that a subset of the plurality of geo-tagged objects are discarded.

10. The method of claim 9, wherein the filtration technique comprises verifying the respective location associated with each geo-tagged object of the plurality of geo-tagged objects such that where the respective location is not within a threshold distance of the respective point-of-interest of the plurality of interests to which the geo-tagged object relates, the respective geo-tagged object is discarded.

11. The method of claim 9, wherein the filtration technique comprises, determining, for each user of the plurality of users, a respective number of geo-tagged objects for the respective user and a respective date, such that where the respective number of geo-tagged objects for the respective user and a respective date is not greater than a threshold number of geo-tagged objects, the respective geo-tagged objects of the plurality of geo-tagged objects associated with the respective date and the respective user ID are discarded.

12. The method of claim 9, wherein the filtration technique comprises, determining, for each user of the plurality of users, if the respective user is a resident of the geographical area, such that where the respective user of the plurality of users is a resident of the geographic area, the respective geo-tagged objects associated with the respective user.

13. The method of claim 9, wherein the filtration technique comprises, determining, for each user of the plurality of users, a respective time span between a respective date and time of an earliest respective geo-tagged object of the plurality of geo-tagged objects associated with a respective user and a respective point-of-interest and a respective date and time of a latest respective geo-tagged object associated with the respective user and the respective point-of-interest, such that where the respective time span is less than a minimum threshold, the respective geo-tagged objects associated with the respective user and a respective point-of-interest are discarded.

14. The method of claim 7, wherein the plurality of points of interest relate to a fixed number of most popular points of interest on a website.

15. The method of claim 7, wherein the plurality of travel times are determined utilizing a mapping service.

16. The method of claim 7 wherein each of the plurality of geo-tagged objects is an image.

17. A non-transitory computer readable storage media for tangibly storing thereon computer readable instructions for a method comprising:

receiving from a user device, a request for a travel itinerary, the request comprising a starting location and an ending location within a geographic area and a time constraint;

retrieving a travel graph for the geographic area, the travel graph comprising a plurality of nodes, each respective node corresponding to a respective one point-of-interest of a plurality of points of interest, where each respective node of the plurality of nodes is associated with respective node level data comprising a respective location, a plurality of travel times between the respective node and at least a subset of the plurality of nodes, a respective popularity score for the node, a respective number of users visiting the node and a respective average time spent by users at the respective node;

calculating respective prize score for each node of the plurality of nodes;

selecting a first node of the plurality of nodes that is nearest to the starting location;

selecting a second node of the plurality of nodes that is nearest to the ending location;

determining a travel itinerary using the travel graph and the respective prize scores for each of the plurality of nodes, such that the travel itinerary comprises the first node of the plurality of nodes, the second node of the plurality of nodes and a plurality of additional nodes selected from the plurality of nodes, where the plurality of additional nodes are selected from the plurality of nodes such that a total prize score for the plurality of additional nodes is maximized within the time constraint; and

communicating a representation of the travel itinerary to the user device.

18. A non-transitory computer readable storage media for tangibly storing thereon computer readable instructions for a method comprising:

retrieving point-of-interest data relating to a plurality of points of interest within a geographic area, the point-of-interest data comprising, for each point-of-interest of the plurality of points of interest, a respective popularity score and a respective location;

retrieving geo-tagged data comprising a plurality of geo-tagged objects, each geo-tagged object of the plurality of geo-tagged objects relating to a respective one point-of-interest of the plurality of points of interest and comprising a respective date and time and a respective one user of a plurality of users;

determining using the geo-tagged data, for each point-of-interest of the plurality of points of interest, a respective average time spent by the plurality of users at the respective point-of-interest;

determining a plurality of travel times, each respective travel time of the plurality of travel times comprising a travel time between a respective first one point-of-interest of the plurality of points-of-interest and a respective second one point-of-interest of the plurality of points-of-interest; and

creating a travel graph for the geographical location based on the point-of-interest data, the respective average time spent by the plurality of users at each respective point-of-interest and the plurality of travel times, such that the travel graph comprises a plurality of nodes, each respective node corresponding to a respective one point-of-interest of the plurality of points of interest, where each respective node of the plurality of nodes is associated with respective node level data, comprising a respective location, a plurality of travel times between the respective node and at least a subset of the plurality of nodes, a respective popularity score for the node, a respective number of users visiting the node and a respective average time spent by users at the respective node.

19. A computing device comprising:

a processor;

a storage medium for tangibly storing thereon program logic for execution by the processor, the program logic comprising;

logic executed by the processor for

logic executed by the processor for receiving from a user device, a request for a travel itinerary, the request comprising a starting location and an ending location within a geographic area and a time constraint;

logic executed by the processor for retrieving a travel graph for the geographic area, the travel graph comprising a plurality of nodes, each respective node corresponding to a respective one point-of-interest of a plurality of points of interest, where each respective node of the plurality of nodes is associated with respective node level data comprising a respective location, a plurality of travel times between the respective node and at least a subset of the plurality of nodes, a respective popularity score for the node, a respective number of users visiting the node and a respective average time spent by users at the respective node;

logic executed by the processor for calculating respective prize score for each node of the plurality of nodes;

logic executed by the processor for selecting a first node of the plurality of nodes that is nearest to the starting location;

logic executed by the processor for selecting a second node of the plurality of nodes that is nearest to the ending location;

logic executed by the processor for determining a travel itinerary using the travel graph and the respective prize scores for each of the plurality of nodes, such that the travel itinerary comprises the first node of the plurality of nodes, the second node of the plurality of nodes and a plurality of additional nodes selected from the plurality of nodes, where the plurality of additional nodes are selected from the plurality of nodes such that a total prize score for the plurality of additional nodes is maximized within the time constraint; and

communicating a representation of the travel itinerary to the user device.

20. A computing device comprising:

a processor;

a storage medium for tangibly storing thereon program logic for execution by the processor, the program logic comprising;

logic executed by the processor for retrieving point-of-interest data relating to a plurality of points of interest within a geographic area, the point-of-interest data comprising, for each point-of-interest of the plurality of points of interest, a respective popularity score and a respective location;

logic executed by the processor for retrieving geo-tagged data comprising a plurality of geo-tagged objects, each geo-tagged object of the plurality of geo-tagged objects relating to a respective one point-of-interest of the plurality of points of interest and comprising a respective date and time and a respective one user of a plurality of users;

logic executed by the processor for determining using the geo-tagged data, for each point-of-interest of the plurality of points of interest, a respective average time spent by the plurality of users at the respective point-of-interest;

logic executed by the processor for determining a plurality of travel times, each respective travel time of the plurality of travel times comprising a travel time between a respective first one point-of-interest of the plurality of points-of-interest and a respective second one point-of-interest of the plurality of points-of-interest; and

logic executed by the processor for creating a travel graph for the geographical location based on the point-of-interest data, the respective average time spent by the plurality of users at each respective point-of-interest and the plurality of travel times, such that the travel graph comprises a plurality of nodes, each respective node corresponding to a respective one point-of-interest of the plurality of points of interest, where each respective node of the plurality of nodes is associated with respective node level data, comprising a respective location, a plurality of travel times between the respective node and at least a subset of the plurality of nodes, a respective popularity score for the node, a respective number of users visiting the node and a respective average time spent by users at the respective node.