Scalable Nearest Neighbor Algorithms for High Dimensional Data

Marius MujaD. Lowe

article2014TPAMI1,537 citations

Presents scalable approximate nearest neighbor search methods, including randomized k-d trees and priority search k-means trees, paired with an automated configuration mechanism implemented in the widely used FLANN library to drastically accelerate high-dimensional matching.

Listen

Modern computer vision and machine learning applications rely heavily on massive datasets to achieve high accuracy in tasks such as object recognition and image retrieval. However, locating the most similar high-dimensional data points—known as nearest neighbor matching—is often the primary computational bottleneck in these pipelines. Performing exact nearest neighbor searches across millions of data points is computationally prohibitive, while manually tuning approximate search algorithms for specific datasets is labor-intensive and inefficient.

The article evaluates scalable approximate nearest neighbor matching methods, introduces new algorithms for vector and binary data, presents an automated framework to select optimal algorithms and search parameters, and develops a distributed computing approach to scale to massive datasets.

To establish these solutions, the authors conducted empirical evaluations across standard benchmark collections, including datasets ranging from 100,000 to 80 million visual features and image patches. They compared traditional partitioning and hashing techniques against newly developed methods, formulated an optimization pipeline combining global grid search and local simplex optimization to tune search parameters automatically, and implemented an index-agnostic distributed framework using standard message-passing cluster architecture.

The analysis established several key operational findings. First, two algorithms consistently outperformed other approaches for continuous vector data: the randomized tree forest and the newly developed priority search clustering tree, which exceeded common baseline and hashing approaches by approximately an order of magnitude in speed at comparable precision levels. Second, for binary features, searching multiple hierarchical clustering trees outperformed standard locality-sensitive hashing while requiring one-sixth of the memory at high search precisions. Third, trading exact precision for approximation yielded massive efficiency gains: accepting a 60 percent precision target resulted in search speedups up to three orders of magnitude faster than linear search, while high precisions above 90 percent still achieved speedups of nearly two orders of magnitude. Finally, the distributed indexing framework scaled successfully to an 80-million-image collection across compute clusters without architectural bottlenecks.

These results demonstrate that organizations can reduce computational processing time and server hardware costs by orders of magnitude while retaining high operational accuracy. The automated tuning mechanism eliminates guesswork, allowing systems to systematically balance search speed, index build time, and memory overhead based on specific business and infrastructure requirements. Furthermore, the cluster framework enables seamless horizontal scaling as datasets expand beyond the random-access memory capacity of single machines.

Organizations handling large-scale visual or feature data should adopt the Fast Library for Approximate Nearest Neighbors (FLANN) framework, where these methods are implemented. Technical teams should integrate the automated configuration tool as a standard pre-processing step to determine the best algorithm and parameter configuration for each unique dataset type. When deploying across multi-core servers, system architects should distribute workloads across multiple machines rather than oversaturating a single machine's CPU cores to prevent memory bandwidth bottlenecks.

Confidence in these findings is high given the extensive empirical validation and real-world adoption in industry-standard software libraries. However, stakeholders should note that performance gains depend heavily on the underlying structure of the data: datasets with highly correlated dimensions yield significantly greater speedups than purely random vectors, and optimal parameter configurations should be re-evaluated when the fundamental distribution or structure of incoming data changes.

BitLit Media Inc University of British Columbia cluster architecture computer vision cpu scalable nearest neighbor algorithms high dimensional data multiple randomized kd-trees

flann-lib/flann Muja et al (2014).pdf

Paper: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions, Alexandr Andoni et al. (2008). This survey details locality-sensitive hashing and sublinear nearest neighbor search foundations that the FLANN paper directly benchmarks against and seeks to outperform.
Paper: Similarity Search in High Dimensions via Hashing, Aristides Gionis et al. (1999). This foundational paper establishes locality-sensitive hashing for high-dimensional approximate nearest neighbor search, providing the primary baseline algorithm evaluated in the source.
Paper: A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Roger Weber et al. (1998). This seminal study establishes the theoretical and practical performance limits of multidimensional partitioning trees under the curse of dimensionality, motivating FLANN's priority search and randomized approximations.
Paper: An Efficient k-Means Clustering Algorithm: Analysis and Implementation, Tapas Kanungo et al. (2002). This work introduces kd-tree filtering to accelerate k-means clustering, directly informing tree-based space partitioning for approximate nearest neighbor algorithms.
Paper: Iterative Quantization: A Procrustean Approach to Learning Binary Codes for Large-Scale Image Retrieval, Yunchao Gong et al. (2013). This paper presents iterative quantization for mapping continuous descriptors into binary codes, representing the binary feature encoding methods evaluated in FLANN.
Paper: Nearest neighbor queries, N. Roussopoulos et al. (1995). This foundational study introduces branch-and-bound nearest neighbor search using spatial tree bounding metrics, which underlies priority tree search strategies.
Paper: The X-tree : An Index Structure for High-Dimensional Data, S. Berchtold et al. (2001). This paper analyzes the breakdown of traditional spatial index trees in high dimensions due to directory overlap, providing background on the tree degradation problems FLANN resolves.

Paper: Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs, Yu. A. Malkov et al. (2016). Hierarchical Navigable Small World (HNSW) graphs represent the next evolutionary leap in approximate nearest neighbor search, significantly outperforming tree-based methods like FLANN on large-scale vector retrieval.
Paper: Billion-Scale Similarity Search with GPUs, Jeff Johnson et al. (2019). FAISS extends high-dimensional similarity search beyond CPU tree forests to billion-scale datasets using highly optimized GPU architectures and product quantization.
Paper: DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node, Suhas Jayaram Subramanya et al. (2019). DiskANN advances scalable nearest neighbor search by combining graph indices with SSD-resident storage to index billion-point datasets efficiently on a single workstation.
Paper: Stop Indexing at Full Precision: Revisiting Clustering for Vector Embeddings, Leonardo Kuffo et al. (2026). This work directly addresses the computational bottleneck of building partition-based vector indexes by demonstrating that aggressive quantization and dimensionality reduction can precede clustering.
Paper: Accelerating Large-Scale Inference with Anisotropic Vector Quantization, Ruiqi Guo et al. (2020). This book applies asymmetric vector quantization to optimize inner-product approximate search, improving upon traditional Euclidean nearest neighbor indexing.
Paper: Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval, Lee Xiong et al. (2021). ANCE incorporates approximate nearest neighbor index lookups dynamically during contrastive model training to retrieve hard negative examples for dense text search.
Paper: Re-ranking Person Re-identification with k-Reciprocal Encoding, Zhun Zhong et al. (2017). This method utilizes k-reciprocal nearest neighbor relationships to re-rank and filter false positives generated by initial nearest neighbor visual feature searches.

Cover for Scalable Nearest Neighbor Algorithms for High Dimensional Data

Abstract

For many computer vision and machine learning problems, large training sets are key for good performance. However, the most computationally expensive part of many computer vision and machine learning algorithms consists of finding nearest neighbor matches to high dimensional vectors that represent the training data. We propose new algorithms for approximate nearest neighbor matching and evaluate and compare them with previous algorithms. For matching high dimensional features, we find two algorithms to be the most efficient: the randomized k-d forest and a new algorithm proposed in this paper, the priority search k-means tree. We also propose a new algorithm for matching binary features by searching multiple hierarchical clustering trees and show it outperforms methods typically used in the literature. We show that the optimal nearest neighbor algorithm and its parameters depend on the data set characteristics and describe an automated configuration procedure for finding the best algorithm to search a particular data set. In order to scale to very large data sets that would otherwise not fit in the memory of a single machine, we propose a distributed nearest neighbor matching framework that can be used with any of the algorithms described in the paper. All this research has been released as an open source library called fast library for approximate nearest neighbors (FLANN), which has been incorporated into OpenCV and is now one of the most popular libraries for nearest neighbor matching.

1 INTRODUCTION
1.1 Definitions and Notation
2 BACKGROUND
2.1 Nearest Neighbor Matching Algorithms
2.1.1 Partitioning Trees
2.1.2 Hashing Based Nearest Neighbor Techniques
2.1.3 Nearest Neighbor Graph Techniques
2.2 Automatic Configuration of NN Algorithms
3 FAST APPROXIMATE NN MATCHING
3.1 The Randomized k-d Tree Algorithm
3.2 The Priority Search K-Means Tree Algorithm
3.2.1 Algorithm Description
3.2.2 Analysis
3.3 The Hierarchical Clustering Tree
3.4 Automatic Selection of the Optimal Algorithm
4 EXPERIMENTS
4.1 Fast Approximate Nearest Neighbor Search
4.1.1 Data Dimensionality
4.1.2 Search Precision
4.1.3 Automatic Selection of Optimal Algorithm
4.2 Binary Features
5 SCALING NEAREST NEIGHBOR SEARCH
5.1 Searching on a Compute Cluster
5.2 Evaluation of Distributed Search
6 THE FLANN LIBRARY
7 CONCLUSIONS
REFERENCES

Knowls

Knowl 1 — Priority Search K-Means Tree Algorithm
algorithm
The priority search $k$ -means tree is an approximate nearest neighbor search algorithm designed for continuous vector spaces. During index construction, the data points are recursively partitioned into $K$ clusters using $k$ -means clustering until a node contains fewer than $K$ points. During query processing, the tree is traversed using a best-bin-first strategy: at each node, the branch with the closest cluster center to the query is explored first, while all other unexplored sibling branches are pushed to a global priority queue sorted in ascending order of the distance from the query to their cluster center boundaries.
Algorithm: BuildPrioritySearchKMeansTree
Input: Dataset $D$ , branching factor $K$ , maximum iterations $I_{max}$ , center selection method $C_{alg}$
Output: Priority search $k$ -means tree node
if $|D| < K$ then
    return CreateLeafNode( $D$ )
else
     $P \leftarrow$ Select $K$ initial cluster centers from $D$ using $C_{alg}$
     $converged \leftarrow$ false
     $iterations \leftarrow$ 0
    while not $converged$ and $iterations < I_{max}$ do
         $C \leftarrow$ Cluster points in $D$ around nearest centers in $P$
         $P_{new} \leftarrow$ Compute mean vectors of clusters in $C$
        if $P = P_{new}$ then
             $converged \leftarrow$ true
        end if
         $P \leftarrow P_{new}$
         $iterations \leftarrow iterations + 1$
    end while
    for each cluster $C_i \in C$ do
         $child_i \leftarrow$ BuildPrioritySearchKMeansTree( $C_i$ , $K$ , $I_{max}$ , $C_{alg}$ )
    end for
    return CreateNonLeafNode(Centers: $P$ , Children: $\{child_1, \dots, child_K\}$ )
end if
Algorithm: SearchPrioritySearchKMeansTree
Input: Tree root $T$ , query point $q$ , max points to examine $L$ , number of neighbors $k_{nn}$
Output: Approximate $k_{nn}$ nearest neighbors of $q$
$count \leftarrow 0$
$PQ \leftarrow$ EmptyPriorityQueue() // ordered by distance from $q$ to branch boundary
$R \leftarrow$ EmptyPriorityQueue() // stores nearest candidates found so far
TraverseKMeansTree( $T$ , $PQ$ , $R$ , $count$ , $q$ )
while $PQ$ is not empty and $count < L$ do
     $N \leftarrow$ PopMin( $PQ$ )
    TraverseKMeansTree( $N$ , $PQ$ , $R$ , $count$ , $q$ )
end while
return Top $k_{nn}$ points from $R$
Procedure TraverseKMeansTree( $N$ , $PQ$ , $R$ , $count$ , $q$ )
if $N$ is leaf node then
    Compute distance from $q$ to all points in $N$ , insert into $R$
     $count \leftarrow count + |N|$
else
     $C \leftarrow$ Child nodes of $N$
     $C_q \leftarrow$ Child node in $C$ whose center is closest to $q$
     $C_p \leftarrow C \setminus \{C_q\}$
    Add all nodes in $C_p$ to $PQ$
    TraverseKMeansTree( $C_q$ , $PQ$ , $R$ , $count$ , $q$ )
end if
Setting the iteration cap $I_{max}$ as low as $7$ yields over $90\%$ of the search efficiency obtained with full $k$ -means convergence while cutting tree construction time by over $90\%$ . Random selection of initial cluster centers ( $C_{alg}$ ) performs comparably to Gonzales or $k$ -means++ seeding.
Knowl 2 — Randomized k-d Forest Algorithm
algorithm
The randomized $k$ -d forest algorithm constructs multiple randomized $k$ -d trees over the same dataset and searches them in parallel. Unlike classic $k$ -d trees that split points along the single dimension with maximum variance, each randomized tree selects its split dimension uniformly at random from the top $N_D$ dimensions exhibiting the highest coordinate variance (with $N_D = 5$ serving as an effective default).
Algorithm: SearchRandomizedKDForest
Input: Forest of randomized trees $\{T_1, \dots, T_m\}$ , query point $q$ , max leaf visits $L_{max}$ , neighbors $k_{nn}$
Output: Approximate $k_{nn}$ nearest neighbors of $q$
$PQ \leftarrow$ EmptyPriorityQueue() // ordered by distance to splitting hyperplanes
$R \leftarrow$ EmptyPriorityQueue() // candidate nearest neighbors
$leaves\_visited \leftarrow 0$
$visited\_points \leftarrow$ EmptySet()
for each tree $T_i$ in $\{T_1, \dots, T_m\}$ do
    TraverseKDTree( $T_i$ , $q$ , $PQ$ , $R$ , $visited\_points$ , $leaves\_visited$ )
end for
while $PQ$ is not empty and $leaves\_visited < L_{max}$ do
     $node \leftarrow$ PopMin( $PQ$ )
    TraverseKDTree( $node$ , $q$ , $PQ$ , $R$ , $visited\_points$ , $leaves\_visited$ )
end while
return Top $k_{nn}$ points from $R$
Procedure TraverseKDTree( $N$ , $q$ , $PQ$ , $R$ , $visited\_points$ , $leaves\_visited$ )
if $N$ is a leaf node then
    for each point $p \in N$ do
        if $p \notin visited\_points$ then
            Add $p$ to $visited\_points$
            Compute distance $d(q, p)$ and update $R$
        end if
    end for
     $leaves\_visited \leftarrow leaves\_visited + 1$
else
     $d_{split} \leftarrow$ split dimension of $N$
     $v_{split} \leftarrow$ split value of $N$
    if $q[d_{split}] < v_{split}$ then
         $near \leftarrow N.left$ , $far \leftarrow N.right$
    else
         $near \leftarrow N.right$ , $far \leftarrow N.left$
    end if
    Push $far$ to $PQ$ with priority $|q[d_{split}] - v_{split}|$
    TraverseKDTree( $near$ , $q$ , $PQ$ , $R$ , $visited\_points$ , $leaves\_visited$ )
end if
A single priority queue is shared across all $m$ trees, ordered by increasing distance between the query point and the splitting hyperplane of each deferred branch. Searching across multiple randomized trees reduces the probability that a query and its true nearest neighbor fall into different partitions at early tree splits.
Knowl 3 — Hierarchical Clustering Forest for Binary Descriptors
algorithm
For binary feature vectors (such as BRIEF, ORB, or BRISK) compared via Hamming distance, arithmetic means are undefined, rendering standard $k$ -means trees unsuitable. The hierarchical clustering tree recursively partitions binary data by randomly choosing $K$ data points directly from the input subset as cluster centers and assigning each remaining point to its closest center via Hamming distance.
Algorithm: BuildHierarchicalClusteringTree
Input: Dataset $D$ , branching factor $K$ , maximum leaf size $S_L$
Output: Hierarchical clustering tree node
if $|D| < S_L$ then
    return CreateLeafNode( $D$ )
else
     $P \leftarrow$ Select $K$ random points from $D$
     $C \leftarrow$ Cluster points in $D$ around nearest centers in $P$ using Hamming distance
    for each cluster $C_i \in C$ do
         $child_i \leftarrow$ BuildHierarchicalClusteringTree( $C_i$ , $K$ , $S_L$ )
    end for
    return CreateNonLeafNode(Centers: $P$ , Children: $\{child_1, \dots, child_K\}$ )
end if
To maximize approximate matching performance, multiple independent hierarchical clustering trees are constructed and queried simultaneously using a shared priority queue that tracks unexplored branches across all trees ordered by center distance, mirroring the randomized $k$ -d forest search strategy.
Knowl 4 — Time Complexity of Priority Search K-Means Tree
theoretical result
For a dataset of $n$ points in a $d$ -dimensional space, constructing a balanced priority search $k$ -means tree with branching factor $K$ and a maximum of $I$ iterations per clustering step requires:

$\mathcal{O}\left(n d K I \frac{\log n}{\log K}\right)$

At each level of the tree, $k$ -means clustering across all internal nodes processes $n$ total points, costing $\mathcal{O}(n d K I)$ . The balanced tree has a height of $\frac{\log n}{\log K}$ , leading directly to the total construction cost.

For a time-constrained approximate nearest neighbor query terminating after examining $L$ data points, the search time complexity is:

$\mathcal{O}\left(L d \frac{\log n}{\log K}\right)$

In a complete tree where each leaf holds $K$ points, examining $L$ points requires $L/K$ top-down traversals. Each traversal visits $\mathcal{O}(\frac{\log n}{\log K})$ internal nodes and one leaf node. At each internal node, computing distances to $K$ child centers requires $\mathcal{O}(K d)$ operations, while maintaining unexplored branches in a priority queue takes $\mathcal{O}(K)$ amortized time using binomial heaps. Evaluating the $K$ points in the target leaf requires $\mathcal{O}(K d)$ operations.
Knowl 5 — Cost Metric and Automatic Parameter Optimization for Approximate NN Search
model/method
To automatically configure algorithm selection and hyperparameter tuning for a specific dataset, the choice of algorithm and its parameters is formulated as an optimization problem minimizing a composite cost function $c(\theta)$ over the configuration space $\Theta$ :

$\min_{\theta \in \Theta} c(\theta)$

$\text{where } c(\theta) = \frac{s(\theta) + w_b b(\theta)}{\min_{\theta' \in \Theta}(s(\theta') + w_b b(\theta'))} + w_m m(\theta)$

Here:
- $\theta \in \Theta$ represents the algorithm and parameter tuple (e.g., number of trees for $k$ -d forests; branching factor $K$ , iteration limit $I_{max}$ , and initial center selection for $k$ -means trees).
- $s(\theta)$ is the search time required to query the same number of points as are in the index.
- $b(\theta)$ is the tree build time.
- $m(\theta) = m_t(\theta) / m_d$ is the memory overhead, defined as the ratio of memory consumed by the index tree(s) $m_t(\theta)$ to the memory consumed by the raw data $m_d$ .
- $w_b \ge 0$ is a weight controlling the penalty of index build time relative to search time.
- $w_m \ge 0$ is a weight controlling the penalty of memory overhead.
Optimization proceeds in two sequential stages using random subsampling cross-validation:
1. Global exploration over $\Theta$ via grid search.
2. Local fine-tuning starting from the best grid-search point using the Nelder-Mead downhill simplex algorithm.
Knowl 6 — Distributed Nearest Neighbor Search via MPI Partitioning
algorithm
Distributed nearest neighbor search scales approximate search across compute clusters using the Message Passing Interface (MPI) by partitioning the dataset into disjoint subsets without requiring a centralized routing index.
Algorithm: BuildDistributedIndex
Input: Dataset $D$ , index parameter set $P$
1: $i \leftarrow \text{MPI\_rank}()$
2: $D_i \leftarrow$ Read subset of $D$ corresponding to rank $i$ from distributed filesystem
3: Build local index $Index_i$ on process $i$ using $D_i$ and parameters $P$
4: $\text{MPI\_barrier}()$ // Synchronize cluster processes
Algorithm: SearchDistributedIndex
Input: Query $Q$ , search parameters $P_{search}$
1: $\text{MPI\_broadcast}(Q, P_{search})$ // Master broadcasts query and parameters to all processes
2: $NN_i \leftarrow$ Run local nearest neighbor search on $Index_i$ with query $Q$ and parameters $P_{search}$
3: $NN \leftarrow \text{MPI\_reduce}(NN_i)$ // Hierarchically merge candidate nearest neighbors across ranks
4: return $NN$
The master process (rank 0) broadcasts the query to all cluster worker nodes. Each worker performs the approximate nearest neighbor search independently on its local data subset $D_i$ . The intermediate neighbor lists (along with precomputed distances) are hierarchically combined using an MPI reduce operation back to the master process, avoiding distance recomputations.

Knowl 7 — Empirical Parameter Configurations Selected by Auto-Tuning on SIFT Features

data/table

The automatic configuration procedure was evaluated on a dataset of 100,000 SIFT features (128 dimensions) targeting search precisions of $60\%$ and $90\%$ across varying trade-off weights for index build time ( $w_b$ ) and memory overhead ( $w_m$ ).

Pr. (%)	$w_b$	$w_m$	Algorithm Configuration	Dist. Error	Search Speedup	Memory Used	Build Time
60%	0	0	k-means, 16, 15	0.096	181.10	0.51	0.58
60%	0	1	k-means, 32, 10	0.058	180.9	0.37	0.56
60%	0.01	0	k-means, 16, 5	0.077	163.25	0.50	0.26
60%	0.01	1	kd-tree, 4	0.041	109.50	0.26	0.12
60%	1	0	kd-tree, 1	0.044	56.87	0.07	0.03
60%	*	$\infty$	kd-tree, 1	0.044	56.87	0.07	0.03
90%	0	0	k-means, 128, 10	0.008	31.67	0.18	1.82
90%	0	1	k-means, 128, 15	0.007	30.53	0.18	2.32
90%	0.01	0	k-means, 32, 5	0.011	29.47	0.36	0.35
90%	0.01	1	k-means, 16, 1	0.016	21.59	0.48	0.10
90%	1	0	kd-tree, 1	0.005	5.05	0.07	0.03
90%	*	$\infty$	kd-tree, 1	0.005	5.05	0.07	0.03

In the Algorithm Configuration column, k-means, K, I specifies branching factor $K$ and iteration count $I$ ; kd-tree, T specifies the number of randomized trees $T$ .
Dist. Error is the mean distance error relative to exact nearest neighbors.
Search Speedup measures linear search time divided by approximate search time.
Memory Used is index memory expressed as a fraction of the raw data size ( $m_t / m_d$ ).
Build Time is index build time expressed as a fraction of linear search time over the test set.

When build time and memory are unrestricted ( $w_b=0, w_m=0$ ), priority search $k$ -means achieves the highest search speedup ( $181.1\times$ at $60\%$ precision; $31.67\times$ at $90\%$ precision). When build time or memory is heavily penalized ( $w_b=1$ or $w_m=\infty$ ), the optimizer selects a single randomized $k$ -d tree, cutting build time to $0.03\times$ and memory overhead to $0.07\times$ at the cost of lower search speedup.

Knowl 8 — Search Efficiency: Space Partitioning vs. LSH and Single k-d Trees
empirical result
On 128-dimensional SIFT datasets (100,000 points), priority search $k$ -means trees and randomized $k$ -d tree forests outperform both standard locality sensitive hashing (via the $E^2LSH$ implementation) and single $k$ -d trees (via the ANN library) in search speedup by approximately one order of magnitude across target precision levels ranging from $50\%$ to $100\%$ .

For binary descriptors (5 million BRIEF and ORB features from recognition benchmarks), the multiple hierarchical clustering forest achieves superior speedup compared to multi-probe LSH across all precision levels ( $50\%$ to $99\%$ ). Furthermore, multi-probe LSH requires $6\times$ more memory than the hierarchical clustering tree when high search precision ( $>90\%$ ) is demanded, due to the rapid growth in hash table allocations required to maintain accuracy.
Knowl 9 — Effect of Intrinsic Dimensionality and Data Correlation on Tree Search Speedup
empirical result
Nearest neighbor search performance in high-dimensional spaces depends strongly on the correlation structure of the data:
1. For uniformly distributed random vectors lacking dimensional correlation, search speedup degrades exponentially as dimensionality grows; for $68\%$ search precision on $10^5$ random points, approximate search speedup becomes no better than linear search when dimensionality exceeds 800.
2. For natural image patches (Winder/Brown dataset, up to $64 \times 64 = 4,096$ dimensions), search speedup does not degrade with increasing dimensionality and can even increase, because strong inter-dimensional correlations allow distances along a few dimensions to provide reliable nearest-neighbor evidence.
3. On correlated image patch datasets (e.g., Trevi Fountain patches), randomized $k$ -d forests outperform priority search $k$ -means trees across almost all precision levels because axis-aligned splits effectively exploit low intrinsic dimensionality. Conversely, priority search $k$ -means trees achieve higher speedups on uncorrelated data or when very high precision ( $>90\%$ ) is targeted.
Knowl 10 — Memory Bus Saturation in Multi-Core Approximate Nearest Neighbor Search
limitation
When parallelizing approximate nearest neighbor search across multiple processes on a single shared-memory multi-core machine (evaluated on an 8-core system with 8 million tiny images):
- Search speedup scales positively when increasing parallel MPI worker processes from 1 to 4.
- Increasing the number of processes from 4 to 8 causes overall search throughput to decline.
This performance degradation occurs because multiple parallel search processes issuing simultaneous random index and data reads saturate the shared main memory bus, shifting the execution bottleneck from CPU processing to memory bandwidth. Distributing the same 8 processes across multiple physical machines (e.g., 4 processes across 2 machines, or 8 processes across 3 machines) reduces the memory access pressure per node and restores scaling performance.

Coverage note — None was omitted; all primary algorithms (randomized kd-forest, priority search k-means, hierarchical binary tree, distributed search via MPI), theoretical complexity derivations, the optimization framework and cost formulation, and the empirical benchmarking results are included as knowls.

References

1.D. G. Lowe, “Distinctive image features from scale-invariant keypoints,” Int. J. Comput. Vis., vol. 60, no. 2, pp. 91–110, 2004.
2.J. Philbin, O. Chum, M. Isard, J. Sivic, and A. Zisserman, “Object retrieval with large vocabularies and fast spatial matching,” in Proc. IEEE Conf. Comput. Vis. Pattern Recog., 2007, pp. 1–8.
3.J. Sivic and A. Zisserman, “Video Google: A text retrieval approach to object matching in videos,” in Proc. IEEE 9th Int. Conf. Comput. Vis., 2003, pp. 1470–1477.
4.J. Hays and A. A. Efros, “Scene completion using millions of photographs,” ACM Trans. Graph., vol. 26, p. 4, 2007.
5.G. Shakhnarovich, P. Viola, and T. Darrell, “Fast pose estimation with parameter-sensitive hashing,” in Proc. IEEE 9th Int. Conf. Comput. Vis., 2003, pp. 750–757.
6.A. C. Berg, T. L. Berg, and J. Malik, “Shape matching and object recognition using low distortion correspondences,” in Proc. IEEE CS Conf. Comput. Vis. Pattern Recog., 2005, vol. 1, pp. 26–33.
7.A. Torralba, R. Fergus, and W.T. Freeman, “80 million tiny images: A large data set for nonparametric object and scene recognition,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 30, no. 11, pp. 1958–1970, Nov. 2008.
8.J. Deng, W. Dong, R. Socher, L. J. Li, K. Li, and L. Fei Fei, “ImageNet: A large-scale hierarchical image database,” in Proc. IEEE Conf. Comput. Vis. Pattern Recog., 2009, pp. 248–255.
9.J. L. Bentley, “Multidimensional binary search trees used for associative searching,” Commun. ACM, vol. 18, no. 9, pp. 509–517, 1975.
10.J. H. Friedman, J. L. Bentley, and R. A. Finkel, “An algorithm for finding best matches in logarithmic expected time,” ACM Trans. Math. Softw., vol. 3, no. 3, pp. 209–226, 1977.
11.S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu, “An optimal algorithm for approximate nearest neighbor searching in fixed dimensions,” J. ACM, vol. 45, no. 6, pp. 891–923, 1998.
12.J. S. Beis and D. G. Lowe, “Shape indexing using approximate nearest-neighbour search in high-dimensional spaces,” in Proc. IEEE Conf. Comput. Vis. Pattern Recog., 1997, pp. 1000–1006.
13.C. Silpa-Anan and R. Hartley, “Optimised KD-trees for fast image descriptor matching,” in Proc. IEEE Conf. Comput. Vis. Pattern Recog., 2008, pp. 1–8.
14.M. Muja and D.G. Lowe, “Fast approximate nearest neighbors with automatic algorithm configuration,” in Proc. Int. Conf. Computer Vis. Theory Appl., 2009, pp. 331–340.
15.R. F. Sproull, “Refinements to nearest-neighbor searching in k-dimensional trees,” Algorithmica, vol. 6, no. 1, pp. 579–589, 1991.
16.S. Dasgupta and Y. Freund, “Random projection trees and low dimensional manifolds,” in Proc. 40th Annu. ACM Symp. Theory Comput., 2008, pp. 537–546.
17.Y. Jia, J. Wang, G. Zeng, H. Zha, and X. S. Hua, “Optimizing kd-trees for scalable visual descriptor indexing,” in Proc. IEEE Conf. Comput. Vis. Pattern Recog., 2010, pp. 3392–3399.
18.K. Fukunaga and P. M. Narendra, “A branch and bound algorithm for computing k-nearest neighbors,” IEEE Trans. Comput., vol. C-24, no. 7, pp. 750–753, Jul. 1975.
19.S. Brin, “Near neighbor search in large metric spaces,” in Proc. 21th Int. Conf. Very Large Data Bases, 1995, pp. 574–584.
20.A. W. Moore, “The anchors hierarchy: Using the triangle inequality to survive high dimensional data,” in Proc. 16th Conf. Uncertainity Artif. Intell., 2000, pp. 397–405.
21.P. N. Yianilos, “Data structures and algorithms for nearest neighbor search in general metric spaces,” in Proc. ACM-SIAM Symp. Discrete Algorithms, 1993, pp. 311–321.
22.A. Beygelzimer, S. Kakade, and J. Langford, “Cover trees for nearest neighbor,” in Proc. 23rd Int. Conf. Mach. Learning, 2006, pp. 97–104.
23.T. Liu, A. Moore, A. Gray, K. Yang,“ An investigation of practical approximate nearest neighbor algorithms,” presented at the Advances in Neural Information Processing Systems, Vancouver, BC, Canada, 2004.
24.D. Nister and H. Stewenius, “Scalable recognition with a vocabulary tree,” in Proc. IEEE Conf. Comput. Vis. Pattern Recog., 2006, pp. 2161–2168.
25.B. Leibe, K. Mikolajczyk, and B. Schiele, “Efficient clustering and matching for object class recognition,” in Proc. British Mach. Vis. Conf., 2006, pp. 789–798.
26.G. Schindler, M. Brown, and R. Szeliski, “City-Scale location recognition,” in Proc. IEEE Conf. Comput. Vis. Pattern Recog., 2007, pp. 1–7.
27.H. Jegou, M. Douze, and C. Schmid, “Product quantization for nearest neighbor search,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 32, no. 1, pp. 1–15, Jan. 2010.
28.A. Babenko and V. Lempitsky, “The inverted multi-index,” in Proc. IEEE Conf. Comput. Vis. Pattern Recog., 2012, pp. 3069–3076.
29.A. Andoni and P. Indyk, “Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions,” Commun. ACM, vol. 51, no. 1, pp. 117–122, 2008.
30.Q. Lv, W. Josephson, Z. Wang, M. Charikar, and K. Li, “Multi-probe LSH: Efficient indexing for high-dimensional similarity search,” in Proc. Int. Conf. Very Large Data Bases, 2007, pp. 950–961.
31.M. Bawa, T. Condie, and P. Ganesan, “LSH forest: Self-tuning indexes for similarity search,” in Proc. 14th Int. Conf. World Wide Web, 2005, pp. 651–660.
32.Y. Weiss, A. Torralba, and R. Fergus, “Spectral hashing,” in Proc. Adv. Neural Inf. Process. Syst., 2008, p. 6.
33.P. Jain, B. Kulis, and K. Grauman, “Fast image search for learned metrics,” in Proc. IEEE Conf. Comput. Vis. Pattern Recog., 2008, pp. 1–8.
34.B. Kulis and K. Grauman, “Kernelized locality-sensitive hashing for scalable image search,” in Proc. IEEE 12th Int. Conf. Comput. Vis., 2009, pp. 2130–2137.
35.B. Kulis and T. Darrell, “Learning to hash with binary reconstructive embeddings,” in Proc. 23rd Adv. Neural Inf. Process. Syst., 2009, vol. 22, pp. 1042–1050.
36.M. Raginsky and S. Lazebnik, “Locality-sensitive binary codes from shift-invariant kernels,” in Proc. Adv. Neural Inf. Process. Syst., 2009, vol. 22, pp. 1509–1517.
37.J. Wang, S. Kumar, and S. F. Chang, “Semi-supervised hashing for scalable image retrieval,” in Proc. IEEE Conf. Comput. Vis. Pattern Recog., 2010, pp. 3424–3431.
38.J. He, W. Liu, and S. F. Chang, “Scalable similarity search with optimized kernel hashing,” in Proc. Int. Conf. Knowledge Discovery Data Mining, 2010, pp. 1129–1138.
39.H. Xu, J. Wang, Z. Li, G. Zeng, S. Li, and N. Yu, “Complementary hashing for approximate nearest neighbor search,” in Proc. IEEE Int. Conf. Comput. Vis., 2011, pp. 1631–1638.
40.T. B. Sebastian and B. B. Kimia, “Metric-based shape retrieval in large databases,” in Proc. IEEE Conf. Comput. Vis. Pattern Recog., 2002, vol. 3, pp. 291–296.
41.K. Hajebi, Y. Abbasi-Yadkori, H. Shahbazi, and H. Zhang, “Fast approximate nearest-neighbor search with k-nearest neighbor graph,” in Proc. 22nd Int. Joint Conf. Artif. Intell., 2011, pp. 1312–1317.
42.J. Wang, J. Wang, G. Zeng, Z. Tu, R. Gan, and S. Li, “Scalable k-NN graph construction for visual descriptors,” in Proc. IEEE Conf. Comput. Vis. Pattern Recog., 2012, pp. 1106–1113.
43.J. A. Nelder and R. Mead, “A simplex method for function minimization,” Comput. J., vol. 7, no. 4, pp. 308–313, 1965.
44.F. Hutter, “Automated configuration of algorithms for solving hard computational problems,” Ph.D. dissertation, Comput. Sci. Dept., Univ. British Columbia, Vancouver, BC, Canada, 2009.
45.F. Hutter, H. H. Hoos, and K. Leyton-Brown, “ParamILS: An automatic algorithm configuration framework,” J. Artif. Intell. Res., vol. 36, pp. 267–306, 2009.
46.J. Bergstra and Y. Bengio, “Random search for hyper-parameter optimization,” J. Mach. Learn. Res., vol. 13, pp. 281–305, 2012.
47.M. Muja, “Scalable nearest neighbour methods for high dimensional data,” Ph.D. dissertation, Comput. Sci. Dept., Univ. British Columbia, Vancouver, BC, Canada, 2013.
48.D. Arthur and S. Vassilvitskii, “K-Means++: The advantages of careful seeding,” in Proc. Symp. Discrete Algorithms, 2007, pp. 1027–1035.
49.M. Calonder, V. Lepetit, C. Strecha, and P. Fua, “BRIEF: Binary robust independent elementary features,” in Proc. 11th Eur. Conf. Comput. Vis., 2010, pp. 778–792.
50.E. Rublee, V. Rabaud, K. Konolige, and G. Bradski, “ORB: An efficient alternative to SIFT or SURF,” in Proc. IEEE Int. Conf. Comput. Vis., Barcelona, Spain, 2011, pp. 2564–2571.
51.S. Leutenegger, M. Chli, and R. Siegwart, “BRISK: Binary robust invariant scalable keypoints,” in Proc. IEEE Int. Conf. Comput. Vis., 2011, pp. 2548–2555.
52.M. Muja and D. G. Lowe, “Fast matching of binary features,” in Proc. 9th Conf. Comput. Robot Vis., 2012, pp. 404–410.
53.S. Winder and M. Brown, “Learning local image descriptors,” in Proc. IEEE Conf. Comput. Vis. Pattern Recog., 2007, pp. 1–8.
54.K. Mikolajczyk and J. Matas, “Improving descriptors for fast tree matching by optimal linear projection,” in Proc. IEEE 11th Int. Conf. Comput. Vis., 2007, pp. 1–8.
55.J. Hays and A. A. Efros, “IM2GPS: Estimating geographic information from a single image,” in Proc. IEEE Conf. Comput. Vis. Pattern Recog., 2008, pp. 1–8.
56.A. Halevy, P. Norvig, and F. Pereira, “The unreasonable effectiveness of data,” IEEE Intell. Syst., vol. 24, no. 2, pp. 8–12, Mar./Apr. 2009.
57.A. Torralba, R. Fergus, and Y. Weiss, “Small codes and large image databases for recognition,” in Proc. IEEE Conf. Comput. Vis. Pattern Recog., 2008, pp. 1–8.
58.M. Aly, M. Munich, and P. Perona, “Distributed Kd-trees for retrieval from very large image collections,” presented at the British Mach. Vis. Conf., DuDundee, U.K., 2011.
59.M. Muja and D. G. Lowe, “FLANN: Fast library for approximate nearest neighbors,” [Online]. Available: http://www.cs.ubc.ca/research/flann
60.M. Cummins and P. Newman, “Highly scalable appearance-only SLAM-FAB-MAP 2.0,” presented at the Robotics: Science and Systems Conf., vol. 5, Seattle, Washington, USA, 2009.
61.M. Havlena, A. Torii, M. Jancosek, and T. Pajdla, “Automatic reconstruction of Mars artifacts,” in Proc. Eur. Planet. Sci. Congress, 2009, p. 280.
62.M. Havlena, A. Torii, J. Knopp, and T. Pajdla, “Randomized structure from motion based on atomic 3D models from camera triplets,” in Proc. IEEE Conf. Comput. Vis. Pattern Recog., 2009, pp. 2874–2881.
63.M. Quigley, K. Conley, B. Gerkey, J. Faust, T. B. Foote, J. Leibs, R. Wheeler, and A.Y. Ng, “ROS: An open-source robot operating system,” in Proc. ICRA Open-Source Softw. Workshop, 2009.
64.P. Turcot and D.G. Lowe, “Better matching with fewer features: The selection of useful features in large database recognition problems,” in Proc. Comput. Vis. Workshops, 2009, pp. 2109–2116.
65.G. Bradski and A. Kaehler, Learning OpenCV: Comput. Vision with the OpenCV Library. Sebastopol, CA, USA: O’Reilly Media, 2008.

Citation

MLA

Muja, M., and D. G. Lowe. “Scalable Nearest Neighbor Algorithms for High Dimensional Data”. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 36, no. 11, 2014, pp. 2227–40, https://doi.org/10.1109/TPAMI.2014.2321376.

APA

Muja, M., & Lowe, D. G. (2014). Scalable Nearest Neighbor Algorithms for High Dimensional Data. IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(11), 2227–2240. https://doi.org/10.1109/TPAMI.2014.2321376

Chicago

Muja, M., and D. G. Lowe. 2014. “Scalable Nearest Neighbor Algorithms for High Dimensional Data”. IEEE Transactions on Pattern Analysis and Machine Intelligence 36 (11): 2227–40. https://doi.org/10.1109/TPAMI.2014.2321376.

Harvard

Muja, M. and Lowe, D.G. (2014) “Scalable Nearest Neighbor Algorithms for High Dimensional Data”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(11), pp. 2227–2240. Available at: https://doi.org/10.1109/TPAMI.2014.2321376.

Vancouver

1. Muja M, Lowe DG (2014) Scalable Nearest Neighbor Algorithms for High Dimensional Data. IEEE Transactions on Pattern Analysis and Machine Intelligence 36:2227–2240

BibTeX

@article{Muja_2014, title={Scalable Nearest Neighbor Algorithms for High Dimensional Data}, volume={36}, ISSN={2160-9292}, url={http://dx.doi.org/10.1109/TPAMI.2014.2321376}, DOI={10.1109/tpami.2014.2321376}, number={11}, journal={IEEE Transactions on Pattern Analysis and Machine Intelligence}, publisher={Institute of Electrical and Electronics Engineers (IEEE)}, author={Muja, Marius and Lowe, David G.}, year={2014}, month=Nov, pages={2227–2240} }

Metadata:Crossref

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Scalable Nearest Neighbor Algorithms for High Dimensional Data

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Priority Search K-Means Tree Algorithm

Knowl 2 — Randomized k-d Forest Algorithm

Knowl 3 — Hierarchical Clustering Forest for Binary Descriptors

Knowl 4 — Time Complexity of Priority Search K-Means Tree

Knowl 5 — Cost Metric and Automatic Parameter Optimization for Approximate NN Search

Knowl 6 — Distributed Nearest Neighbor Search via MPI Partitioning

Knowl 7 — Empirical Parameter Configurations Selected by Auto-Tuning on SIFT Features

Knowl 8 — Search Efficiency: Space Partitioning vs. LSH and Single k-d Trees

Knowl 9 — Effect of Intrinsic Dimensionality and Data Correlation on Tree Search Speedup

Knowl 10 — Memory Bus Saturation in Multi-Core Approximate Nearest Neighbor Search

References

Citation

BibTeX

Source Code

Access the Paper