Routing with data version stitching

Patent metadata

Field	Value
Publication number	US-9435658-B2
Application number	US-201514714742-A
Country	US
Kind code	B2
Filing date	May 18, 2015
Priority date	May 21, 2014
Publication date	Sep 6, 2016
Grant date	Sep 6, 2016

Abstract

Systems and methods are provided for the determination of routes from, for instance, travel segment network data associated with different data versions. More particularly, a request can be received for a route from an origin to a destination. Graph data modeling a travel segment network for a geographic region associated with the origin and for a geographic region associated the destination can be accessed. The graph data can preserve boundary nodes for visiting during a search (e.g. a contraction hierarchies style search) for a shortest path through the graph data. The reach value of a boundary segment can be considered in identifying boundary segments to be visited during the shortest path search through the graph data. The route can be determined based at least in part on the shortest path.

First claim

What is claimed is:

1. A computer-implemented method of determining routes in geographic areas, comprising
obtaining, by one or more computing devices, data indicative of a request for a route from an origin to a destination, wherein the one or more computing devices comprise one or more processors;
accessing, by the one or more computing devices, first graph data modeling a travel segment network for a first geographic region;
accessing, by the one or more computing devices,…

Assignees

• Google Inc

Inventors

• Geisberger Robert
• Eigenwillig Arno

Classifications

• G06Q10/047

  Physics · mapped topic

• G01C21/3446 Primary

  Physics · mapped topic

• G01C21/20

  Physics · mapped topic

• G06Q50/30

  Physics · mapped topic

• G06Q50/40

  Physics · mapped topic