System and method for recommending pleasant routes from the sentiment of geo-tagged photographs

• US 9,410,816 B2
• Filed: 05/07/2014
• Issued: 08/09/2016
• Est. Priority Date: 05/07/2014
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Schifanella, Rossano, Aiello, Luca Maria, Quercia, Daniele
• Primary Examiner(s): CAMBY, RICHARD M
• Application Number:
  US14/271,960
• Publication Number:
  US 20150323337A1
• Time in Patent Office: 825 Days
• Field of Search: 701/533
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3407 specially adapted for specific applications
• CPC Class Codes: G01C 21/3453 Special cost functions, i.e. other than distance or default speed limit of road segments
• CPC Class Codes: G01C 21/3476 using point of interest [POI] information, e.g. a route passing visible POIs
• CPC Class Codes: G01C 21/36 Input/output arrangements for on-board computers
• CPC Class Codes: G01C 21/3676 Overview of the route on the road map
• CPC Class Codes: G01C 21/3682 output of POI information on a road map G01C21/3614, G01C21/3685 take precedence
• CPC Class Codes: G06N 5/04 Inference or reasoning models
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

A system and method generates and recommends a short and pleasant path between a source s and destination d in a geo-location such as a city or city center. The routes are not only short but emotionally pleasant, offering an engaging user experience, going beyond just showing paths on a map.

Claims

1. A method for providing a pleasant route within a geographic location, comprising:

receiving a source address and a destination address within the geographic location;

building a location graph of the geographic location with nodes representing sites within the geographic location, wherein building the location graph comprises;

building a geographical bounding box for the geographic location;

dividing the geographical bounding box into a plurality of cells, wherein a size of each cell is associated with a walkable distance; and

linking geographic neighboring cells of the plurality of cells to form the location graph;

computing one or more pleasantness scores for the nodes;

selecting a route from the source address to the destination address responsive to determining that one or more pleasantness scores associated with the route are higher than one or more other pleasantness scores; and

presenting the route on a map of the geographic location.

2. The method of claim 1, wherein computing the one or more pleasantness scores comprises:

computing a first pleasantness score for a first node of the nodes; and

computing a second pleasantness score for a second node of the nodes.

3. The method of claim 1, comprising:

weighting links between neighboring cells by a geographic distance between cell centroids.

4. The method of claim 1, wherein computing the one or more pleasantness scores comprises retrieving data about the nodes from a crowdsourcing website.

5. The method of claim 1, wherein computing the one or more pleasantness scores comprises accessing geo-tagged photos of the geographic location.

6. The method of claim 5, comprising processing tags associated with the geo-tagged photos to capture words expressing emotional and cognitive perceptions of a node.

7. The method of claim 5, comprising gathering statistics for the geo-tagged photos to predict one or more scores for a node in association with each of the attributes of quiet, happy, and beauty.

8. The method of claim 1, wherein selecting the route comprises:

identifying M shortest paths connecting the source address and the destination address;

iteratively computing an average rank for locations within m paths, wherein m is less than M;

at each iteration, recording a path with a best average rank; and

terminating when the best average rank improves less than a predetermined amount.

9. An information processing system for providing a pleasant route within a geographic location, the information processing system comprising:

a processor device; and

a memory operably coupled with the processor device, the memory comprising computer-executable instructions causing a computer to perform;

receiving a source address and a destination address within the geographic location;

building a location graph of the geographic location with nodes representing sites within the geographic location;

computing one or more pleasantness scores for the nodes, wherein computing the one or more pleasantness scores comprises accessing geo-tagged photos of the geographic location and at least one of;

processing tags associated with the geo-tagged photos to capture words expressing emotional and cognitive perceptions of a node;

or

gathering statistics for the geo-tagged photos to predict one or more scores for the node in association with each of the attributes of quiet, happy, and beauty;

selecting a route from the source address to the destination address responsive to determining that one or more pleasantness scores associated with the route are higher than one or more other pleasantness scores; and

presenting the route on a map of the geographic location.

10. The information processing system of claim 9, wherein the computer-executable instructions for building the location graph comprise:

building a geographical bounding box for the geographic location;

dividing the geographical bounding box into a plurality of cells, wherein a size of each cell is associated with a walkable distance; and

linking geographic neighboring cells of the plurality of cells to form the location graph.

11. The information processing system of claim 10, wherein the computer-executable instructions comprise weighting links between neighboring cells by a geographic distance between cell centroids.

12. The information processing system of claim 9, wherein the computer-executable instructions for computing the one or more pleasantness scores comprise retrieving data about the nodes from a crowdsourcing website.

13. The information processing system of claim 9, wherein the computer-executable instructions for computing the one or more pleasantness scores comprise the processing and the gathering.

14. The information processing system of claim 9, wherein the computer-executable instructions for selecting the route comprise selecting the route from amongst two or more routes comprising the route and a second route.

15. The information processing system of claim 14, wherein the second route is associated with at least one of the one or more other pleasantness scores.

16. The information processing system of claim 9, wherein the computer-executable instructions for selecting the route comprise:

identifying M shortest paths connecting the source address and the destination address;

iteratively computing an average rank for locations within m paths, wherein m is less than M;

at each iteration, recording a path with a best average rank; and

terminating when the best average rank improves less than a predetermined amount.

17. A computer program product comprising a non-transitory computer-readable storage medium with computer-executable instructions stored thereon, the computer-executable instructions comprising:

receiving a source address and a destination address within a geographic location;

building a location graph of the geographic location with nodes representing sites within the geographic location;

computing one or more pleasantness scores for the nodes;

selecting a route from the source address to the destination address responsive to determining that one or more pleasantness scores associated with the route are higher than one or more other pleasantness scores, wherein selecting the route comprises obtaining three paths between the source address and the destination address by repeating the following acts in association with attributes of beauty, quiet, and happy;

identifying M shortest paths connecting the source address and the destination address;

iteratively computing an average rank for locations within m paths, wherein m is less than M;

at each iteration, recording a path with a best average rank; and

terminating when the best average rank improves less than a predetermined amount; and

presenting the route on a map of the geographic location.

18. The computer program product of claim 17, wherein the computer-executable instructions for selecting the route comprise selecting the route from amongst two or more routes comprising the route and a second route.

19. The computer program product of claim 17, wherein the computer-executable instructions for building the location graph comprise:

building a geographical bounding box for the geographic location;

dividing the geographical bounding box into a plurality of cells, wherein a size of each cell is associated with a walkable distance; and

linking geographic neighboring cells of the plurality of cells to form the location graph.

20. The computer program product of claim 19, wherein the computer-executable instructions comprise weighting links between neighboring cells by a geographic distance between cell centroids.