Simple Distances for Trajectories via Landmarks
This provides a simple and interpretable solution for data analysis tasks involving trajectories and other geometric objects, with broad applications in fields like robotics or GIS, though it is incremental in improving existing distance metrics.
The paper tackles the problem of measuring distances between geometric objects like trajectories, lines, and hyperplanes by introducing a new class of distances based on landmarks, which map objects to Euclidean space for easy computation and interpretability. The result shows that for trajectories, these distances match or outperform state-of-the-art metrics, enabling efficient k-means clustering and nearest neighbor search with orders of magnitude improvement in speed.
We develop a new class of distances for objects including lines, hyperplanes, and trajectories, based on the distance to a set of landmarks. These distances easily and interpretably map objects to a Euclidean space, are simple to compute, and perform well in data analysis tasks. For trajectories, they match and in some cases significantly out-perform all state-of-the-art other metrics, can effortlessly be used in k-means clustering, and directly plugged into approximate nearest neighbor approaches which immediately out-perform the best recent advances in trajectory similarity search by several orders of magnitude. These distances do not require a geometry distorting dual (common in the line or halfspace case) or complicated alignment (common in trajectory case). We show reasonable and often simple conditions under which these distances are metrics.