With the increasing accumulation of spatial temporal path data, such as in the truck and cab datasets considered here, the need for effective path comparison algorithms is of current importance. This paper develops a measure employing an interval of comparison between such paths when addressing the possibly significant variations in the sampling process (differing sample rates, asynchronous sampling).

Central to this work is the estimated maximum path speed that constrains missing data points in the comparisons. The resulting convex optimization formulation for finding an interval of uncertainty between paths then leads to a more efficient approximate approach better suited to the long sequences and large databases encountered in practice. Concepts from the Ramer-Douglas-Peucker algorithm (for approximating a curve composed of line segments with a reduced number of line segments) are incorporated, with the algorithm presented inheriting its average (nlogn) and worst (n²) behaviors from this connection.

Theoretical foundations are clearly developed, along with good pseudocode details useful to software developers interested in implementations. Clearly described examples and matching figures clarify mathematical details. A strength that provides a good foundation for readers interested in applications is the use of a statistical methodology in the detailed study of sampling cases working with real datasets with hundreds of trajectory samples. Results, including comparisons with eight other methods reviewed in the paper, are neatly presented through a number of graphs and show the significant accuracy and efficiency advantages of the proposed method.