Hybrid road network and grid based spatial-temporal indexing under missing road links
First Claim
Patent Images
1. A computer program product for indexing map data, the computer program product comprising:
- one or more non-transitory computer readable storage media and program instructions stored on the one or more non-transitory computer readable storage media, 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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
1 Claim
-
1. A computer program product for indexing map data, the computer program product comprising:
one or more non-transitory computer readable storage media and program instructions stored on the one or more non-transitory computer readable storage media, 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.
Specification