Skip to Main content Skip to Navigation
Journal articles

Products of Euclidean Metrics, Applied to Proximity Problems among Curves

Ioannis Z. Emiris 1, 2 Ioannis Psarros 1, 2
2 AROMATH - AlgebRe, geOmetrie, Modelisation et AlgoriTHmes
CRISAM - Inria Sophia Antipolis - Méditerranée , NKUA - National and Kapodistrian University of Athens
Abstract : Approximate Nearest Neighbor (ANN) search is a fundamental computational problem that has benefited from significant progress in the past couple of decades. However, most work has been devoted to pointsets, whereas complex shapes have not been sufficiently addressed. Here, we focus on distance functions between discretized curves in Euclidean space: They appear in a wide range of applications, from road segments and molecular backbones to time-series in general dimension. For ℓp-products of Euclidean metrics, for any constant p, we propose simple and efficient data structures for ANN based on randomized projections: These data structures are of independent interest. Furthermore, they serve to solve proximity questions under a notion of distance between discretized curves, which generalizes both discrete Fréchet and Dynamic Time Warping distance functions. These are two very popular and practical approaches to comparing such curves. We offer, for both approaches, the first data structures and query algorithms for ANN with arbitrarily good approximation factor, at the expense of increasing space usage and preprocessing time over existing methods. Query time complexity is comparable or significantly improved by our methods; our algorithm is especially efficient when the length of the curves is bounded. Finally, we focus on discrete Fréchet distance when the ambient space is high dimensional and derive complexity bounds in terms of doubling dimension as well as an improved approximate near neighbor search.
Document type :
Journal articles
Complete list of metadatas
Contributor : Ioannis Emiris <>
Submitted on : Wednesday, December 16, 2020 - 4:26:16 PM
Last modification on : Wednesday, December 16, 2020 - 7:54:13 PM


Files produced by the author(s)




Ioannis Z. Emiris, Ioannis Psarros. Products of Euclidean Metrics, Applied to Proximity Problems among Curves. ACM Transactions on Spatial Algorithms and Systems, ACM, 2020, 6 (4), pp.1-20. ⟨10.1145/3397518⟩. ⟨hal-03045134⟩



Record views


Files downloads