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

• US 9,551,583 B1
• Filed: 07/06/2015
• Issued: 01/24/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: Ji, Peng, Duan, Ning, Gao, Peng, Li, Xiao Bo, Wang, Zhi Hu, Zhu, Jun
• Primary Examiner(s): Tarcza, Thomas
• Assistant Examiner(s): Dunn, Alex C
• Application Number:
  US14/791,576
• Publication Number:
  US 20170010101A1
• Time in Patent Office: 568 Days
• 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 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.

2. The method of claim 1, further comprising:

responsive to receiving the query, identifying the spatial cells which intersect with the area of the map.

3. The method of claim 1, further comprising:

combining, by one or more processors, more than one road link to form a bundled road link.

4. The method of claim 1, further comprising:

combining, by one or more processors, at least one grid, to form a bundled grid.

5. The method of claim 3, further comprising:

updating, by one or more processors, the bundled road link, based, at least in part, on a road link feature and a trajectory feature, wherein the trajectory feature comprises;

a trajectory pattern and a trajectory density.

6. The method of claim 2, further comprising:

calculating, by one or more processors, a spatial cell comprising a road link, using linear computations; and

calculating, by one or more processors, a spatial cell comprising at least one grid, using spatial computations.

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.

8. The computer program product of claim 7, further comprising:

program instructions to, responsive to receiving the query, identify the spatial cells which intersect with the area of the map.

9. The computer program product of claim 7, further comprising:

program instructions to combine more than one road link to form a bundled road link.

10. The computer program product of claim 7, further comprising:

program instructions to combine at least one grid, to form a bundled grid.

11. The computer program product of claim 9, further comprising:

program instructions to update the bundled road link, based, at least in part, on a road link feature and a trajectory feature, wherein the trajectory feature comprises;

a trajectory pattern and a trajectory density.

12. The computer program product of claim 8, further comprising:

program instructions to calculate a spatial cell comprising a road link, using linear computations; and

program instructions to calculate a spatial cell comprising at least one grid, using spatial computations.

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.

14. The computer system of claim 13, further comprising:

program instructions to, responsive to receiving the query, identify the spatial cells which intersect with the area of the map.

15. The computer system of claim 13, further comprising:

program instructions to combine more than one road link to form a bundled road link.

16. The computer system of claim 13, further comprising:

program instructions to combine at least one grid, to form a bundled grid.

17. The computer system of claim 15, further comprising:

program instructions to update the bundled road link, based, at least in part, on a road link feature and a trajectory feature, wherein the trajectory feature comprises;

a trajectory pattern and a trajectory density.