Compressing trajectory data of a navigation device

• US 9,739,620 B2
• Filed: 09/29/2015
• Issued: 08/22/2017
• Est. Priority Date: 09/29/2014
• Status: Active Grant

• Current Assignee: AirBNB Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Duan, Ning, Wang, Zhi Hu, Ji, Peng, Zhu, Jun
• Primary Examiner(s): EL CHANTI, HUSSEIN A
• Application Number:
  US14/868,921
• Publication Number:
  US 20160093208A1
• Time in Patent Office: 693 Days
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G08G 1/052 with provision for determining speed or overspeed speed measuring in general G01P

Abstract

An embodiment of the present invention provides a method for storing trajectory. The method includes: mapping, based on a plurality of positions on a trajectory of an entity, the trajectory to at least one road segment in a road network; identifying an entry point and an exit point of one of the road segments, wherein the entry point is a point where the entity starts traveling along the road segment, and the exit point is a point where the entity ends traveling along the road segment; and storing data related to at least one of the entry point and the exit point, to store the road segment as a part of information of the trajectory.

Claims

1. A method of compressing trajectory data comprising a plurality of trajectory points and corresponding arrival times, the trajectory data corresponding to a plurality of road segments, the method comprising:

for each road segment,

identifying, by a processor of a computer, an entry point from among the trajectory points and an entry time among the arrival times;

calculating, by the processor, an entry distance between a known point along the corresponding road segment and the entry point;

identifying, by the processor, an exit point from among the trajectory points and an exit time among the arrival times; and

calculating, by the processor, an exit distance between the known point and the exit point; and

storing, by the processor, a compressed version of the trajectory data on a computer that comprises the entry times, the entry distances, the exit times, and the exit distances,

wherein the trajectory data is received from a navigation device and corresponds to movements of an entity.

2. The method according to claim 1, wherein for each road segment further comprising:

identifying a point of interest on the corresponding road segment;

obtaining data related to the point of interest; and

storing the data in the compressed version of the trajectory data.

3. The method according to claim 2, wherein identifying a point of interest on the road segment includes at least one of:

identifying the point of interest by analyzing a road characteristic associated with the corresponding road segment;

or

identifying the point of interest by analyzing a behavior characteristic of the entity when traveling along the corresponding road segment.

4. The method according to claim 2, wherein the point of interest includes at least one of a turn point, an intersection point, a critical point, a point with a predetermined traffic condition, or a point where the entity performs a predetermined behavior.

5. The method according to claim 2, wherein the data includes at least one of:

an arrival time instant of the entity;

or speed of the entity.

6. The method according to claim 1, wherein the entry point is a point where the entity starts traveling along the corresponding road segment, the entry time is a time instant when the entity starts the travelling, the exit point is a point where the entity ends the travelling, and the exit time is a time instant when the entity ends the travelling.

7. A computer system for compressing trajectory data comprising a plurality of trajectory points and corresponding arrival times, the trajectory data corresponding to a plurality of road segments, the system comprising:

a processor configured to, for each road segment, identify an entry point from among the trajectory points and an entry time among the arrival times;

calculate an entry distance between a known point along the corresponding road segment and the entry point;

identify an exit point from among the trajectory points and an exit time among the arrival times;

calculate an exit distance between the known point and the exit point; and

generate a compressed version of the trajectory data that comprises the entry times, the entry distances, the exit times, and the exit distances; and

a storage device configured to store the compressed version of the trajectory data,

wherein the trajectory data is received from a navigation device and corresponds to movements of an entity.

8. The system according to claim 7, wherein for each road segment the processor is configured to identify a point of interest on the corresponding road segment, obtain data related to the point of interest, and store the data in the compressed version of the trajectory data.

9. The system according to claim 8, wherein the processor is configured to analyze a road characteristic associated with the corresponding road segment to identify the point of interest or to analyze a behavior characteristic of the entity when traveling along the corresponding road segment to identify the point of interest.

10. The system according to claim 8, wherein the point of interest includes at least one of a turn point, an intersection point, a critical point, a point with a predetermined traffic condition, or a point where the entity performs a predetermined behavior.

11. The system according to claim 8, wherein the data include at least one of:

an arrival time instant of the entity;

or speed of the entity.

12. The system according to claim 7, wherein the entry point is a point where the entity starts traveling along the corresponding road segment, the entry time is a time instant when the entity starts the travelling, the exit point is a point where the entity ends the travelling, and the exit time is a time instant when the entity ends the travelling.