Constructing travel itineraries from tagged geo-temporal photographs

• US 8,285,483 B2
• Filed: 02/18/2010
• Issued: 10/09/2012
• Est. Priority Date: 02/18/2010
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Amer-Yahia, Sihem, De Choudhury, Munmun, Feldman, Moran, Golbandi, Nadav, Lempel, Ronny, Yu, Cong
• Primary Examiner(s): NGUYEN, TAN QUANG
• Application Number:
  US12/708,321
• Publication Number:
  US 20110202267A1
• Time in Patent Office: 964 Days
• Field of Search: 701/428, 701/437, 701/533, 705/6, 705/14, 348/211.3, 715/723, 715/202
• US Class Current: 701/428
• 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

Abstract

One embodiment accesses two or more photos taken by one or more travelers at one or more destinations and one or more points-of-interest located within the destinations; constructs one or more photo streams for each unique traveler-destination combination, wherein each one of the photo streams comprises two or more of the photos taken by the corresponding traveler at the corresponding destination; maps each one of the photos to one of the points-of-interest; constructs one or more timed paths for each unique traveler-destination combination based on the photo streams and the mapping between the photos and the points-of-interest, wherein each one of the timed paths comprises one or more of the points-of-interest located within the corresponding destination and visited by the corresponding travel; and constructs an itinerary based on a start point-of-interest, an end point-of-interest, a time constraint, and the timed paths.

Claims

1. A method comprising, by one or more computing devices:

accessing;

two or more photos, wherein each one of the photos is associated with a location and a time at which the photo is taken, and is taken by one of one or more travelers while visiting one of one or more destinations, and

one or more points-of-interest, wherein each one of the points-of-interest is located within one of the destinations;

constructing one or more photo streams for each unique traveler-destination combination, wherein each one of the photo streams comprises two or more of the photos taken by the corresponding traveler at the corresponding destination and ordered according to the respective times at which the photos are taken;

mapping each one of the photos to one of the points-of-interest;

constructing one or more timed paths for each unique traveler-destination combination based on the photo streams and the mapping between the photos and the points-of-interest, wherein each one of the timed paths comprises;

one or more of the points-of-interest located within the corresponding destination,

for each one of the points-of-interest located within the corresponding destination, a visit time representing a first amount of time the corresponding traveler spends at the point-of-interest, and

for each one of one or more pairs of points-of-interest located within the corresponding destination, a transit time representing a second amount of time it takes the corresponding traveler to travel from a first one of the pair of points-of-interest to a second one of the pair of points-of-interest; and

constructing an itinerary based on a start point-of-interest, an end point-of-interest, a time constraint, and the timed paths.

2. The method recited in claim 1, further comprising, for each one of the photo streams, between any two successive photos, if a difference between a first time at which a first one of the two successive photos is taken and a second time at which a second one of the two successive photos is taken is greater than a predetermined threshold, then dividing the photo stream into two new photo streams, replacing the old photo stream, wherein the first one of the two new photo streams comprises from a first photo to the first one of the two successive photos of the old photo stream, and the second one of the two new photo streams comprises from the second one of the two successive photos to a last photo of the old photo stream.

3. The method recited in claim 1, wherein for each one of the timed paths constructed for each traveler-destination combination:

the points-of-interest are ordered according to a sequence of the corresponding traveler visiting the points-of-interest,

for each one of the points-of-interest, the visit time is a difference between a first time a first photo is taken in connection with the point-of-interest and a second time a last photo is taken in connection with the point-of-interest based on the photo streams constructed for the traveler-destination combination, and

for each one of the pairs of points-of-interest, the transit time is a difference between a third time a last photo is taken in connection with the first one of the pair of points-of-interest and a fourth time a first photo is taken in connection with the second one of the pair of points-of-interest based on the photo streams constructed for the traveler-destination combination.

4. The method recited in claim 1, wherein:

each one of the points-of-interest is associated with a value determined base on popularity and visit duration of the point-of-interest, and

the additional points-of-interest of the itinerary are selected to maximize a total value of the points-of-interest of the itinerary.

5. The method recited in claim 1, wherein:

the itinerary comprises the start point-of-interest, the end point-of-interest, zero or more additional points-of-interest in-between the start point-of-interest and the end point-of-interest, and

a total amount of time needed to visit the start point-of-interest, the additional points-of-interest, and the end point-of-interest satisfies the time constraint.

6. The method recited in claim 5, wherein:

the start point-of-interest, the additional points-of-interest, and the end point-of-interest are located within a same one of the destinations, and

the total amount of time of the itinerary comprises the visit times of all the points-of-interest of the itinerary and the transmit times between all pairs of successive points-of-interest of the itinerary.

7. A system, comprising:

a memory comprising instructions executable by one or more processors; and

one or more processors coupled to the memory and operable to execute the instructions, the one or more processors being operable when executing the instructions to;

access;

two or more photos, wherein each one of the photos is associated with a location and a time at which the photo is taken, and is taken by one of one or more travelers while visiting one of one or more destinations, and

one or more points-of-interest, wherein each one of the points-of-interest is located within one of the destinations;

construct one or more photo streams for each unique traveler-destination combination, wherein each one of the photo streams comprises two or more of the photos taken by the corresponding traveler at the corresponding destination and ordered according to the respective times at which the photos are taken;

map each one of the photos to one of the points-of-interest;

construct one or more timed paths for each unique traveler-destination combination based on the photo streams and the mapping between the photos and the points-of-interest, wherein each one of the timed paths comprises;

one or more of the points-of-interest located within the corresponding destination,

for each one of the points-of-interest located within the corresponding destination, a visit time representing a first amount of time the corresponding traveler spends at the point-of-interest, and

for each one of one or more pairs of points-of-interest located within the corresponding destination, a transit time representing a second amount of time it takes the corresponding traveler to travel from a first one of the pair of points-of-interest to a second one of the pair of points-of-interest; and

construct an itinerary based on a start point-of-interest, an end point-of-interest, a time constraint, and the timed paths.

8. The system recited in claim 7, wherein the one or more processors are further operable when executing the instructions to, for each one of the photo streams, between any two successive photos, if a difference between a first time at which a first one of the two successive photos is taken and a second time at which a second one of the two successive photos is taken is greater than a predetermined threshold, then divide the photo stream into two new photo streams, replacing the old photo stream, wherein the first one of the two new photo streams comprises from a first photo to the first one of the two successive photos of the old photo stream, and the second one of the two new photo streams comprises from the second one of the two successive photos to a last photo of the old photo stream.

9. The system recited in claim 7, wherein for each one of the timed paths constructed for each traveler-destination combination:

the points-of-interest are ordered according to a sequence of the corresponding traveler visiting the points-of-interest,

for each one of the points-of-interest, the visit time is a difference between a first time a first photo is taken in connection with the point-of-interest and a second time a last photo is taken in connection with the point-of-interest based on the photo streams constructed for the traveler-destination combination, and

for each one of the pairs of points-of-interest, the transit time is a difference between a third time a last photo is taken in connection with the first one of the pair of points-of-interest and a fourth time a first photo is taken in connection with the second one of the pair of points-of-interest based on the photo streams constructed for the traveler-destination combination.

10. The system recited in claim 7, wherein:

each one of the points-of-interest is associated with a value determined base on popularity and visit duration of the point-of-interest, and

the additional points-of-interest of the itinerary are selected to maximize a total value of the points-of-interest of the itinerary.

11. The system recited in claim 7, wherein:

the itinerary comprises the start point-of-interest, the end point-of-interest, zero or more additional points-of-interest in-between the start point-of-interest and the end point-of-interest, and

a total amount of time needed to visit the start point-of-interest, the additional points-of-interest, and the end point-of-interest satisfies the time constraint.

12. The system recited in claim 11, wherein:

the start point-of-interest, the additional points-of-interest, and the end point-of-interest are located within a same one of the destinations, and

the total amount of time of the itinerary comprises the visit times of all the points-of-interest of the itinerary and the transmit times between all pairs of successive points-of-interest of the itinerary.

13. One or more computer-readable tangible storage media embodying software operable when executed by one or more computer systems to:

access;

two or more photos, wherein each one of the photos is associated with a location and a time at which the photo is taken, and is taken by one of one or more travelers while visiting one of one or more destinations, and

one or more points-of-interest, wherein each one of the points-of-interest is located within one of the destinations;

construct one or more photo streams for each unique traveler-destination combination, wherein each one of the photo streams comprises two or more of the photos taken by the corresponding traveler at the corresponding destination and ordered according to the respective times at which the photos are taken;

map each one of the photos to one of the points-of-interest;

construct one or more timed paths for each unique traveler-destination combination based on the photo streams and the mapping between the photos and the points-of-interest, wherein each one of the timed paths comprises;

one or more of the points-of-interest located within the corresponding destination,

for each one of the points-of-interest located within the corresponding destination, a visit time representing a first amount of time the corresponding traveler spends at the point-of-interest, and

for each one of one or more pairs of points-of-interest located within the corresponding destination, a transit time representing a second amount of time it takes the corresponding traveler to travel from a first one of the pair of points-of-interest to a second one of the pair of points-of-interest; and

construct an itinerary based on a start point-of-interest, an end point-of-interest, a time constraint, and the timed paths.

14. The media recited in claim 13, wherein the software is further operable when executed by the one or more computer systems to, for each one of the photo streams, between any two successive photos, if a difference between a first time at which a first one of the two successive photos is taken and a second time at which a second one of the two successive photos is taken is greater than a predetermined threshold, then divide the photo stream into two new photo streams, replacing the old photo stream, wherein the first one of the two new photo streams comprises from a first photo to the first one of the two successive photos of the old photo stream, and the second one of the two new photo streams comprises from the second one of the two successive photos to a last photo of the old photo stream.

15. The media recited in claim 13, wherein for each one of the timed paths constructed for each traveler-destination combination:

the points-of-interest are ordered according to a sequence of the corresponding traveler visiting the points-of-interest,

for each one of the points-of-interest, the visit time is a difference between a first time a first photo is taken in connection with the point-of-interest and a second time a last photo is taken in connection with the point-of-interest based on the photo streams constructed for the traveler-destination combination, and

for each one of the pairs of points-of-interest, the transit time is a difference between a third time a last photo is taken in connection with the first one of the pair of points-of-interest and a fourth time a first photo is taken in connection with the second one of the pair of points-of-interest based on the photo streams constructed for the traveler-destination combination.

16. The media recited in claim 13, wherein:

each one of the points-of-interest is associated with a value determined base on popularity and visit duration of the point-of-interest, and

the additional points-of-interest of the itinerary are selected to maximize a total value of the points-of-interest of the itinerary.

17. The media recited in claim 13, wherein:

the itinerary comprises the start point-of-interest, the end point-of-interest, zero or more additional points-of-interest in-between the start point-of-interest and the end point-of-interest, and

a total amount of time needed to visit the start point-of-interest, the additional points-of-interest, and the end point-of-interest satisfies the time constraint.

18. The media recited in claim 17, wherein:

the start point-of-interest, the additional points-of-interest, and the end point-of-interest are located within a same one of the destinations, and

the total amount of time of the itinerary comprises the visit times of all the points-of-interest of the itinerary and the transmit times between all pairs of successive points-of-interest of the itinerary.