Probabilistic cost model for nearest neighbor search in image retrieval

We present a probabilistic cost model to analyze the performance of the kd-tree for nearest neighbor search in the context of content-based image retrieval. Our cost model measures the expected number of kd-tree 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, if the query points follow the distribution of data used to construct the kd-trees, the median-based partitioning method as well as PCA-based partitioning technique can produce near-optimal kd-trees in terms of minimizing our cost model. The probabilistic cost model is validated through experiments in SIFT-based image retrieval.