An optimal algorithm for approximate nearest neighbor searching fixed dimensions

DOI10.1145/293347.293348zbMath1065.68650OpenAlexW2427881153WikidataQ55920348 ScholiaQ55920348MaRDI QIDQ3158524

Nathan S. Netanyahu, Angela Y. Wu, David M. Mount, Ruth Silverman, Sunil Arya

Publication date: 25 January 2005

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/293347.293348

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (only showing first 100 items - show all)

Nonlocal PDEs on graphs: from tug-of-war games to unified interpolation on images and point clouds ⋮ Kinetic \(k\)-semi-Yao graph and its applications ⋮ Efficiently approximating color-spanning balls ⋮ Efficient sparse ICP ⋮ IGA-suitable planar parameterization with patch structure simplification of closed-form polysquare ⋮ Optimizing the geometrical accuracy of curvilinear meshes ⋮ Meshfree, probabilistic determination of point sets and support regions for meshless computing ⋮ A stabilized finite element method using a discontinuous level set approach for the computation of bubble dynamics ⋮ Fast and versatile algorithm for nearest neighbor search based on a lower bound tree ⋮ Robust multi-view feature matching from multiple unordered views ⋮ A logarithmic-time solution to the point location problem for parametric linear programming ⋮ TSS: temporal similarity search measure for heterogeneous information networks ⋮ Fast \(k\) most similar neighbor classifier for mixed data (tree \(k\)-MSN) ⋮ Familiarity based unified visual attention model for fast and robust object recognition ⋮ On plane geometric spanners: a survey and open problems ⋮ Partition of unity interpolation using stable kernel-based techniques ⋮ Matching sets of line segments ⋮ Approximate distance oracles for graphs with dense clusters ⋮ Computational approximations of compact metric spaces ⋮ Reliable region predictions for automated valuation models ⋮ Closest pair and the post office problem for stochastic points ⋮ An immersed boundary method for complex incompressible flows ⋮ GPU accelerated initialization of local maximum-entropy meshfree methods for vibrational and acoustic problems ⋮ Dense neighborhoods on affinity graph ⋮ A computational approach for hypersonic nonequilibrium radiation utilizing space partition algorithm and Gauss quadrature ⋮ Fast-Match: fast affine template matching ⋮ Virtuaschlieren: a hybrid GPU/CPU-based schlieren simulator for ideal and non-ideal compressible-fluid flows ⋮ Fast computation of triangular Shepard interpolants ⋮ Iterative denoising ⋮ Approximate range searching in external memory ⋮ Low-interference networks in metric spaces of bounded doubling dimension ⋮ Fuzzy transform and least-squares approximation: Analogies, differences, and generalizations ⋮ Robust proximity search for balls using sublinear space ⋮ Geometric spanners for weighted point sets ⋮ Optimal selection of local approximants in RBF-PU interpolation ⋮ Multilabel classification with meta-level features in a learning-to-rank framework ⋮ Energy-efficient paths in radio networks ⋮ Geodesics on point clouds ⋮ Counts-of-counts similarity for prediction and search in relational data ⋮ A discrete mathematical model for chaotic dynamics in economics: Kaldor's model on business cycle ⋮ Adaptive finite element analysis of elliptic problems based on bubble-type local mesh generation ⋮ Two-dimensional Laplacianfaces method for face recognition ⋮ A practical approach to the 2D incremental nearest-point problem suitable for different point distributions ⋮ Scalable representation for 3D object recognition using feature sharing and view clustering ⋮ Concurrent linearizable nearest neighbour search in LockFree-kD-tree ⋮ Efficient computation of spatial queries over points stored in \(k^2\)-tree compact data structures ⋮ A variant of \(k\)-nearest neighbors search with cyclically permuted query points for rotation-invariant image processing ⋮ Efficient data structures for model-free data-driven computational mechanics ⋮ Group nearest-neighbor queries in the \(L_1\) plane ⋮ Index structures for fast similarity search for real-valued vectors. I ⋮ Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points ⋮ Image classification based on quantum K-nearest-neighbor algorithm ⋮ Positive constrained approximation via RBF-based partition of unity method ⋮ Approximating geodesic distances on 2-manifolds in \(\mathbb{R}^3\): The weighted case ⋮ Transient adaptivity applied to two-phase incompressible flows ⋮ An information theoretic approach to use high-fidelity codes to calibrate low-fidelity codes ⋮ Clustering and maximum likelihood search for efficient statistical classification with medium-sized databases ⋮ Probably correct \(k\)-nearest neighbor search in high dimensions ⋮ Discretizing Laplace-Beltrami operator from differential quantities ⋮ Well-separated pair decomposition in linear time? ⋮ Knowledge discovery by accuracy maximization ⋮ Efficient computation of partition of unity interpolants through a block-based searching technique ⋮ Conic nearest neighbor queries and approximate Voronoi diagrams ⋮ Finding representative landmarks of data on manifolds ⋮ Using hash tables to manage the time-storage complexity in a point location problem: application to explicit model predictive control ⋮ Adaptive radial basis function partition of unity interpolation: a bivariate algorithm for unstructured data ⋮ Extreme value theory for anomaly detection -- the GPD classifier ⋮ Index structures for fast similarity search for real vectors. II ⋮ Nearest neighbour group-based classification ⋮ Deformable spanners and applications ⋮ Nearest neighbors search using point location in balls with applications to approximate Voronoi decompositions ⋮ An \(O(\log n)\) query time algorithm for reducing \(\varepsilon \)-NN to \((c,r)\)-NN ⋮ Ramsey partitions and proximity data structures ⋮ Generalised kernel weighted fuzzy c-means clustering algorithm with local information ⋮ Error indicators and refinement strategies for solving Poisson problems through a RBF partition of unity collocation scheme ⋮ Cycle bases of graphs and sampled manifolds ⋮ Maximum-likelihood approximate nearest neighbor method in real-time image recognition ⋮ Efficient temporal pattern recognition by means of dissimilarity space embedding with discriminative prototypes ⋮ Covering Minkowski sum boundary using points with applications ⋮ Practical methods for shape fitting and kinetic data structures using coresets ⋮ Monte Carlo simulation of radiative transfer in a medium with varying refractive index specified at discrete points ⋮ Approximate similarity search: a multi-faceted problem ⋮ A Bayesian approach for comparing cross-validated algorithms on multiple data sets ⋮ Consensus hashing ⋮ An efficient trivariate algorithm for tetrahedral Shepard interpolation ⋮ Fitting a \(C^m\)-smooth function to data. II ⋮ The \(C^m\) norm of a function with prescribed jets. II ⋮ Kernel-independent adaptive construction of \(\mathcal{H}^2\)-matrix approximations ⋮ Spatiotemporal pattern extraction by spectral analysis of vector-valued observables ⋮ An immersed boundary method coupled with a dynamic overlapping-grids strategy ⋮ A quadrature-free discontinuous Galerkin method for the level set equation ⋮ Kaldor-Kalecki new model on business cycles ⋮ A numerical algorithm for multidimensional modeling of scattered data points ⋮ Chromatic nearest neighbor searching: A query sensitive approach ⋮ Approximate range searching ⋮ Randomized partition trees for nearest neighbor search ⋮ On approximate nearest neighbors under \(l_\infty\) norm ⋮ Graph-theoretic algorithms for Kolmogorov operators: approximating solutions and their gradients in elliptic and parabolic problems on manifolds ⋮ Similarity, kernels, and the fundamental constraints on cognition ⋮ Approximate \(k\)-closest-pairs in large high-dimensional data sets

This page was built for publication: An optimal algorithm for approximate nearest neighbor searching fixed dimensions