Probabilistic cost model for nearest neighbor search in image retrieval

Abstract

The nearest neighbor search is one of the most fundamental queries for content-based image retrieval. kd-trees are widely used to accelerate the performance of the nearest neighbor search, and the quality of kdtrees significantly affects the performance of the nearest neighbor search. In order to quantify the quality of kd-trees, we propose a novel, probabilistic cost model that measures the expected number of nodes traversed during the search query. We show that our cost model has high correlations with both the observed number of traversed nodes and the runtime performance of search queries used in image retrieval. Furthermore, we prove that the median-based partitioning method commonly used to construct kd-trees can produce near-optimal kdtrees in terms of minimizing our cost model, under an assumption that the query points follow the distribution of data used to construct the kd-trees. We also show that this assumption is valid in SIFT-based image retrieval.