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

• US 9,546,872 B1
• Filed: 02/29/2016
• Issued: 01/17/2017
• 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): HUANG, MIRANDA M
• Application Number:
  US15/055,681
• Publication Number:
  US 20170010102A1
• Time in Patent Office: 323 Days
• Field of Search: None
• US Class Current: 1/1
• 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 method for indexing map data, the method comprising:

from a set of received trajectory points, determining, by one or more computer processors, 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;

building, by one or more processors, 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;

creating one or more bundled spatial cell by combining, by one or more processors, 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;

forming a trajectory segment with identification based on the one or more bundled spatial cells;

responsive to building the hybrid index, inputting, by one or more processors, 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;

receiving, by one or more processors, a query for an area of the map, based on the bundled spatial cell, comprising;

identifying, by one or more processors, each area represented by the bundled spatial cells which intersects with an area of the map represented by the query;

scanning, by one or more processors, the area represented by the bundled spatial cells which intersects with the area of the map represented by the query;

determining, by one or more processors, whether the intersecting bundled spatial cells are grid cells; and

in response to determining that the intersecting bundled spatial cells are grid cells, executing, by one or more processors, a set of spatial related computations, wherein the set of spatial related computations comprise;

determining, by a spatial computing engine, an intersection between the grid cells, using data associated with the received set of trajectory points;

returning, by one or more processors, results from the set of spatial related computations, based on the received query; and

updating, by one or more processors, during runtime, the bundled spatial cell, based, at least in part, on a trajectory pattern and the trajectory density.