An Algorithm for Finding Best Matches in Logarithmic Expected Time

DOI10.1145/355744.355745zbMath0364.68037OpenAlexW2024668293WikidataQ56638872 ScholiaQ56638872MaRDI QIDQ4139672

Jon Louis Bentley, Raphael Ari Finkel, Jerome H. Friedman

Publication date: 1977

Published in: ACM Transactions on Mathematical Software (Search for Journal in Brave)

Full work available at URL: https://www.osti.gov/biblio/1443274

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Information storage and retrieval of data (68P20) General topics in the theory of software (68N01) Algorithms in computer science (68W99)

Related Items

d-blink: Distributed End-to-End Bayesian Entity Resolution, GEOMETRIC PROXIMITY GRAPHS FOR IMPROVING NEAREST NEIGHBOR METHODS IN INSTANCE-BASED LEARNING AND DATA MINING, An optimal-transport finite-particle method for mass diffusion, Bayesian Modeling and Classification of Neural Signals, Finding our way in the dark: approximate MCMC for approximate Bayesian methods, Efficient Lagrangian particle tracking algorithms for distributed-memory architectures, Data-driven computational method for growth-induced deformation problems of soft materials, Quantum computing enhanced distance-minimizing data-driven computational mechanics, A Lagrangian method for reactive transport with solid/aqueous chemical phase interaction, Expectations of Random Sets and Their Boundaries Using Oriented Distance Functions, Constructing a High-Dimensional k NN-Graph Using a Z-Order Curve, Efficient Learning and Feature Selection in High-Dimensional Regression, Learning Binary Hash Codes for Large-Scale Image Search, WINNING ENTRY OF THE K. U. LEUVEN TIME-SERIES PREDICTION COMPETITION, A STATE‐SPACE PARTITIONING METHOD FOR PRICING HIGH‐DIMENSIONAL AMERICAN‐STYLE OPTIONS, Introduction to vector quantization and its applications for numerics, Neighborhood Property–Based Pattern Selection for Support Vector Machines, A Method for Measuring Distance From a Training Data Set, A fast nearest neighbor search algorithm by filtration, An Improved Algorithm Finding Nearest Neighbor Using Kd-trees, Cryo-EM reconstruction of continuous heterogeneity by Laplacian spectral volumes, Dual‐tree fast exact max‐kernel search, Globally enumerating unstable periodic orbits for observed data using symbolic dynamics, Optimal Quantization for the Pricing of Swing Options, $C^\infty$ Compactly Supported and Positive Definite Radial Kernels, UniversalL^s-rate-optimality ofL^r-optimal quantizers by dilatation and contraction, A FAST IMPLEMENTATION OF THE ISODATA CLUSTERING ALGORITHM, Simplicial Multivalued Maps and the Witness Complex for Dynamical Analysis of Time Series, Evaluation of Range Searching Methods for Contact Searching in Mechanical Engineering, Estimating mutual information for feature selection in the presence of label noise, Dimensionality reduction of collective motion by principal manifolds, Random-walk based approximate \(k\)-nearest neighbors algorithm for diffusion state distance, A localized meshless approach for modeling spatial-temporal calcium dynamics in ventricular myocytes, A generalised multiple mapping conditioning approach for turbulent combustion, The efficiency of using k-d trees for finding nearest neighbors in discrete space, An approach to adaptive refinement for the RBF-FD method for 2D elliptic equations, Confidence Regions for Means of Random Sets Using Oriented Distance Functions, Example-based single document image super-resolution: a global MAP approach with outlier rejection, Optimal Delaunay and Voronoi Quantization Schemes for Pricing American Style Options, A mathematical model of controlling the growth of tissue in pigs, Detecting phase transitions in collective behavior using manifold's curvature, A stochastic multiple mapping conditioning computational model in openfoam for turbulent combustion, A symmetry based multiobjective clustering technique for automatic evolution of clusters, Rotation-discriminating template matching based on Fourier coefficients of radial projections with robustness to scaling and partial occlusion, Fast model predictive control combining offline method and online optimization with K-D tree, Strong form-based meshfree collocation method for wind-driven ocean circulation, On neural network design. I: Using the MVQ algorithm, Accounting for boundary effects in nearest-neighbor searching, Computational approximations of compact metric spaces, A mean field annealing approach to accurate free form shape matching, Local 2D Pattern Spectra as Connected Region Descriptors, Inversion and geodiversity: searching model space for the answers, Exploration of 2D and 3D environments using Voronoi transform and fast marching method, Scientific data interpolation with low dimensional manifold model, A computational approach for hypersonic nonequilibrium radiation utilizing space partition algorithm and Gauss quadrature, Entropy-based block processing for satellite image registration, Estimating abundance from counts in large data sets of irregularly spaced plots using spatial basis functions, A stochastic adaptive radial basis function algorithm for costly black-box optimization, Constructing Voronoi diagrams from hollow spheres using conformal geometric algebra, Fast neighbor search by using revised \(k\)-d tree, On coupling particle filter trajectories, Optimal choice of discriminators in a balanced K-D binary search tree, The saddle-straddle method to test for Wada basins, Decomposable algorithms for nearest neighbor computing, Unnamed Item, Finding nearest neighbors with Voronoi tessellations, Missing-values adjustment for mixed-type data, The extendible cell method for closest point problems, Directional density measure to intrinsically estimate and counteract non-uniformity in point clouds, Nearest neighbor estimates of entropy for multivariate circular distributions, Information storage and search complexity theory, How to speed up the quantization tree algorithm with an application to swing options, Geometric modeling of complex knitting stitches using a bicontinuous surface and its offsets, Using chaos to generate variations on movement sequences, Fuzzy-rough nearest neighbor algorithms in classification, A practical approach to the 2D incremental nearest-point problem suitable for different point distributions, Concurrent linearizable nearest neighbour search in LockFree-kD-tree, A greedy clustering algorithm based on interval pattern concepts and the problem of optimal box positioning, Projection-based model reduction: formulations for physics-based machine learning, How to find Steiner minimal trees in Euclidean \(d\)-space, An incremental learning algorithm based on the \( K\)-associated graph for non-stationary data classification, Efficient data structures for model-free data-driven computational mechanics, A kd-tree-accelerated hybrid data-driven/model-based approach for poroelasticity problems with multi-fidelity multi-physics data, KNN and adaptive comfort applied in decision making for HVAC systems, An adaptive framework for costly black-box global optimization based on radial basis function interpolation, Probably correct \(k\)-nearest neighbor search in high dimensions, Fast exact \(k\) nearest neighbors search using an orthogonal search tree, Approximate closest-point queries in high dimensions, Parallel re-initialization of level set functions on distributed unstructured tetrahedral grids, Analysis of range searches in quad trees, Chameleon based on clustering feature tree and its application in customer segmentation, Arbitrary 3D crack propagation with improved XFEM: accurate and efficient crack geometries, Multi-dimensional tree guided efficient global association for decomposition-based evolutionary many-objective optimization, WHEN ARE SWING OPTIONS BANG-BANG?, How to detect Wada basins, Index structures for fast similarity search for real vectors. II, Weighted quasi-interpolant spline approximations: properties and applications, GAPS: A clustering method using a new point symmetry-based distance measure, Diffusion-controlled reactions modeling in Geant4-DNA, A simple measure of conditional dependence, A new point symmetry based fuzzy genetic clustering technique for automatic evolution of clusters, ForestDSH: a universal hash design for discrete probability distributions, Enhancing point symmetry-based distance for data clustering, Fast high-dimensional node generation with variable density, A hierarchical detection framework for computational contact mechanics, Asymptotic expansions of the \(k\) nearest neighbor risk, Consensus hashing, A moving-box algorithm to estimate generalized dimensions and the \(f(\alpha)\) spectrum, Heuristic and optimization approaches to extending the Kohonen self organizing algorithm, Numerical Quadrature over the Surface of a Sphere, Parallel Algorithms for Nearest Neighbor Search Problems in High Dimensions, Projection-based model reduction of dynamical systems using space-time subspace and machine learning, Adaptive sparse approximations of scattered data, Core clustering as a tool for tackling noise in cluster labels, Feature ranking for multi-target regression, Fast model order reduction boundary element method for large-scale acoustic systems involving surface impedance, Approximating surfaces by moving total least squares method, A probabilistic result on multi-dimensional Delaunay triangulations, and its application to the 2D case, A numerical algorithm for multidimensional modeling of scattered data points, Refinements to nearest-neighbor searching in k-dimensional trees, A complete system for NN classification based on a VLSI array processor, Automatic error correction in flexion languages, Algorithms for ordering unorganized points along parametrized curves, Graph-theoretic algorithms for Kolmogorov operators: approximating solutions and their gradients in elliptic and parabolic problems on manifolds, Parallel solutions to geometric problems in the scan model of computation, A conversation with Jerry Friedman, Nearest neighbors methods for support vector machines, A selective sampling approach to active feature selection, Noise reduction in chaotic time series using scaled probabilistic methods