Discovering theme and attribute oriented travel routes and relevant geographic entities along a route

• US 9,234,765 B1
• Filed: 05/21/2014
• Issued: 01/12/2016
• Est. Priority Date: 06/05/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Padovitz, Amir, Java, Akshay N.
• Primary Examiner(s): Jeanglaude, Gertrude Arthur
• Application Number:
  US14/283,417
• Time in Patent Office: 601 Days
• Field of Search: 701/28, 701/36, 701/425, 701/438, 701/409, 701/533, 701/461, 707/737, 707/748
• US Class Current: 1/1
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/3453 Special cost functions, i.e. other than distance or default speed limit of road segments
• CPC Class Codes: G09B 29/003 Maps
• CPC Class Codes: G09B 29/10 Map spot or coordinate position indicators; Map reading aids optical projection apparatus per se G03B

Abstract

Methods, systems, and apparatus include computer programs encoded on a computer-readable storage medium, including a method for determining routes. Starting and destination points, and any user constraints, are identified for travel. Initial routes are determined between the starting and destination points. Each initial route is segmented into segments. Attribute oriented routes are determined using the segments. Entities associated with each segment are determined. Attributes are identified for each entity and are aggregated and ranked along all the determined initial routes, and emerging attributes are determined. Attribute oriented routes are determined based on the emerging attributes including: identifying a theme for an attribute oriented route, identifying a set of entities from the determined entities that are associated with the emerging attributes, and creating the attribute oriented route that passes through a region that includes the entities. At least one attribute oriented route and information related to the theme are provided.

Claims

1. A computer-implemented method, comprising:

identifying a starting point and a destination point for travel by a user including any constraints of the user regarding the travel;

determining one or more initial routes between the starting point and the destination point;

for each initial route, segmenting the route into a plurality of segments based on one or more criteria; and

determining attribute oriented routes using the segments including;

determining one or more entities associated with each segment;

identifying attributes for each determined entity;

aggregating and ranking the attributes along all the determined initial routes and determining one or more emerging attributes;

determining one or more attribute oriented routes based on the emerging attributes including identifying a theme for an attribute oriented route based on one or more of the emerging attributes, identifying a set of entities from the determined entities that are associated with the one or more emerging attributes, and creating the attribute oriented route that passes through a region that includes the set of entities, wherein determining one or more attribute oriented routes includes scoring a particular region based on matching emerging attributes of the particular region compared to one or more goals and determining routes that maximize an aggregate rank based on the scoring under the constraints; and

providing at least one attribute oriented route and information related to the theme to a device associated with the user.

2. The method of claim 1 wherein identifying includes receiving the starting point, destination point and constraints, and wherein the constraints include limitations that affect a choice of the attribute oriented route.

3. The method of claim 1 wherein determining the one or more initial routes further includes determining a plurality of direct routes between the starting point and the destination point.

4. The method of claim 1 wherein the one or more criteria is a distance criterion, and wherein segmenting includes segmenting the route into plural substantially equal segments.

5. The method of claim 1 wherein the one or more criteria include a function and a segment is a length equal to the function applied to a respective route.

6. The method of claim 1 wherein segmenting the route further comprises locating one or more intermediary points along the route in accordance with the criteria, each intermediary point representing an end of one segment and a beginning of a new segment, and wherein determining one or more entities that are in proximity to each segment further includes for each intermediary point, determining one or more entities in an area around a given intermediary point.

7. The method of claim 6 wherein determining one or more entities in an area includes determining one or more entities in a radius around the intermediary point.

8. The method of claim 6 wherein determining the entities in an area includes performing a geographical search around starting and end points for each segment.

9. The method of claim 1 wherein aggregating and ranking the attributes along all the determined routes and determining one or more emerging attributes further includes accumulating the attributes, evaluating the accumulated attributes to determine top attributes for entities along the determined routes, and identifying the emerging attributes from the determined top attributes.

10. The method of claim 1 further comprising identifying regions along the determined routes based on the emerging attributes.

11. The method of claim 1 wherein the area is a bounding area within which attribute oriented routes are selected.

12. The method of claim 1 wherein the one or more goals define a set of optimization goals, and wherein the method further comprises receiving the set of optimization goals from the user or deriving the set of optimization goals from a profile associated with the user.

13. The method of claim 1 further comprising optimizing routes in, or eliminating routes from, the one or more attributed oriented routes based on the constraints provided by the user.

14. The method of claim 13 wherein the constraints include a total maximum travel time between the starting point and destination point.

15. The method of claim 1 wherein determining one or more attribute oriented routes further includes searching the attribute oriented routes for one that passes through regions with highest aggregate scores for a set of selected attributes of the emerging attributes.

16. The method of claim 1 wherein the theme is based on a set of emerging attributes.

17. A computer program product embodied in a non-transitive computer-readable medium including instructions that when executed cause one or more processors to:

identify a starting point and a destination point for travel by a user including any constraints of the user regarding the travel;

determine one or more initial routes between the starting point and the destination point;

for each initial route, segment the route into a plurality of segments based on one or more criteria; and

determine attribute oriented routes using the segments including;

determine one or more entities associated with each segment;

identify attributes for each determined entity;

aggregate and rank the attributes along all the determined initial routes and determine one or more emerging attributes, wherein aggregating and ranking the attributes along all the determined routes and determining one or more emerging attributes comprises accumulating the attributes, evaluating the accumulated attributes to determine top attributes for entities along the determined routes, and identifying the emerging attributes from the determined top attributes;

determine one or more attribute oriented routes based on the emerging attributes including identifying a theme for an attribute oriented route based on one or more of the emerging attributes, identifying a set of entities from the determined entities that are associated with the one or more emerging attributes, and creating the attribute oriented route that passes through a region that includes the set of entities; and

provide at least one attribute oriented route and information related to the theme to a device associated with the user.

18. The computer program product of claim 17 wherein identifying includes receiving the starting point, destination point and constraints, and wherein the constraints include limitations that affect a choice of the attribute oriented route.

19. A system, comprising:

one or more processors; and

one or more memory elements including instructions that, when executed, cause the one or more processors to;

identify a starting point and a destination point for travel by a user including any constraints of the user regarding the travel;

determine one or more initial routes between the starting point and the destination point;

for each initial route, segment the route into a plurality of segments based on one or more criteria, wherein segmenting the route comprises locating one or more intermediary points along the route in accordance with the criteria, each intermediary point representing an end of one segment and a beginning of a new segment; and

determine attribute oriented routes using the segments including;

determine one or more entities associated with each segment, wherein determining one or more entities associated with each segment comprises, for each intermediary point, determining one or more entities in an area around a given intermediary point;

identify attributes for each determined entity;

aggregate and rank the attributes along all the determined initial routes and determine one or more emerging attributes;

determine one or more attribute oriented routes based on the emerging attributes including identifying a theme for an attribute oriented route based on one or more of the emerging attributes, identifying a set of entities from the determined entities that are associated with the one or more emerging attributes, and creating the attribute oriented route that passes through a region that includes the set of entities; and

provide at least one attribute oriented route and information related to the theme to a device associated with the user.

20. The method of claim 19, wherein determining one or more entities in an area includes determining one or more entities in a radius around the intermediary point.

21. The method of claim 20, wherein determining the entities in an area includes performing a geographical search around starting and end points for each segment.

22. A computer-implemented method to provide attribute oriented routes and related theme information, comprising:

identifying, by one or more computing devices, a starting point and a destination point for travel by a user including any constraints of the user regarding the travel;

determining, by the one or more computing devices, one or more initial routes between the starting point and the destination point;

for each initial route, segmenting, by the one or more computing devices, the route into a plurality of segments; and

determining, by the one or more computing devices, attribute oriented routes using the segments including;

determining, by the one or more computing devices, one or more entities associated with each segment;

identifying, by the one or more computing devices, attributes for each determined entity;

aggregating and ranking, by the one or more computing devices, the attributes along all the determined initial routes and determining one or more emerging attributes;

determining, by the one or more computing devices, one or more attribute oriented routes based on the emerging attributes and including identifying a theme for an attribute oriented route based on one or more of the emerging attributes, identifying a set of entities from the determined entities that are associated with the one or more emerging attributes, and creating the attribute oriented route that passes through a region that includes the set of entities; and

providing, by the one or more computing devices, at least one attribute oriented route and information related to the theme to a device associated with the user.