Optimised KD-trees for fast image descriptor matching

By Chanop Silpa-Anan, Richard I. Hartley. 2008

809 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

How researchers see this paper

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

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

Product Quantization for Nearest Neighbor Search (2011, methodology): “These methods include randomized KD-trees [14] and hierarchical k-means [15], both of which are implemented in the FLANN selection algorithm [9].”
Visualizing Large-scale and High-dimensional Data (2016, methodology): “…2 d ) (with N being the number of data points and d being the number of dimensions) which is too costly, existing approaches use roughly three categories of techniques: space-partitioning trees [3, 10, 21, 7], locality sensitive hashing techniques [8, 6, 12], and neighbor exploring techniques [9].”
High-level event recognition in unconstrained videos (2012, methodology): “This converts the ad hoc event detection task into a nearest neighbor search problem, to which highly efficient hashing techniques [152,156] or indexing methods [126] may be applied to achieve real-time retrieval in large databases.”
Approximate Nearest Neighbor Search by Residual Vector Quantization (2010, neutral): “The state-of-the-art approaches such as tree-based methods (e.g., KD-tree [4], hierarchical k-means (HKM) [5], FLANN [6]) and hash-based methods (e.g., Exact Euclidean Locality-Sensitive Hashing (E2LSH) [7,8]) involve indexing structures to improve the performance.”
Optimized Cartesian K-Means (2014, background): “magnitude speed-ups than exact NN search with near-optimal accuracy [29]. There has been a lot of research interest on designing effective data structures, such as k-d tree [4], randomized k-d forest [30], FLANN [22], trinary-projection tree [11], [39], and neighborhood graph search [1], [35], [37],”
Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph (2017, methodology): “For dense continuous vectors, various solutions have been proposed such as tree-structure based approaches[6, 14, 19, 29], hashing-based approaches[15, 17, 32], quantization-based approaches[16, 20, 34] and graph-based approaches[1, 18, 26, 33].”
Deep Imbalanced Learning for Face Recognition and Attribute Prediction (2018, neutral): “the KD-tree [61] whose runtime is logarithmic in the cluster number (bL=lc) with a complexity of OðL=l log ðL=lÞÞ.”
Milvus: A Purpose-Built Vector Data Management System (2021, background): “Prior works on approximate search can be roughly classified in four categories: LSH-based [23, 23, 24, 32, 40, 44, 45, 48, 73], tree-based [17, 46, 54, 57], graph-based [20, 43, 49, 61, 72], and quantization-based [3, 6, 22, 27, 33, 35].”
k-Nearest Neighbour Classifiers - A Tutorial (2020, background): “the prospect of ﬁnding good neighbours can be improved by repeating with multiple trees. Different variants of the tree can be produced by including a random element in the Kd-Tree generation process [45]. Since there is a risk that there will not be great variety in the Kd-Tree variants, it is comm”
Appearance-only SLAM at large scale with FAB-MAP 2.0 (2011, methodology): “…approximate k-means algorithm discussed in Philbin et al. (2007), where, at the beginning of each k-means iteration, a randomized forest of kdtrees (Silpa-Anan and Hartley 2008; Muja and Lowe 2009) is constructed over the cluster centers, which is then used for fast (approximate) distance…”
Learning Deep Representation for Imbalanced Classification (2016, methodology): “For instance, we utilize the KD-tree [36] whose runtime is logarithmic in the number of all clusters (L/l) with a complexity of O(L/l log(L/l)) in comparison to O(L log L) by sample-wise search.”
Bayesian Optimization with an Empirical Hardness Model for approximate Nearest Neighbour Search (2014, methodology): “FLANN incorporates two algorithms for search: a randomized kd-tree as described in [18] and a hierarchical k-means clustering novel to the FLANN implementation.”
Large Scale Nearest Neighbors Search Based on Neighborhood Graph (2013, methodology): “KD-tree: A KD-tree [9, 10] partitions the space by hyperplanes that are perpendicular to the coordinate axes.”
The MOPED framework: Object recognition and pose estimation for manipulation (2011, background): “1998), randomized kd-trees (Silpa-Anan and Hartley 2008), FLANN (Muja and Lowe 2009)) or hashing (e.”
A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search (2021, methodology): “According to the index adopted, the existing ANNS algorithms can be divided into four major types: hashing-based [40, 45]; tree-based [8, 86]; quantization-based [52, 74]; and graph-based [38, 67] algorithms.”
Highly scalable appearance-only SLAM - FAB-MAP 2.0 (2009, methodology): “Instead we apply the fast approximate k-means algorithm discussed in [14], where, at the beginning of each k-means iteration, a randomized forest of kd-trees [22], [23] is constructed over the cluster centres, which is then used for fast (approximate) distance calculations.”
Fast Neighborhood Graph Search Using Cartesian Concatenation (2013, methodology): “Various trees, such as BD tress [3], metric trees [9, 24, 26, 46], hierarchical k-means tree [28], and randomized KD trees [20, 33, 43], have been proposed.”