Location data is often generated as a sequence of points in time reflecting a geographical position at a moment in time. These coordinates reflect someone’s continuous location history with a set of discrete points which make calculations on underlying trajectories costly and conceptually difficult. If the data can be reduced in size without sacrificing information, it is possible to simultaneously reduce both the computational complexity as well as the number of assumptions that must be made about individual locations. One method of data reduction is by partitioning trajectories into straight line segments that sufficiently represent the path. These line segments can then be used for calculations on properties of the underlying trajectory such as speed or distance. They can additionally be more easily compared against other trajectories consisting of line segments in order to identify similar paths and come with the added benefit of reducing measurement error common to GPS navigational systems.

The algorithm is iterative and if allowed to run indefinitely will create N - 1 segments for N points. In order to be useful, it must be given a stopping criteria such as the number of segments or the maximum error distance between the recorded points and the adjusted points that lie along the line segment. The smaller the error, the more information is preserved, but at the expense of the data reduction being sought. It is therefore important to choose stopping criteria such that we find a balance between the two opposing aims.

Methods of segmentation vary, but most follow along with the well-known Douglas-Peucker algorithm’s method of creating new segments based on the magnitude of discrepancy between the proposed segment and the point that it should represent. This simulation study implements the Top-Down Time Ratio algorithm outlined in Han (2011). A segment is generated between the first location in a trajectory and the last location in the trajectory. Each recorded location point between the two segment ends is given a proposed new point along the generated segment, with respect to the elapsed time. The distance is calculated between the recorded point and this pseudo-sampled point. The point lying furthest from its segment is selected to form a new segment end, whereupon the process begins again.

Results from the simulation study in terms of total distance demonstrate that as expected, as the maximum allowed error increases, the total distance decreases. The overall change is modest in most cases and extreme in very few. Despite the wide range of error conditions, total distance as a whole remains largely stable even when accepting points that deviate by 200 meters. Total distance as a metric can give us a way to estimate the distance lost as we generate segments, but it is not in itself particularly informative.

Below are two examples of data sets in which even the 10m error condition misses a large percentage of the total distance. The segments drawn appear to be relatively faithful to the underlying path with only minor deviations (and in fact we see that the mean error is very low – around 2 meters). The recorded points are high-density over the time period which in the absence of error, would give us a very good estimation of total distance traveled. However, in this case, the high density of points coupled with a small amount of measurement error leads us to an overestimate of the distance traveled. The total distance of the continuous path is likely to fall somewhere between the 10 meter error and 0 meter error measurements.

segcomp

worstoff