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