Method and apparatus for filtering device location points in a sampled trajectory while maintaining path reconstructability

Patent metadata

Field	Value
Publication number	US-2018224293-A1
Application number	US-201715425531-A
Country	US
Kind code	A1
Filing date	Feb 6, 2017
Priority date	Feb 6, 2017
Publication date	Aug 9, 2018
Grant date	—

Abstract

An approach is provided for filtering device location points in a sampled trajectory while maintaining path reconstructability. The approach involves determining a first location point in the sampled trajectory that is an unfiltered location point. The sampled trajectory includes device location points sampled by a device traversing a road network. The approach also involves determining a fastest alternative path from the first location point to a second location point. The approach further involves calculating a sampling time difference between a time at which the first location point was sampled and another time at which the second location point was sampled. The approach further involves designating the second location point as a next unfiltered location point when the sampling time difference is within a threshold value of a free-flow travel time calculated for the fastest alternative path. Otherwise, the second location point is designated as a filtered location point.

First claim

What is claimed is:

1 . A method for filtering device location points in a sampled trajectory while maintaining path reconstructability comprising:
determining a first location point in the sampled trajectory that is an unfiltered location point, wherein the sampled trajectory includes a plurality of device location points sampled by one or more sensors of a device traversing a road network; determining a fastest alternative path from the first location point to a second location point that follows the first location point in the sampled trajectory; calculating a sampling time difference between a time at which the first location point was sampled and another time at which the second location point was sampled; designating the second location point as a next unfiltered location point when the sampling time difference is within a threshold value of a free-flow travel time calculated for the fastest alternative path; and designating the second location point as a filtered location point when the sampling time difference is not within a threshold criterion of a free-flow travel time calculated for the fastest alternative path.

2 . The method of claim 1 , further comprising:
transmitting the second location point as a location update when the second point is designated as the next unfiltered location point.

3 . The method of claim 1 , further comprising:
adding the second location point to a compressed version of the sampled trajectory when the second point is designated as the next unfiltered location point.

4 . The method of claim 1 , further comprising:
processing each subsequent location point in the travel trajectory to designate said each subsequent location point as either unfiltered or filtered based on a respective fastest alternative path and a respective sampling time difference with respect to said each subsequent location point and an immediate previous unfiltered location point.

5 . The method of claim 1 , further comprising:
determining that the second location point is within a threshold distance of an intersection point in the road network; determining another fastest alternative path from the first location point to the intersection point; and designating the second location point as the next unfiltered location point when the sampling time difference and the another free-flow travel time calculated for the another fastest alternative path differ by less than a calculated time for the device to traverse the threshold distance to the intersection point.

6 . The method of claim 1 , wherein the threshold value for the sampling time difference is based on a location sampling frequency that is used by the device to create the sampled trajectory.

7 . The method of claim 6 , wherein the location sampling frequency is greater than a frequency at which the device transmits location updates, a frequency at which a location point is selected to be included in a compressed version of the sampled trajectory, or a combination thereof.

8 . An apparatus for filtering device location points in a sampled trajectory while maintaining path reconstructability comprising:
at least one processor; and at least one memory including computer program code for one or more programs, the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to perform at least the following,
determine a first location point in the sampled trajectory that is an unfiltered location point, wherein the sampled trajectory includes a plurality of device location points sampled by one or more sensors of a device traversing a road network;
calculate a sampling time difference between a time at which the first location point was sampled and another time at which a second location point was sampled, wherein the second location point follows the first location point in the sample trajectory;
when the second location point is not within a threshold distance of an intersection point of the road network, designate the second location point as a next unfiltered location point when the sampling time difference is within a threshold value of a free-flow travel time calculated for a fastest alternative path between the first location point and the second location point; and
when the second location point is within a threshold distance of the intersection point, designate the second location point as the next unfiltered location point when the sampling time difference and another free-flow travel time calculated for another fastest alternative path between the first location point and the intersection point differ by less than a calculated time for the device to traverse the threshold distance to the intersection point.

9 . The apparatus of claim 8 , wherein the apparatus is further caused to:
initiate a transmission of the second location point as a location update, an addition of the second location point to a compressed version of the sampled trajectory, or a combination thereof when the second point is designated as the next unfiltered location point.

10 . The apparatus of claim 8 , wherein the apparatus is further caused to:
designate the second location point as a filtered location point either when the sampling time difference is not within a threshold value of the free-flow travel time, or when the sampling time difference and the another free-flow travel time do not differ by less than the calculated time for the device to traverse the threshold distance to the intersection point.

11 . The apparatus of claim 8 , wherein the apparatus is further caused to:
process each subsequent location point in the travel trajectory to designate said each subsequent location point as either unfiltered or filtered based on a respective fastest alternative path and a respective sampling time difference with respect to said each subsequent location point and an immediate previous unfiltered location point.

12 . A non-transitory computer-readable storage medium for filtering device location points in a sampled trajectory while maintaining path reconstructability, carrying one or more sequences of one or more instructions which, when executed by one or more processors, cause an apparatus to at least perform the following steps:
mapping a fastest alternative route from a first location point in the sampled trajectory to a second location point in the sampled trajectory to one or more links of a geographic database representing a road network, wherein the sampled trajectory includes a plurality of device location points sampled by one or more sensors of a device traversing the road network, and wherein the first location point is an unfiltered location point; designating one or more complete links among the one or more links as a trunk portion, wherein each of the one or more complete links include a respective tail node and a head node that lies within the fastest alternative route; calculating a sampling time difference between a time at which the first location point was sampled and another time at which the second location point was sampled; designating the second location point as a next unfiltered location point when the sampling time difference is within a threshold value of a free-flow travel time calculated for traversing the one or more links; and initiating a re-determination the trunk portion when the second location point is designated as the next unfiltered location point.

13 . The non-transitory computer-readable storage medium of claim 12 , wherein the re-determination of the trunk portion is further initiated when the second location point indicates that the device has reached a subsequ

Assignees

• Here Global Bv

Inventors

• Xu Bo
• Mas-Ud Hussain Muhammed

Classifications

• G01C21/30

  Map- or contour-matching · CPC title

• G01C21/3446 Primary

  Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F17/30958

  Physics · mapped topic

• G06F17/30241

  Physics · mapped topic