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

Patent metadata

Field	Value
Publication number	US-9234765-B1
Application number	US-201414283417-A
Country	US
Kind code	B1
Filing date	May 21, 2014
Priority date	Jun 5, 2013
Publication date	Jan 12, 2016
Grant date	Jan 12, 2016

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.

First claim

What is claimed is:

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 enti

Assignees

• Google Inc

Inventors

• Padovitz Amir
• Java Akshay N

Classifications

• G01C21/20 Primary

  Instruments for performing navigational calculations (G01C21/24, G01C21/26 take precedence) · CPC title

• G01C21/3617 Primary

  using user history, behaviour, conditions or preferences, e.g. predicted or inferred from previous use or current movement · CPC title

• G09B29/10

  Map spot or coordinate position indicators; Map reading aids (optical projection apparatus per se G03B) · CPC title

• G01C21/32

  Structuring or formatting of map data · CPC title

• G09B29/003

  Maps · CPC title