Approximating nearest neighbor distances

DOI10.1007/978-3-319-21840-3_17MaRDI QIDQ3449817zbMATH OpenOpenAlexWikidataFDO

Authors Michael B. Cohen, Brittany Terese Fasy, Amir Nayyeri, Donald R. Sheehy, Ameya Velingker, Gary L. Miller

Publication date 30 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.08048

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: Several researchers proposed using non-Euclidean metrics on point sets in Euclidean space for clustering noisy data. Almost always, a distance function is desired that recognizes the closeness of the points in the same cluster, even if the Euclidean cluster diameter is large. Therefore, it is preferred to assign smaller costs to the paths that stay close to the input points. In this paper, we consider the most natural metric with this property, which we call the nearest neighbor metric. Given a point set P and a path $gamma$, our metric charges each point of $gamma$ with its distance to P. The total charge along $gamma$ determines its nearest neighbor length, which is formally defined as the integral of the distance to the input points along the curve. We describe a $(3+varepsilon)$-approximation algorithm and a $(1+varepsilon)$-approximation algorithm to compute the nearest neighbor metric. Both approximation algorithms work in near-linear time. The former uses shortest paths on a sparse graph using only the input points. The latter uses a sparse sample of the ambient space, to find good approximate geodesic paths.

Recommendations

• scientific article; zbMATH DE number 1559576
• Approximate nearest neighbor queries revisited
• Nearest neighbor queries in metric spaces
• Net and prune: a linear time algorithm for Euclidean distance problems
• Approximate Nearest Neighbor Searching with Non-Euclidean and Weighted Distances

Cites work

• A fast algorithm for well-spaced points and approximate Delaunay graphs
• Approximating nearest neighbor distances
• Beating the spread, time-optimal point meshing
• Determining approximate shortest paths on weighted polyhedral surfaces
• Efficient algorithms for globally optimal trajectories
• Geometric approximation algorithms
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• Linear stability of planar solidification fronts
• Shortest path through random points
• The weighted region problem
• Topological inference via meshing

Cited in

(8)

• Estimation of errors between Euclidean and m-neighbor distance
• Approximate greedy clustering and distance selection for graph metrics
• Approximating nearest neighbor distances
• The Metric Nearness Problem
• Metric spaces with expensive distances
• Approximate Nearest Neighbor Searching with Non-Euclidean and Weighted Distances
• Determining Cosine Similarity Neighborhoods by Means of the Euclidean Distance
• scientific article; zbMATH DE number 2222699 (Why is no real title available?)

This page was built for publication: Approximating nearest neighbor distances

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449817)