Data formats and usage for massive point to point route calculation
US8000891B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | May 22, 2006 |
| Grant date | Aug 16, 2011 |
| Priority date | — |
| Expiry date | May 15, 2030 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06Q10/047
- WIPO fieldMeasurement
- WIPO sectorInstruments
Abstract
The invention is directed to a method by which optimal paths are found between one or more start destinations and one or more end destinations. First destination and travel data is converted into a node and edge data format, wherein the nodes represent start points and the edges have a weight related to a travel weight. These nodes and edges are subdivided into subsets. The paths between the start nodes and each of the end nodes are determined using the node and edge representations stored in the subsets. A selected union of subsets is determined that contains the start end destinations. The optimal paths are determined by using the travel values associated with the edges connecting the nodes. The union of subsets, which may comprise less than the full amount of subsets, is loaded for the path determination. Or, when the path determination perceives that a relevant boundary has been reached in a path determination, that next subset in the union of subsets is loaded. The newly loaded subset is “joined” to the already loaded subsets, thus allowing the completion of the path determination.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.