Multidimensional binary search trees used for associative searching

By J. Bentley. 1975

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

Toward Interpretable-AI Policies Using Evolutionary Nonlinear Decision Trees for Discrete-Action Systems (2020, methodology): “In [27], regression trees are derived using classical methods, such as CART [22] and Kd-tree [28], to model Q -function through supervised training on batch of experiences and comparative study is made with ensemble techniques.”
Selective Experience Replay for Lifelong Learning (2018, methodology): “This time complexity can be reduced to O ( log ( | E | )) by using a KD-tree (Bentley 1975) and only comparing against the k nearest neighbors or to O ( k ) by sampling the buffer.”
Neural Episodic Control (2017, methodology): “Munos et al. (2016) show that by incorporating on-policy samples allows an agent to learn faster in Atari environments, indicating that reward propagation is indeed a bottleneck to efficiency in deep reinforcement learning.”
Generating Differentially Private Datasets Using GANs (2018, methodology): “ge features by the Inception V3 network (Szegedy et al. 2016) and use inverse distances between features as simfunction. We implement the KL divergence estimator (Perez-Cruz 2008) and use´ k-d trees (Bentley 1975) for fast nearest neighbour searches. For privacy evaluation, we implement the model in”
Particle-flow reconstruction and global event description with the CMS detector (2017, methodology): “In order to prevent the computing time of the link algorithm from growing quadratically with the number of particles, the pairs of elements considered by the link procedure are restricted to the nearest neighbours in the (η, φ) plane, as obtained with a k-dimensional tree [38].”
Index-driven similarity search in metric spaces (Survey Article) (2003, methodology): “This is the case for a PR quadtree [Orenstein 1982; Samet 1990], PR k-d tree [Orenstein 1982], as well as variants of k-d trees [Bentley 1975] such as the adaptive k-d tree [Friedman et al. 1977] and the BSP tree [Fuchs et al. 1980].”
Graph Matching Networks for Learning the Similarity of Graph Structured Objects (2019, methodology): “Therefore, the embeddings of graphs in a large database can be precomputed and indexed, which enables efﬁcient retrieval with fast nearest neighbor search data structures like k-d trees (Bentley, 1975) or locality sensitive hashing (Gionis et al., 1999).”
k-Nearest Neighbour Classifiers - A Tutorial (2020, background): “If the tree is not well balanced some retrieval times will be poor [6].”
A proof of the Gamma test (2002, methodology): “We remark that nearest-neighbour lists for the rst k nearest neighbours can be found in O(M log M ) time using techniques developed in Bentley (1975).”
Data stream clustering: A survey (2013, methodology): “2Considering a DBSCAN implementation that employs KD-trees [Bentley 1975].”
Interpretable Counterfactual Explanations Guided by Prototypes (2019, methodology): “If we do not have a trained encoder available, we can build class representations using k-d trees (Bentley 1975).”
Fast k-Nearest Neighbour Search via Prioritized DCI (2017, background): “It effectively trades off space for time and achieves polynomial query time in ambient dimensionality at the cost of exponential space complexity in ambient dimensionality.”