Matching trip data to transportation network data

• US 8,645,402 B1
• Filed: 12/22/2009
• Issued: 02/04/2014
• Est. Priority Date: 12/22/2009
• Status: Active Grant

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: Teradata US, Inc. (Teradata Corporation)
• Inventors: Watzke, Michael W., Gerritson, Peter
• Primary Examiner(s): Badawi, Sherief
• Application Number:
  US12/644,240
• Time in Patent Office: 1,505 Days
• Field of Search: 707/713, 707/714, 707/814, 455/456.1
• US Class Current: 707/755
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 50/40 Business processes related to the transportation industry shipping G06Q10/083

Abstract

Trip data that includes points traversed during corresponding trips is received. Transportation network data that describes geographic locations and links between the geographic locations is received. The trip data and transportation network data are partitioned across a plurality of processing units executing on one or more processors. At each of the plurality of processing units, a subset of the trip data at the corresponding processing unit is locally matched to a subset of the transportation network data at the corresponding processing unit to identify a subset of paths of the transportation network data traversed by one or more of the trips.

Claims

1. A method comprising:

receiving trip data that includes points representative of geographic locations traversed during a plurality of corresponding independently-traversed separate trips;

storing the trip data in a storage device;

retrieving the stored trip data from the storage device;

determining a particular geographic space occupied by the trip data;

receiving transportation network data that describes geographic locations and links between the geographic locations of the transportation network data;

partitioning the stored trip data and transportation network data across a plurality of processing units executing on one or more processors, wherein the stored trip data is partitioned into subsets, wherein each subset of stored trip data is a respective one of the corresponding independently-traversed separate trips, and wherein the transportation network data is partitioned into subsets, and wherein each subset of transportation network data includes geographic space data containing a corresponding one of the independently-traversed separate trips from the stored trip data; and

organizing the stored trip data according to a predetermined function;

at each of the plurality of processing units executing on the one or more processors, locally matching a subset of the stored trip data to a corresponding subset of the transportation network data to identify a subset of paths of the transportation network data traversed by each subset of stored trip data.

2. The method of claim 1, further comprising:

combining the subsets of paths identified by the plurality of processing units to provide an output that identifies all paths traversed by the plurality of independently-traversed separate trips.

3. The method of claim 1, organizing the stored trip data according to the predetermined function comprises organizing the trip data according to a Hilbert space filling curve that defines a space filling curve in a particular geographic space, wherein the particular geographic space is divided into cells including corresponding different portions of the space filling curve, wherein each of the cells is identified by a corresponding Hilbert code.

4. The method of claim 3, wherein partitioning the trip data comprises range partitioning the trip data by the Hilbert codes.

5. The method of claim 4, further comprising organizing the transportation network data into an global Rtree having a hierarchical arrangement of tree nodes, wherein each of the tree nodes contains a range of Hilbert codes and a corresponding tree node identifier.

6. The method of claim 5, wherein partitioning the transportation network data across the plurality of processing units comprises partitioning the tree nodes of the Rtree.

7. The method of claim 6, wherein partitioning the transportation network data comprises range partitioning the Rtree according to a corresponding median value of Hilbert codes contained in each tree node.

8. The method of claim 6, wherein locally matching comprises:

at each of the processing units, searching the Rtree to identify the subset of the transportation network data to retrieve to locally match to the corresponding subset of the trip data at the processing unit.

9. The method of claim 1, wherein local matching is performed by each of the plurality of processing units that are part of a database management system, wherein the processing units are configured to manage access of one or more relational tables in the database management system.

10. An article comprising at least one non-transitory storage medium storing instructions that upon execution by at least one processor causes the at least one processor to:

receive trip data that includes points representative of geographic locations traversed during a plurality of corresponding independently-traversed separate trips;

store the trip data in a storage device;

retrieve the stored trip data from the storage device;

determine a particular geographic space occupied by the trip data;

identify transportation network data that describes geographic locations and links between the geographic locations of the transportation network data;

provide an index representing transportation network data, wherein the transportation network data comprises geographic space data;

partition the stored trip data and the index across a plurality of processing units, wherein each stored trip data partition includes stored trip data for at least one independently-traversed separate trip, and wherein each index partition is associated with a subset of transportation network data corresponding to at least one of the independently-traversed separate trips;

organize the stored trip data according to a predetermined function; and

use, at each of the plurality of processing units, the index to identify a corresponding subset of the transportation network data to locally match to the stored trip data to identify a subset of paths of the transportation network data traversed by each subset of stored trip data.

11. The article of claim 10, wherein, upon execution of the instructions, the processor is further caused to:

provide an index having plural levels of tree nodes; and

partition the index through identification of subsets of the tree nodes and assignment of the subsets to respective ones of the processing units.

12. The article of claim 11, wherein the tree nodes include leaf nodes that are assigned respective ranges of Hilbert codes, and wherein organization of the stored trip data comprises assignment of Hilbert codes to trip data objects containing respective subsets of trip data.

13. The article of claim 12, wherein organization of the stored trip data is performed in accordance to a Hilbert space filling curve that defines a space filling curve in a particular geographic space, wherein the particular geographic space is divided into cells including corresponding different portions of the space filling curve, wherein each of the cells is identified by a corresponding Hilbert code.

14. The article of claim 13, wherein, upon execution of the instructions, the processor is further caused to partition the stored trip data according to the Hilbert codes and numbers of vertexes of each trip data object, where each vertex represents a geographic point.

15. The article of claim 14, wherein, upon execution of the instructions, the processor is further caused to partition the trip data objects into plural partitions, wherein at least a particular one of the plural partitions includes multiple ones of the trip data objects, wherein the multiple trip data objects in the particular partition are sorted by corresponding Hilbert codes.

16. The article of claim 15, wherein, upon execution of the instructions, the processor is further caused to sequentially locally match the multiple trip data objects to the transportation network data in order.

17. The article of claim 14, wherein, upon execution of the instructions, the processor is further caused to partition the index according to Hilbert codes.

18. A database management system comprising:

a storage subsystem having a plurality of storage modules;

a memory;

one or more processors;

a plurality of processing units executable on the one or more processors to access data in the respective storage modules, wherein each of the plurality of processing units is executable to further;

retrieve trip data that represents a plurality of independently-traversed separate trips from one or more of the storage modules into the memory, wherein the trip data is partitioned into plural partitions, wherein each plural partition corresponds to one of the independently-traversed separate trips;

retrieve a plurality of subsets of transportation network data associated with the first partition into the memory, wherein each subset of transportation network data is associated with one of the includes geographic space data that corresponds to one of the independently-traversed separate trips; and

organize the trip data according to a predetermined function

locally match the trip data representing each of the independently-traversed separate trips to the associated subset of transportation network data to identify paths from the transportation network data traversed by each of the independently-traversed separate trips.

19. The database management system of claim 18, wherein the transportation network data is represented by an index partitioned into the plural partitions.