Travelogue-based travel route planning

• US 8,275,546 B2
• Filed: 09/29/2009
• Issued: 09/25/2012
• Est. Priority Date: 09/29/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Xiao, Rong, Yang, Jiangming, Zhang, Lei
• Primary Examiner(s): Zanelli, Michael J.
• Application Number:
  US12/568,725
• Publication Number:
  US 20110077848A1
• Time in Patent Office: 1,092 Days
• Field of Search: None
• US Class Current: 701/533
• 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

Abstract

A location extraction component analyzes a set of travelogues to identify locations mentioned therein. A co-occurrence extraction component computes co-occurrence values for the identified locations. When a request to generate a travel route from a starting location to an ending location is received, suggested locations on or near the travel route are identified through the use of the co-occurrence values. A suggested travel route is then generated that passes through the starting location, the ending location, and the suggested locations. A map may be displayed showing the starting location, the ending location, the suggested locations, and the suggested travel route.

Claims

1. A computer-implemented method for travelogue-based travel route planning, the computer-implemented method comprising performing computer-implemented operations for:

identifying a plurality of locations in a set of travelogues;

computing co-occurrence values for the identified locations;

receiving a request to generate a travel route, the request comprising data identifying a starting location and an ending location; and

in response to receiving the request to generate the travel route, determining a first travel route between the starting location and the ending location, identifying one or more suggested locations on or near the first travel route using the co-occurrence values, determining a second travel route passing through the starting location, the ending location, and the suggested locations, and causing the second travel route to be displayed.

2. The computer-implemented method of claim 1, wherein each travelogue comprises a text description of an experience with a location.

3. The computer-implemented method of claim 2, wherein each co-occurrence value comprises an integer value specifying the number of times a first location and a second location are mentioned within the same travelogue for travelogues within the set of travelogues.

4. The computer-implemented method of claim 3, wherein determining a first travel route comprises performing a shortest path computation between the starting location and the ending location to identify the first travel route.

5. The computer-implemented method of claim 3, wherein determining a first travel route comprises performing a fastest path computation between the starting location and the ending location to identify the first travel route.

6. The computer-implemented method of claim 3, wherein identifying one or more suggested locations on or near the first travel route using the co-occurrence values comprises:

identifying one or more locations on the first travel route; and

for each location identified on the first travel route, identifying one or more suggested locations, each of the suggested locations having a non-zero co-occurrence value with a location identified on the first travel route.

7. The computer-implemented method of claim 6, wherein identifying one or more suggested locations on or near the first travel route using the co-occurrence values further comprises filtering the identified suggested locations that are more than a threshold distance away from the first travel route.

8. The computer-implemented method of claim 7, wherein the second travel route passing through the starting location, the ending location, and the suggested locations is computed using a traveling salesman algorithm.

9. The computer-implemented method of claim 7, wherein causing the second travel route to be displayed comprises causing a map to be displayed, the map showing the starting location, the ending location, the suggested locations, and the second travel route.

10. A computer-readable storage medium having computer-readable instructions stored thereupon which, when executed by a computer, cause the computer to:

store one or more travelogues;

execute a location extraction component to identify one or more locations within the travelogues;

execute a co-occurrence extraction component to compute co-occurrence values for pairs of locations identified within the travelogues;

receive a request to generate a travel route, the request comprising data identifying a starting location and an ending location; and

in response to receiving the request to generate the travel route, to determine a first travel route between the starting location and the ending location, to identify one or more suggested locations on or near the first travel route using the co-occurrence values, to determine a second travel route passing through the starting location, the ending location, and the suggested locations, and to cause the second travel route to be displayed.

11. The computer-readable storage medium of claim 10, wherein each co-occurrence value comprises an integer value specifying the number of times a first location and a second location are mentioned within the same travelogue for travelogues within the set of travelogues.

12. The computer-readable storage medium of claim 11, wherein each travelogue comprises a text description of an experience with a location.

13. The computer-readable storage medium of claim 12, wherein determine a first travel route comprises performing a shortest path computation between the starting location and the ending location to identify the first travel route.

14. The computer-readable storage medium of claim 12, wherein determine a first travel route comprises performing a fastest path computation between the starting location and the ending location to identify the first travel route.

15. The computer-readable storage medium of claim 12, wherein determine a second travel route comprises performing a traveling salesman algorithm to determine the second travel route passing through the starting location, the ending location, and the suggested locations.

16. The computer-readable storage medium of claim 15, wherein identify one or more suggested locations on or near the first travel route using the co-occurrence values comprises:

identifying one or more locations on the first travel route; and

for each location identified on the first travel route, identifying one or more suggested locations, each of the suggested locations having a non-zero co-occurrence value with a location identified on the first travel route.

17. The computer-readable storage medium of claim 16, wherein identify one or more suggested locations on or near the first travel route using the co-occurrence values further comprises filtering the identified suggested locations that are more than a threshold distance away from the first travel route.

18. The computer-readable storage medium of claim 17, wherein cause the second travel route to be displayed comprises causing a map to be displayed, the map showing the starting location, the ending location, the suggested locations, and the second travel route.

19. A computer-implemented method for travelogue-based travel route planning, the computer-implemented method comprising performing computer-implemented operations for:

storing one or more travelogues, each of the travelogues comprising a text description of an experience with a location;

executing a location extraction component configured to identify one or more locations within the travelogues;

executing a co-occurrence extraction component configured to compute co-occurrence values for pairs of locations identified within the travelogues, each of the co-occurrence values comprising an integer specifying the number of times a pair of locations are mentioned within the same travelogue for all of the travelogues;

receiving a request to generate a travel route, the request comprising data identifying a starting location and an ending location; and

in response to receiving the request to generate the travel route,

to determine a first travel route between the starting location and the ending location,

to identify one or more locations on the first travel route and for each location identified on the first travel route, identifying one or more suggested locations, each of the suggested locations having a non-zero co-occurrence value with a location identified on the first travel route,

to determine a second travel route passing through the starting location, the ending location, and the suggested locations, and

to cause the second travel route to be displayed.

20. The computer-implemented method of claim 19, wherein suggested locations that are more than a threshold distance away from the first travel route are removed from the second travel route, wherein the first travel route is computed using a shortest path algorithm, wherein the second travel route is computed using a traveling salesman algorithm, and wherein cause the second travel route to be displayed comprises causing a map to be displayed, the map showing the starting location, the ending location, the suggested locations, and the second travel route.