Storing trajectory

• US 10,077,986 B2
• Filed: 07/12/2017
• Issued: 09/18/2018
• Est. Priority Date: 09/29/2014
• Status: Active Grant

• Current Assignee: AirBNB Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Duan, Ning, Ji, Peng, Wang, Zhi Hu, Zhu, Jun
• Primary Examiner(s): El Chanti, Hussein A
• Application Number:
  US15/647,706
• Publication Number:
  US 20170307384A1
• Time in Patent Office: 433 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 road segments comprising at least a first road segment and a last road segment different from the first road segment that is traversed last among the 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 a first road segment of the road segments and the entry point of the first road segment;

for each road segment, identifying, by the processor, an exit point from among the trajectory points;

identifying, by the processor, a single exit time of only the last road segment of the road segments using the arrival times;

calculating, by the processor, a single exit distance between a known point along the last road segment and the exit point of the last road segment; and

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

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

2. The method of claim 1, wherein the entity is a vehicle or a mobile device.

3. The method of claim 1, wherein the navigation device is a global positioning system (GPS) receiver.

4. 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 single exit time is a time instant when the entity ends the travelling.

5. 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.

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

analyzing a road characteristic associated with the corresponding road segment;

or analyzing a behavior characteristic of the entity when traveling along the corresponding road segment.

7. The method according to claim 5, 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.

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

an arrival time instant of the entity;

or speed of the entity.

9. 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 road segments comprising at least a first road segment and a last road segment different from the first road segment that is traversed last among the 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 a first road segment of the road segments and the entry point of the first road segment;

for each road segment, identify, an exit point from among the trajectory points;

identify a single exit time of only the last road segment of the road segments using the arrival times;

calculate a single exit distance between a known point along the last road segment and the exit point of the last road segment; and

generate a compressed version of the trajectory data that comprises the entry times, the entry distance, the single exit time, and the single exit distance; 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.

10. The computer system of claim 9, wherein the entity is a vehicle or a mobile device.

11. The computer system of claim 9, wherein the navigation device is a global positioning system (GPS) receiver.

12. The computer system of claim 9, 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 single exit time is a time instant when the entity ends the travelling.

13. The computer system of claim 9, wherein the processor, for each road segment, identifies a point of interest on the corresponding road segment;

obtains data related to the point of interest; and

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

14. The computer system of claim 13, wherein the processor identifies the point of interest on the road segment by analyzing a road characteristic associated with the corresponding road segment;

or analyzing a behavior characteristic of the entity when traveling along the corresponding road segment.

15. The computer system of claim 13, 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.

16. The computer system of claim 13, wherein the data includes at least one of:

an arrival time instant of the entity;

or speed of the entity.