# Fast Exact Nearest Neighbour Matching in High Dimensions Usingd-D Sort

Authors: Ruan Lakemond; Clinton Fookes; Sridha Sridharan
Journal: ISRN Machine Vision
 (2013)

---

## Abstract

Data structures such ask-D trees and hierarchical k-means trees perform very well in approximate k nearest neighbour matching, but are only marginally more effective than linear search when performing exact matching in high-dimensional image descriptor data. This paper presents several improvements to linear search that allows it to outperform existing methods and recommends two approaches to exact matching. The first method reduces the number of operations by evaluating the distance measure in order of significance of the query dimensions and terminating when the partial distance exceeds the search threshold. This method does not require preprocessing and significantly outperforms existing methods. The second method improves query speed further by presorting the data using a data structure called d-D sort. The order information is used as a priority queue to reduce the time taken to find the exact match and to restrict the range of data searched. Construction of the d-D sort structure is very simple to implement, does not require any parameter tuning, and requires significantly less time than the best-performing tree structure, and data can be added to the structure relatively efficiently.


---

## Body

## 1. Introduction

Thek nearest neighbour matching (kNN) problem is encountered in many applications of computer science. It is the problem of finding the k points in a database nearest to a given query point. The complexity of a simple linear search is proportional to dn, where n is the number of database entries and d is the number of data dimensions. Many attempts have been made to reduce the search time by implementing data storage and indexing structures so that the minimum number of data points has to be compared to the query point. Unfortunately, these methods are only effective in low dimensions or when using approximate nearest neighbour matching [1, 2]. Where an exact solution is required in dimensions greater than 20, linear search is only a fraction slower than the best existing search structure.This paper proposes methods for improving the performance of linear search for the purpose of exact nearest neighbour matching using typical visual descriptors, such as the scale invariant feature transform (SIFT) [3, 4]. Many modern visual descriptors, such as gradient location and orientation histogram (GLOH) [5], are based on SIFT and have very similar characteristics from a search perspective. First, it is shown that simple modifications to the linear algorithm can allow it to outperform all existing search structures, without the need for any data preprocessing. Secondly, by presorting the data it is possible to reduce search time further. A multidimensional sorting data structure called d-D Sort is introduced that is trivially simple to construct, does not require any parameter tuning, and supports an efficient data addition operation. Thirdly, intersecting the search sphere with the data unit sphere is used to reduce the search space.The proposed methods are compared to leading methods based onk-D trees and k-means trees [1, 2]. A set of SIFT descriptors were extracted from the MIRFLICKR-1 M image collection [6] for this purpose. Two approaches are recommended based on the results. The first requires no preprocessing and significantly outperforms leading tree structures that require a large amount of preprocessing. The second improves results further at the cost of additional memory and preprocessing. Which method is best depends on the application.


## 2. Related Work

The most popular indexing and search methods are based onk-D trees [7] and hierarchical k-means trees [8, 9]. Due to the so-called curse of dimensionality [10], these methods become less effective as the data dimensionality increases. In the exact matching case, linear search is the best method for data with more than 20 dimensions. In many applications, such as where feature vocabularies are used instead of original features [11], an exact match is not essential. Many methods have been proposed to reduce computation time by finding approximate matches.A probabilistic best-bin-first search algorithm fork-D trees was proposed in [12], where the total number of data points evaluated is fixed to limit computation time. This method does not enforce explicit bounds on the accuracy of the result. In [1] a method is proposed which ensures that, given tolerance ϵ, the distance between a query and a selected nearest neighbour is within a factor (1+ϵ) of the distance between the query and the true nearest neighbour. The construction process does not depend on ϵ. A priority queue search is used, where the priority is determined by the distance of cells in the tree from the query point. Cells further than dist(q,p)/(1+ϵ) are not evaluated, where q is the query and p is the current kth neighbour. These best-bin-first and approximate matching methods can also be applied to k-means trees in a very similar fashion.Whilek-D trees and hierarchical k-means trees on average yield similar results, their relative performance depends on the data and type of search query. A procedure for selecting between these algorithms and automatically tuning their parameters is presented in [2]. This procedure constructs a set of sample structures with various parameters from a subset of the data. The parameters of the best performing structure are then used to build the complete data structure. The construction time can be significantly increased by the parameter selection process.More recently, locality sensitive hashing (LSH) has become a very popular approach to approximate matching. Hashing functions are used to map high-dimensional vectors to buckets. The hashing functions are designed to maximise the likelihood that similar descriptors are mapped to the same bucket. The query point is also hashed multiple times to select target buckets. The descriptors in the target buckets are then compared to the query using the original descriptors in a post-verification stage. The choice of hashing functions needs to be made with the aid of training data that is very similar to the final application data. This method is highly effective for approximate matching, but a large number of buckets need to be selected to ensure that the exact match is found, leading to unremarkable performance in exact matching [13, 14].This paper focuses on the exact matching case, where the true nearest neighbour is required. Systems based onk-D trees and k-means trees support guaranteed exact search, but at best outperform linear search by only a fraction. Instead of modifying these structures, this paper investigates methods for improving linear search and shows that it can outperform the above methods.


## 3. Improved Linear Search

The objective of visual descriptor extraction is usually to capture some structure. Consequently, the elements of the resulting descriptor vector are not uniformly distributed, but exhibit some structure as well. Additionally, these feature vectors are frequently normalised to have unit length and only have positive values. Figure1 shows the distribution of descriptor element values for a 128-dimensional SIFT descriptor computed from a large set of maximally stable extremal region (MSER) features [15], extracted from a natural scene. It can be seen that this distribution is approximately exponential. For an evenly distributed unit vector descriptor, one would expect the median value to be near d-1/2; however, only 15% of the elements of the SIFT descriptor are above this value. It can therefore be said that most descriptors consist of a small set of relatively large values and a majority of small values (and often many zeros). Since the larger values of any descriptor are both rare and responsible for the majority of the distance between unit vector descriptors, it is possible to evaluate a large component of the distance by considering only a small number of dimensions.Figure 1
Distribution of descriptor element values for a 128-dimensional SIFT descriptor computed from a large set of MSER features.


### 3.1. Partial Distance Evaluation

While the exact distance between a query descriptor and the nearestk descriptors is usually of interest, the distance to other descriptors is not, except to determine that all other descriptors are more distant than the kth descriptor. Evaluation of the distance measure can therefore be aborted once it exceeds the distance to the current best candidate for descriptor k (used as a threshold). In the case of normalised vectors, the number of evaluated dimensions can be further reduced by evaluating the distance measure in order of the significance of the query dimensions. This does not generalise to unnormalised, uniformly distributed data. While partial distances have been used before [16], the computation in order of significance is novel. All that is required for ordered partial distance computation is to find the order of significance of the query dimensions. This can be done using a sorting operation in O(dlog(d)) time.The effectiveness of this method depends on how long it takes the search algorithm to encounter the nearest neighbour. At the start of the search, a relatively large search threshold is used (tight search thresholds have been shown to be ineffective [4]), resulting in complete distance computation for at least the first descriptor. As descriptors closer to the query are encountered, the search threshold is decreased and the partial evaluation becomes more effective.Implementing the above improvements is trivial and requires only the following three modifications.(1)
Sort the query dimensions according to significance.(2)
Modify the distance function so that the distance measure is computed in order of query dimension significance.(3)
The distance function should terminate as soon as the partially computed distance exceeds a threshold.


### 3.2. Searching on Sorted Arrays

Presorting the data according to one of the dimensions can be used to improve performance in two ways. Firstly, the sorted dimension can be used as a search priority queue. Bilinear search can be used to find a starting point that is close to the query point in at least one dimension, from where the search progresses outwards. If the sorted dimension is one of the more significant query dimensions, then the linear search is more likely to encounter the nearest neighbour early in the search, thereby improving the effectiveness of partial distance evaluation. The inverse is true if selecting a dimension that is one of the least significant query dimensions (this is demonstrated experimentally in Section5). The best results are achieved by sorting the data on every dimension and by selecting the order associated with the query’s dominant dimension.Secondly, the sorted dimension can be used to restrict the search range. A naive approach to defining the search limits would be to simply search in the range[qj-r,qj+r], where q is the query, r is the current search threshold (distance to kth nearest neighbour), and j is the query’s dominant dimension. This is equivalent to stopping the search when the ordered partial distance exceeds the threshold on the first dimension. Because the data is normalised to unit vectors, much tighter constraints are possible. The search limits on qj are set to the minimum and maximum values that satisfy the intersection of the data unit hypersphere and the search radius hypersphere.The data space can be defined as(1)x∈ℝd,xi=x{i}∈[0,1],x⊤x=1.The boundary,b∈x, of the search space around query point q∈x additionally satisfies the constraint:
(2)(b-q)⊤(b-q)=r2,∴b⊤q=1-r22.Letb=p+s, where p=q1-r2/2 is the component of b parallel to q and s is the orthogonal component such that s⊤q=s⊤p=0. The length of s is found as
(3)b⊤b=1(s+p)⊤(s+p)=1,s⊤s+2s⊤p+p⊤p=1,s⊤s=r22.In order to maximisebj, choose s so that |bi| is minimised for all i≠j, that is, si∝-qi. Add scale factor a to correct the length and select sj to satisfy the orthogonality constraint:
(4)si=-aqi,∀i≠j,s⊤q=sjqj-a∑∀i≠jqi2=0,∴sj=a∑∀i≠jqi2qj.
Let c=∑∀i≠j‍qi2 and solve for a using the known length of s:
(5)sj=acqj,s⊤s=sj2+∑∀i≠j‍si2,r22=a2c2qj2+a2c,a2=r22(c2/qj2+c),∴sj=rcqj2(c2/qj2+c)=rg.Similarly,bj can be minimised, resulting in sj=-rg. Note that g depends only on q and can be computed once per query.The above equations only findb with minimum or maximum value of bj if the search area is not bounded by one of the coordinate axes. If the j-axis intersects the search area, then the maximum value of bj is 1, and if any other axis intersects the search area, then the minimum value of bj is 0. Let ru be the distance between q and the unit vector along dimension j, and let rl be the distance between q and the unit vector along the minimum dimension of q. The upper and lower search limits along dimension j are then,
(6)tu={qj1-r22+rg,r<ru,1,r≥ru,tl={qj1-r22-rg,r<rl,0,r≥rl.


## 3.1. Partial Distance Evaluation

While the exact distance between a query descriptor and the nearestk descriptors is usually of interest, the distance to other descriptors is not, except to determine that all other descriptors are more distant than the kth descriptor. Evaluation of the distance measure can therefore be aborted once it exceeds the distance to the current best candidate for descriptor k (used as a threshold). In the case of normalised vectors, the number of evaluated dimensions can be further reduced by evaluating the distance measure in order of the significance of the query dimensions. This does not generalise to unnormalised, uniformly distributed data. While partial distances have been used before [16], the computation in order of significance is novel. All that is required for ordered partial distance computation is to find the order of significance of the query dimensions. This can be done using a sorting operation in O(dlog(d)) time.The effectiveness of this method depends on how long it takes the search algorithm to encounter the nearest neighbour. At the start of the search, a relatively large search threshold is used (tight search thresholds have been shown to be ineffective [4]), resulting in complete distance computation for at least the first descriptor. As descriptors closer to the query are encountered, the search threshold is decreased and the partial evaluation becomes more effective.Implementing the above improvements is trivial and requires only the following three modifications.(1)
Sort the query dimensions according to significance.(2)
Modify the distance function so that the distance measure is computed in order of query dimension significance.(3)
The distance function should terminate as soon as the partially computed distance exceeds a threshold.


## 3.2. Searching on Sorted Arrays

Presorting the data according to one of the dimensions can be used to improve performance in two ways. Firstly, the sorted dimension can be used as a search priority queue. Bilinear search can be used to find a starting point that is close to the query point in at least one dimension, from where the search progresses outwards. If the sorted dimension is one of the more significant query dimensions, then the linear search is more likely to encounter the nearest neighbour early in the search, thereby improving the effectiveness of partial distance evaluation. The inverse is true if selecting a dimension that is one of the least significant query dimensions (this is demonstrated experimentally in Section5). The best results are achieved by sorting the data on every dimension and by selecting the order associated with the query’s dominant dimension.Secondly, the sorted dimension can be used to restrict the search range. A naive approach to defining the search limits would be to simply search in the range[qj-r,qj+r], where q is the query, r is the current search threshold (distance to kth nearest neighbour), and j is the query’s dominant dimension. This is equivalent to stopping the search when the ordered partial distance exceeds the threshold on the first dimension. Because the data is normalised to unit vectors, much tighter constraints are possible. The search limits on qj are set to the minimum and maximum values that satisfy the intersection of the data unit hypersphere and the search radius hypersphere.The data space can be defined as(1)x∈ℝd,xi=x{i}∈[0,1],x⊤x=1.The boundary,b∈x, of the search space around query point q∈x additionally satisfies the constraint:
(2)(b-q)⊤(b-q)=r2,∴b⊤q=1-r22.Letb=p+s, where p=q1-r2/2 is the component of b parallel to q and s is the orthogonal component such that s⊤q=s⊤p=0. The length of s is found as
(3)b⊤b=1(s+p)⊤(s+p)=1,s⊤s+2s⊤p+p⊤p=1,s⊤s=r22.In order to maximisebj, choose s so that |bi| is minimised for all i≠j, that is, si∝-qi. Add scale factor a to correct the length and select sj to satisfy the orthogonality constraint:
(4)si=-aqi,∀i≠j,s⊤q=sjqj-a∑∀i≠jqi2=0,∴sj=a∑∀i≠jqi2qj.
Let c=∑∀i≠j‍qi2 and solve for a using the known length of s:
(5)sj=acqj,s⊤s=sj2+∑∀i≠j‍si2,r22=a2c2qj2+a2c,a2=r22(c2/qj2+c),∴sj=rcqj2(c2/qj2+c)=rg.Similarly,bj can be minimised, resulting in sj=-rg. Note that g depends only on q and can be computed once per query.The above equations only findb with minimum or maximum value of bj if the search area is not bounded by one of the coordinate axes. If the j-axis intersects the search area, then the maximum value of bj is 1, and if any other axis intersects the search area, then the minimum value of bj is 0. Let ru be the distance between q and the unit vector along dimension j, and let rl be the distance between q and the unit vector along the minimum dimension of q. The upper and lower search limits along dimension j are then,
(6)tu={qj1-r22+rg,r<ru,1,r≥ru,tl={qj1-r22-rg,r<rl,0,r≥rl.


## 4. Thed-D Sort System

A search structure namedd-D sort is used to implement the sorted linear search improvements presented in the previous section.


### 4.1. Construction

Thed-D Sort structure consist of d index arrays, o={o1,o2,…,od}, with each oi={oi1,oi2,…,oin} indexing the descriptor data, x, in order of dimension i. It requires nd memory in addition to the data. Construction is extremely simple; sort the descriptor data according to each dimension and write the result in o (instead of actually reordering the data), requiring O(dnlog(n)) time.


### 4.2. Adding Data

Adding additional data to thed-D Sort structure is relatively simple as well. The new data, x′, is appended to the existing data, x′′={x,x′}. The ordering arrays are updated by finding the position of the new data. This can be achieved efficiently using binary search in O(dlog(n)) time and array insertion operations in linear time. For a large batch of new descriptors, a more efficient solution is to sort the new data first (O(dn′logn′) time) and then merge the result with the existing order arrays (O(d(n+n′)) time), rather than performing multiple separate insertions. This addition operation is faster than a complete reconstruction where the new data contains fewer descriptors than the existing data.


### 4.3. Queries

All matching queries are variants of ak nearest neighbours (kNNs) query with a maximum distance threshold. The algorithm is listed in Algorithm 1.Algorithm 1:
kNN Query Algorithm for the d-D Sort Structure.
Input: x, o, q, k, r, ϵ
Output: nr, ir, er
(1.1)begin
(1.2)  Sort query,q in ascending order, yielding order array oq.
(1.3)  Select prime dimension,j←oq{d}.
(1.4)  Select data order vectoroj=o{j}    as the search order.
(1.5)  Computeru  and  rl.
(1.6)  Computeg according to (5).
(1.7)  Compute initial search range,[tu,tl], according to (6).
(1.8)  Use binary search to findi0←argimin|x{oj{i}}{j}-qj|.
(1.9)foreach  i∈[1,n] in order of increasing distance from i0   do
(1.10) If  x{oj{i}}{j}  is out of search range [tu,tl], terminate.
(1.11) Compute distance e = dist (x{oj{i}},q)  using the ordered partial distance method.
(1.12) if  e<r  then
(1.13)  Insert  i, e in results list, ir, er.
(1.14)  Increment nr (up to k).
(1.15)  if  nr=k  then
(1.16)   Reduce the search range, r←ek/(1+ϵ).
(1.17)   Recompute [tu,tl] according to (6).
(1.18)  end
(1.19) end
(1.20)end
(1.21)endOther types of queries are essentially specialisations of the above algorithm. KNN without a threshold is achieved by settingr to a very large initial value. Nearest neighbour ratio matching [4] is equivalent to 1NN matching with the additional requirement that no second match is found in the radius (1+δ)er{1}. In this case r is updated as r←(1+δ)e in line (1.16), and the final match is invalidated if any second nearest neighbour is found to be within r.Two possible methods can be applied to further speed up the query process while sacrificing exact results. Firstly, the number of descriptors visited can be limited. It is possible to compute the worst case accuracy of this approach for each individual query, but it is not possible to enforce a lower accuracy bound on all queries. Alternatively, the distance threshold can be reduced according to an accuracy requirement, to reduce the number of descriptors visited. The convention used in [1] for describing approximation tolerance is used: given tolerance ϵ, the distance between a query and a selected nearest neighbour must be within a factor (1+ϵ) of the distance between the query and the true nearest neighbour. This is implemented in the d-D Sort query algorithm in line (1.16). As is shown in the experimental evaluation, this method can reduce search time, but the search accuracy degrades more rapidly than with other search structures.The computation time of the query operation is highly dependant on the data distribution. Sorting the query requiresO(dlog(d)) operations and the initial binary search requires O(log(n)) operations. Searching for k exact matches requires at best Ω(kd) operations and at worst O(nd) operations (requiring an invalid query q=0 or data spherically symmetric around q). In practice, the total number of data points visited is much smaller than n, and much fewer than d dimensions are evaluated for most visited points.


## 4.1. Construction

Thed-D Sort structure consist of d index arrays, o={o1,o2,…,od}, with each oi={oi1,oi2,…,oin} indexing the descriptor data, x, in order of dimension i. It requires nd memory in addition to the data. Construction is extremely simple; sort the descriptor data according to each dimension and write the result in o (instead of actually reordering the data), requiring O(dnlog(n)) time.


## 4.2. Adding Data

Adding additional data to thed-D Sort structure is relatively simple as well. The new data, x′, is appended to the existing data, x′′={x,x′}. The ordering arrays are updated by finding the position of the new data. This can be achieved efficiently using binary search in O(dlog(n)) time and array insertion operations in linear time. For a large batch of new descriptors, a more efficient solution is to sort the new data first (O(dn′logn′) time) and then merge the result with the existing order arrays (O(d(n+n′)) time), rather than performing multiple separate insertions. This addition operation is faster than a complete reconstruction where the new data contains fewer descriptors than the existing data.


## 4.3. Queries

All matching queries are variants of ak nearest neighbours (kNNs) query with a maximum distance threshold. The algorithm is listed in Algorithm 1.Algorithm 1:
kNN Query Algorithm for the d-D Sort Structure.
Input: x, o, q, k, r, ϵ
Output: nr, ir, er
(1.1)begin
(1.2)  Sort query,q in ascending order, yielding order array oq.
(1.3)  Select prime dimension,j←oq{d}.
(1.4)  Select data order vectoroj=o{j}    as the search order.
(1.5)  Computeru  and  rl.
(1.6)  Computeg according to (5).
(1.7)  Compute initial search range,[tu,tl], according to (6).
(1.8)  Use binary search to findi0←argimin|x{oj{i}}{j}-qj|.
(1.9)foreach  i∈[1,n] in order of increasing distance from i0   do
(1.10) If  x{oj{i}}{j}  is out of search range [tu,tl], terminate.
(1.11) Compute distance e = dist (x{oj{i}},q)  using the ordered partial distance method.
(1.12) if  e<r  then
(1.13)  Insert  i, e in results list, ir, er.
(1.14)  Increment nr (up to k).
(1.15)  if  nr=k  then
(1.16)   Reduce the search range, r←ek/(1+ϵ).
(1.17)   Recompute [tu,tl] according to (6).
(1.18)  end
(1.19) end
(1.20)end
(1.21)endOther types of queries are essentially specialisations of the above algorithm. KNN without a threshold is achieved by settingr to a very large initial value. Nearest neighbour ratio matching [4] is equivalent to 1NN matching with the additional requirement that no second match is found in the radius (1+δ)er{1}. In this case r is updated as r←(1+δ)e in line (1.16), and the final match is invalidated if any second nearest neighbour is found to be within r.Two possible methods can be applied to further speed up the query process while sacrificing exact results. Firstly, the number of descriptors visited can be limited. It is possible to compute the worst case accuracy of this approach for each individual query, but it is not possible to enforce a lower accuracy bound on all queries. Alternatively, the distance threshold can be reduced according to an accuracy requirement, to reduce the number of descriptors visited. The convention used in [1] for describing approximation tolerance is used: given tolerance ϵ, the distance between a query and a selected nearest neighbour must be within a factor (1+ϵ) of the distance between the query and the true nearest neighbour. This is implemented in the d-D Sort query algorithm in line (1.16). As is shown in the experimental evaluation, this method can reduce search time, but the search accuracy degrades more rapidly than with other search structures.The computation time of the query operation is highly dependant on the data distribution. Sorting the query requiresO(dlog(d)) operations and the initial binary search requires O(log(n)) operations. Searching for k exact matches requires at best Ω(kd) operations and at worst O(nd) operations (requiring an invalid query q=0 or data spherically symmetric around q). In practice, the total number of data points visited is much smaller than n, and much fewer than d dimensions are evaluated for most visited points.


## 5. Experimental Evaluation

The following eight search methods were compared experimentally:(1)
linear search,(2)
linear search using partial distance computation,(3)
linear search using significance ordered partial distance computation,(4)
d-D Sort structured search,(5)
1-D Sort search,(6)
thek-D tree from the approximate nearest neighbor (ANN) library [1],(7)
theb-D tree from the approximate nearest neighbor (ANN) library [1],(8)
the fast library for approximate nearest neighbors (FLANN) [2].Publicly available C/C++ implementations by the original authors were used for ANN and FLANN. The FLANN method was set to use 1000 points in its an automatic parameter selection process. The1-D Sort method sorts the data on the first dimension only. This method is added to the evaluation to demonstrate the importance of using the order of the most significant query dimension as search priority queue.A set of data was generated using a characteristic scale determinant of Hessian feature detector [17, 18] and SIFT descriptor [3, 4] to extract 1 million descriptors from a subset of the MIRFLICKR-1 M image collection [6]. These descriptors are normalised to have an L2 norm of 1 and consists of strictly positive values.Figure2 plots construction times and average query time results for a set of queries produced by extracting features for an image not included in the dataset. This is the most difficult test case, since the queries are rarely very close to any points in the dataset. Query time results are expressed in terms of a relative increase in speed over the time taken to do a simple linear search (tlinear/ttest). Table 1 lists 1NN performance for queries from an image that is not in the database (same as Figure 2(b)), a rotated version of an image that is in the database, and an exact copy of an image in the database.Table 1
1 NN query performance using a 128000-point dataset. Each column shows results for query descriptors extracted from an image related to the data in a different way. Results are presented as the ratio between linear search time and the given method's search time.
Method
Not in database
Rotated copy
Exact copy
ANNb-D tree
0.297
0.292
0.2872
ANNk-D tree
0.503
0.498
0.4909
FLANN
1.450
2.483
23.13
Linear
1.000
1.000
1.000
Linear partial
1.392
2.124
12.62
Linear ordered partial
2.588
4.397
12.62
d-D sort
3.404
7.032
2246.0Results for SIFT descriptor data experiment using euclidean distance. (a) Search structure construction time plots against database size. (b) Exact 1NN query time, normalised according to linear search time, plots against database size. A threshold of 2.0 was used. (c) Exact 1NN query time, normalised according to linear search time, plots against threshold for 100 k descriptor database. (d) Exact query time, normalised according to linear search time, plots against the number of neighbours to find. A 100 k descriptor database and threshold of 2.0 was used. (e) Accuracy of approximate 1NN query plots against query time, normalised according to linear search time. A 100 k descriptor database and threshold of 2.0 were used.
(a)
(b)
(c)
(d)
(e)Data structure construction times are plotted in Figure2(a) for those methods that require preprocessing. The d-D Sort structure construction time is comparable to that of the b-D tree on average, while the construction time increases more slowly than the k-D Tree. FLANN takes the longest to construct due to the simulation process it uses to select parameters. Figure 3 shows the time taken to append 100 descriptors to a d-D Sort structure of increasing size. It can be seen that the addition method is more efficient when adding a relatively small number of points to the database, compared to rebuilding the structure completely.Figure 3
The time required to append 100 SIFT descriptors to ad-D sort structure plot against the number of descriptors already in the structure. The time taken to construct the database anew is included for reference.Figure2(b) plots the relative exact 1NN query performance against the size of the database. A matching threshold of 2.0 was used. It can be seen that using only partial distance computation is sufficient to bring the speed of linear search up to that of the best tree structure method (FLANN). Ordered partial distance adds a further improvement, all without any data preprocessing. The d-D Sort structure achieves the best performance by a significant margin, demonstrating the benefits of presorting the data. In contrast, 1-D Sort performs worse than the ordered partial distance method. This shows that sorting on an arbitrary dimension is not beneficial for all queries and that it is necessary to sort on the query’s most significant dimension.The effect of matching threshold on query performance is examined in Figure2(c). Smaller thresholds reduce the search space and improve matching speed in general. Of the linear methods, the d-D Sort structure is best able to take advantage of smaller thresholds. The k-D Tree and b-D Tree structures benefit the most from smaller thresholds, with k-D Tree surpassing d-D Sort at a relatively small threshold of 0.2.The number of nearest neighbours selected impacts the partial distance computation, since the greater distance to thekth match leads to a greater search threshold. Figure 2(d) plots the query performance against k. A decrease in performance can be seen for d-D Sort and modified linear methods, while the ANN and FLANN methods are unaffected. The linear methods remain the most efficient.Thed-D Sort structure supports approximate matching by reducing the search threshold below what is needed to prove an exact match. Figure 2(b) plots the match accuracy against the relative query performance for approximate nearest neighbour matching. Match accuracy is measured as the proportion of matches returned that are the true matches. It can be seen that approximate matching leads to more than an order of magnitude improvement in performance at the cost of a slight reduction in accuracy. The accuracy of the d-D Sort structure drops more quickly than that of ANN k-D tree or FLANN. While d-D Sort consistently outperforms the other methods in guaranteed exact matching, it is not the best choice for approximate matching.The effect of the similarity between queries and the data is demonstrated by Table1. The first column shows results from an image not in the database, which is the same as one of the points in Figure 2(b). The second column lists results of matching a rotated version of an image in the database and the third column is for an exact copy of a database image. The absolute time performance of linear search is the same for all three cases. The ANN methods perform the same for all three cases as well, which is unexpected. FLANN shows a significant increase in performance. This is the expected behaviour, since the closer true match allows for reduced search space. Both modified linear methods show an improvement in performance, though the improvement is less pronounced than with FLANN. In the exact copy case the modified linear methods practically become equivalent, since any nonzero dimension of the query is sufficient to exclude a potential match after the true nearest neighbour has been found. The d-D Sort method shows the best improvement in performance, with performance more than doubling between the outlier case and the rotated image case. In the exact case, the initial bilinear search always delivers the exact match, resulting in log(n) search time and extremely fast performance. Unfortunately the exact match case does not have many applications. This last result really shows not only that exact matching is possible using a one dimensional feature, but also that d-D Sort is able to take advantage of close similarity.


## 6. Conclusion

Data structures such ask-D trees and hierarchical k-means trees are only marginally more effective than linear search when performing exact k nearest neighbour matching in high-dimensional local image descriptor data. Of these, the best-performing method is the FLANN approach [2], which improves performance by a factor of 2.5 at best, but typically yields an improvement of less than 1.5-fold. At the same time, this data structure requires more than a minute to construct for even small datasets.This paper presents several performance improvements to the linear search method for exactk nearest neighbour matching. It is shown that evaluating the distance measure in order of the significance of query dimensions and terminating when the search threshold is reached can improve linear search time by 1.7–4.4-fold (usually at least 2.6 fold). These modifications are simple to implement and do not require any data preprocessing. Secondly, the d-D sort structure is introduced. This structure essentially presorts the data according to every dimension. No parameter tuning is required and data can be added efficiently. Using the sort order associated with the query’s most significant dimension as a priority queue and to limit the search range improves results further. The d-D Sort-based search showed an improvement over linear search of 2–7-fold (usually at least 3.2-fold), while the preprocessing time can be several orders of magnitude less than that of FLANN. While it is possible to implement approximate nearest neighbour search using the d-D Sort structure, results show that the accuracy of this method decreases more rapidly than that of ANN and FLANN and does not yield the same performance-accuracy ratio.In summary, this paper proposes two approaches for exact nearest neighbour search in normalised high-dimensional descriptor data. The first is the use of partial distance computation in order of significance of the query dimensions. This does not require any data preprocessing and yields best results when preprocessing time would be a significant factor, for example, when matching between a small set of images. The second approach is to use thed-D sort structure and proposed query mechanism, which yield the best query time performance without the need for any parameter tuning. This yields the best performance where the preprocessing time is small compared to the number of queries that will be performed. The d-D Sort structure also supports data addition for problems where the matching database grows progressively.



---

*Source: 405680-2013-02-17.xml*