Analysis of approximate nearest neighbor searching with clustered point sets

By S. Maneewongvatana, David M. Mount. 1999

How researchers see this paper

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

SciPy 1.0: fundamental algorithms for scientific computing in Python (2019, background): “In 2013, the time complexity of the k -nearest-neighbor search from cKDTree.query was approximately loglinear 68 , consistent with its formal description 69 .”
Grounding Image Matching in 3D with MASt3R (2024, unknown): “When matching 3D points 𝑥 ∈ ℝ 3 , we implement NN ( 𝑥 ) using K-d trees [56].”
An Efficient k-Means Clustering Algorithm: Analysis and Implementation (2002, methodology): “The data structure implemented was a kd-tree that was constructed from the ANN library [43] using the sliding midpoint rule [39].”
A learning framework for nearest neighbor search (2007, background): “Indeed, we discovered at the time of press that the algorithm for KD-trees we describe appeared previously in [12].”
SciPy 1.0-Fundamental Algorithms for Scientific Computing in Python (2019, background): “In 2013, the time complexity of the k -nearest-neighbor search from cKDTree.query was approximately loglinear 68 , consistent with its formal description 69 .”