Multidimensional binary search trees used for associative searching

DOI10.1145/361002.361007zbMath0306.68061DBLPjournals/cacm/Bentley75OpenAlexW2165558283WikidataQ56638869 ScholiaQ56638869MaRDI QIDQ4062679

Jon Louis Bentley

Publication date: 1975

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

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Information storage and retrieval of data (68P20) General topics in the theory of software (68N01) Algorithms in computer science (68W99)

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

An algorithm for handling many relational calculus queries efficiently. ⋮ Peridynamics enabled learning partial differential equations ⋮ Automatic topography of high-dimensional data sets by non-parametric density peak clustering ⋮ Random-walk based approximate \(k\)-nearest neighbors algorithm for diffusion state distance ⋮ Online machine learning techniques for Coq: a comparison ⋮ Expected time analysis for Delaunay point location ⋮ Topology from time series ⋮ Determinstic VLSI block placement algorithm using less flexibility first principle ⋮ Boolean operations on 3D selective Nef complexes: data structure, algorithms, optimized implementation and experiments ⋮ Embedded local search approaches for routing optimization ⋮ A unified algorithm for finding maximum and minimum object enclosing rectangles and cuboids ⋮ On optimal cuts of hyperrectangles ⋮ Cloud-assisted secure biometric identification with sub-linear search efficiency ⋮ Fast spectral analysis for approximate nearest neighbor search ⋮ Automated flexion crease identification using internal image seams ⋮ Image replica detection system utilizing R-trees and linear discriminant analysis ⋮ Range searching in multidimensional databases using navigation metadata ⋮ A new internal index based on density core for clustering validation ⋮ Fast model predictive control combining offline method and online optimization with K-D tree ⋮ Quasi-Monte-Carlo methods and the dispersion of point sequences ⋮ Max-plus approximation for reinforcement learning ⋮ Accounting for boundary effects in nearest-neighbor searching ⋮ Predicting spatio-temporal time series using dimension reduced local states ⋮ Dense neighborhoods on affinity graph ⋮ Preparation of grids for simulations of groundwater flow in fractured porous media ⋮ Iterative estimation of rigid-body transformations ⋮ Locality preserving matching ⋮ Biased range trees ⋮ Quantum speed-up for unsupervised learning ⋮ Fast neighbor search by using revised \(k\)-d tree ⋮ Variations of largest rectangle recognition amidst a bichromatic point set ⋮ Convex variational methods on graphs for multiclass segmentation of high-dimensional data and point clouds ⋮ Stochastic distance transform: theory, algorithms and applications ⋮ Fast neighbor lists for adaptive-resolution particle simulations ⋮ Transforming Tanimoto queries on real valued vectors to range queries in Euclidean space ⋮ Posterior concentration for Bayesian regression trees and forests ⋮ Multibody multipole methods ⋮ Distance fields on unstructured grids: stable interpolation, assumed gradients, collision detection and gap function ⋮ A high order method for pricing of financial derivatives using radial basis function generated finite differences ⋮ Rotational projection statistics for 3D local surface description and object recognition ⋮ The localized RBFs collocation methods for solving high dimensional PDEs ⋮ Radial basis function generated finite differences for option pricing problems ⋮ Kernel-based adaptive approximation of functions with discontinuities ⋮ Concurrent linearizable nearest neighbour search in LockFree-kD-tree ⋮ Machine learning based classification of normal, slow and fast walking by extracting multimodal features from stride interval time series ⋮ Projection-based model reduction: formulations for physics-based machine learning ⋮ Anomaly detection in a mobile communication network ⋮ Efficient computation of spatial queries over points stored in \(k^2\)-tree compact data structures ⋮ Exact and efficient top-\(K\) inference for multi-target prediction by querying separable linear relational models ⋮ Anytime parallel density-based clustering ⋮ 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 ⋮ pBO-2GP-3B: a batch parallel known/unknown constrained Bayesian optimization with feasibility classification and its applications in computational fluid dynamics ⋮ A higher-order finite element method with unstructured anisotropic mesh adaption for two phase flows with surface tension ⋮ POPMUSIC for the travelling salesman problem ⋮ Implicit reconstructions of thin leaf surfaces from large, noisy point clouds ⋮ Efficient geometric reconstruction of complex geological structures ⋮ Symbolic image indexing and retrieval by spatial similarity: An approach based on B-tree ⋮ Meshless local Petrov-Galerkin solution of the neutron transport equation with streamline-upwind Petrov-Galerkin stabilization ⋮ A deterministic skip list for \(k\)-dimensional range search ⋮ Finding representative landmarks of data on manifolds ⋮ A multi-level method for data-driven finite element computations ⋮ Finite element solver for data-driven finite strain elasticity ⋮ Diffusion maps-aided neural networks for the solution of parametrized PDEs ⋮ A limit field for orthogonal range searches in two-dimensional random point search trees ⋮ Stochastic block models are a discrete surface tension ⋮ Multi-dimensional tree guided efficient global association for decomposition-based evolutionary many-objective optimization ⋮ An efficient and parallel level set reinitialization method -- application to micromechanics and microstructural evolutions ⋮ ForestDSH: a universal hash design for discrete probability distributions ⋮ Generalised kernel weighted fuzzy c-means clustering algorithm with local information ⋮ The \(n\)-dimensional \(k\)-vector and its application to orthogonal range searching ⋮ Fast discrete convolution in \(\mathbb{R}^2\) with radial kernels using non-uniform fast Fourier transform with nonequispaced frequencies ⋮ Maximum-likelihood approximate nearest neighbor method in real-time image recognition ⋮ Adaptive interpolation algorithm based on a kd-tree for numerical integration of systems of ordinary differential equations with interval initial conditions ⋮ Localized MQ-RBF meshless techniques for modeling unsaturated flow ⋮ Metric regression forests for correspondence estimation ⋮ Monte Carlo simulation of radiative transfer in a medium with varying refractive index specified at discrete points ⋮ Estimating multi-index models with response-conditional least squares ⋮ Random projection-based auxiliary information can improve tree-based nearest neighbor search ⋮ An adaptive binary-tree element subdivision method for evaluation of volume integrals with continuous or discontinuous kernels ⋮ A modified discrete-vortex method algorithm with shedding criterion for aerodynamic coefficients prediction at high angle of attack ⋮ A massively-parallel, unstructured overset method for mesh connectivity ⋮ A binary-tree element subdivision method for evaluation of nearly singular domain integrals with continuous or discontinuous kernel ⋮ Probabilistic analysis of vantage point trees ⋮ The properties of random trees ⋮ Computing the topology of Voronoï diagrams of parallel half-lines ⋮ Projection-based model reduction of dynamical systems using space-time subspace and machine learning ⋮ Adaptive sparse approximations of scattered data ⋮ Diffusion nets ⋮ Geometric prior of multi-resolution yielding manifolds and the local closest point projection for nearly non-smooth plasticity ⋮ A multigrid preconditioner for spatially adaptive high-order meshless method on fluid-solid interaction problems ⋮ A probabilistic result on multi-dimensional Delaunay triangulations, and its application to the 2D case ⋮ An effective quasi-human based heuristic for solving the rectangle packing problem ⋮ An efficient nearest neighbor search in high-dimensional data spaces ⋮ Comparison of various trees for nearest-point search with/without the Voronoi diagram. ⋮ Efficient splitting and merging algorithms for order decomposable problems. ⋮ A numerical algorithm for multidimensional modeling of scattered data points ⋮ Model-free global likelihood subsampling for massive data ⋮ Randomized partition trees for nearest neighbor search ⋮ Graph-theoretic algorithms for Kolmogorov operators: approximating solutions and their gradients in elliptic and parabolic problems on manifolds

This page was built for publication: Multidimensional binary search trees used for associative searching