Hybrid road network and grid based spatial-temporal indexing under missing road links
First Claim
Patent Images
1. A computer-implemented method for indexing map data, the method comprising:
- from a set of trajectory points received from a global positioning system (GPS), 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;
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 and a grid;
receiving, by one or more processors, a query, wherein the query comprises an area of the map;
responsive to determining that a received trajectory point from the set of received trajectory points is associated with a road link of the map, using the road link for a spatial cell;
responsive to determining that a received trajectory point from the set of received trajectory points is not associated with a road link of the map, using the grid for the spatial cell; and
displaying, by one or more processors, output data associated with the built hybrid index.
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
17 Claims
-
1. A computer-implemented method for indexing map data, the method comprising:
-
from a set of trajectory points received from a global positioning system (GPS), 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; 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 and a grid; receiving, by one or more processors, a query, wherein the query comprises an area of the map; responsive to determining that a received trajectory point from the set of received trajectory points is associated with a road link of the map, using the road link for a spatial cell; responsive to determining that a received trajectory point from the set of received trajectory points is not associated with a road link of the map, using the grid for the spatial cell; and displaying, by one or more processors, output data associated with the built hybrid index. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A computer program product comprising:
-
a computer readable storage medium and program instructions stored on the computer readable storage medium, the program instructions comprising; program instructions to, from a set of trajectory points received from a global positioning system (GPS), determine whether each received trajectory point from the set of received trajectory points is associated with a road link of a map; 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 and a grid; program instructions to receive a query, wherein the query comprises an area of the map; program instructions to, responsive to determining that a received trajectory point from the set of received trajectory points is associated with a road link of the map, use the road link for a spatial cell; program instructions to, responsive to determining that a received trajectory point from the set of received trajectory points is not associated with a road link of the map, use the grid for the spatial cell; and program instructions to display output data associated with the built hybrid index. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
13. A computer system comprising:
-
one or more computer processors; one or more computer readable storage media; program instructions stored on the one or more computer readable storage media for execution by at least one of the one or more processors, the program instructions comprising; program instructions to, from a set of trajectory points received from a global positioning system (GPS), determine whether each received trajectory point from the set of received trajectory points is associated with a road link of a map; 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 and a grid; program instructions to receive a query, wherein the query comprises an area of the map program instructions to, responsive to determining that a received trajectory point from the set of received trajectory points is associated with a road link of the map, use the road link for a spatial cell; program instructions to, responsive to determining that a received trajectory point from the set of received trajectory points is not associated with a road link of the map, use the grid for the spatial cell; and program instructions to display output data associated with the built hybrid index. - View Dependent Claims (14, 15, 16, 17)
-
Specification