Mining trajectory for spatial temporal analytics

• US 9,256,689 B2
• Filed: 08/09/2013
• Issued: 02/09/2016
• Est. Priority Date: 12/07/2012
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: He, Qing, Liu, Xuan, Xing, Songhua, Hampapur, Arun
• Primary Examiner(s): GEBRESENBET, DINKU W
• Application Number:
  US13/963,489
• Publication Number:
  US 20140164390A1
• Time in Patent Office: 914 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries

Abstract

A method is provided to generate a heat map to show traffic congestion based on transit points. The method includes generating, by a processing device, a trajectory database from time-stamped global positioning system (GPS) sample points, and computing transit points for each trajectory in the trajectory database. The method further includes constructing a temporal transit graph. The transit graph captures the shortest paths among the transit points. The method further includes indexing and storing the transit graph in a spatial-temporal database for online analytic processing.

Claims

1. A computer system, comprising:

a memory having computer readable computer instructions; and

a processor configured to execute the computer readable instructions to perform a method comprising;

generating a trajectory database from time-stamped global positioning system (GPS) sample points;

computing transit points for each trajectory in the trajectory database, each transit point computed from a respective time-stamped GPS sample point;

grouping the transit points into individual transit clusters, and constructing a temporal transit graph based on the transit clusters to define an aggregated trajectory of traffic patterns, the transit graph capturing the shortest paths among the transit points;

determining a common route of at least two vehicles whose GPS sampling intervals are different based on performing a trajectory alignment of the transit points with respect to a road network;

in response to determining that two consecutive GPS points do not locate on the same or adjacent road segments, connecting the consecutive GPS points by the shortest path and performing a temporal interpolation to generate modified time stamps corresponding to the connected GPS points; and

indexing and storing the transit graph in a spatial-temporal database online analytic processing, the online analytic processing comprising receiving spatial-temporal queries on the transit graph via a user interface,

wherein the GPS sample points that are collected from GPS logs of a plurality of vehicles in a street network table to define traffic patterns.

2. The computer system of claim 1, wherein the transit points divide each trajectory into a number of sub-trajectories, each sub-trajectory being an exact shortest path between each transit point.

3. The computer system of claim 1, wherein the generating of the trajectory database further comprises:

removing corrupted GPS sample points to determine qualified GPS sample points indicating the transit points; and

aligning the qualified GPS sample points to the road network.

4. The computer system of claim 1, wherein the computing of the transit points further comprises:

analyzing the distribution of transit points on the trajectory graph; and

clustering transit points located in similar network locations of the trajectory graph, whereby the centroids of transit point clusters form a node for the transit graph.

5. The computer system of claim 4, wherein the constructing of the temporal transit graph further comprises:

computing a connectivity among all point transit clusters; and

color coding the transit graph based on a number of routes passed on each transit edge of the transit graph.

6. The computer system of claim 1, wherein the temporal transit graph is constructed offline and the online analytics processing occurs online.