Hybrid road network and grid based spatial-temporal indexing under missing road links

• US 9,880,012 B2
• Filed: 11/18/2016
• Issued: 01/30/2018
• Est. Priority Date: 07/06/2015
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Duan, Ning, Gao, Peng, Ji, Peng, Li, Xiao Bo, Wang, Zhi Hu, Zhu, Jun
• Primary Examiner(s): Park, Grace
• Assistant Examiner(s): Le, Jessica N
• Application Number:
  US15/355,539
• Publication Number:
  US 20170067745A1
• Time in Patent Office: 438 Days
• Field of Search: 701450, 707743
• CPC Class Codes: G01C 21/3667 Display of a road map G01C21/3614 takes precedence; guidance using 3D or perspective road maps G01C21/3635
• CPC Class Codes: G01C 21/3874 Structures specially adapted for data searching and retrieval
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

Embodiments of the present invention provide efficient and dynamic systems and methods for building a hybrid road network and grid based spatial temporal index to handle big trajectory data. Embodiments of the present invention can be used to satisfy the issue of low indexing and compression rate of big trajectory data, and to improve the efficiency of index queries, while also providing a mechanism to account for missing road links in a map.

Claims

1. A computer system for indexing map data, the computer system comprising:

one or more computer processors;

one or more non-transitory computer readable storage media; and

program instructions stored on the one or more non-transitory computer readable storage media for execution by at least one of the one or more computer processors, the program instructions comprising;

from a set of received trajectory points, program instructions to determine whether each received trajectory point from the set of received trajectory points is associated with a road link of a map, wherein data associated with the set of received trajectory points comprises;

a moving object identification, a timestamp of a moving object, a longitude coordinate and a latitude coordinate of the data, a spatial cell identification, and a distance;

program instructions to build from the set of received trajectory points, a hybrid index, wherein the hybrid index comprises spatial cells, and wherein the spatial cells comprise a road link or a grid cell, wherein the grid cell represents a missing road link of the map;

program instructions to create one or more bundled spatial cell by combining at least one grid cell to form a bundled grid cell and more than one road links to form a bundled road link, wherein a size of the hybrid index data is less than a size of the set of received trajectory points, and wherein an equivalent trajectory density is represented in each bundled spatial cell;

program instructions to form a trajectory segment with identification based on the one or more bundled spatial cells;

program instructions to, responsive to building the hybrid index, input a set of information into a trajectory hybrid indexing module, wherein the set of information comprises;

moving object (MO) identification, a spatial cell identification, a start time, an end time, and a determined trajectory segment identification;

program instructions to receive a query for an area of the map based on the bundled spatial cell, comprising;

program instructions to identify each area represented by the bundled spatial cells which intersects with an area of the map represented by the query;

program instructions to scan the area represented by the bundled spatial cells which intersects with the area of the map represented by the query;

program instructions to determine whether the intersecting bundled spatial cells are grid cells; and

program instructions to, responsive to determining that the intersecting bundled spatial cells are grid cells, execute a set of spatial related computations, wherein the set of spatial related computations comprise;

program instructions to determine an intersection between the grid cells, using data associated with the received set of trajectory points;

program instructions to return results from the set of spatial related computations, based on the received query; and

program instructions to update, during runtime, the bundled spatial cell based, at least in part, on a trajectory pattern and the trajectory density.