MINING TRAJECTORY FOR SPATIAL TEMPORAL ANALYTICS

• US 20140164390A1
• Filed: 08/09/2013
• Published: 06/12/2014
• Est. Priority Date: 12/07/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hampapur, Arun, He, Qing, Liu, Xuan, Xing, Songhua
• Granted Patent: US 9,256,689 B2
• Time in Patent Office: Days
• US Class Current: 707/743
• 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

Embodiments relate to generating a trajectory heat map at an aggregated level using computed transit points is provided. An aspect includes generating, by a processing device, a trajectory database from time-stamped global positioning system (GPS) sample points. According to exemplary embodiments, transit points are computed for each trajectory in the trajectory database. A temporal transit graph is constructed from the transit points. The transit graph of embodiments captures the shortest paths among these transit points. The transit graph is then indexed and stored 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;

constructing a temporal transit graph, the transit graph capturing the shortest paths among the transit points; and

indexing and storing the transit graph in a spatial-temporal database for online analytic processing.

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; and

aligning qualified GPS sample points to a 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 online analytic processing comprises receiving spatial-temporal queries on the transit graph via a user interface.

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