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.
최근접 이웃 검색은 이미지 기반 이미지 검색 기술에 있어서 가장 중요한 질의 중 하나이다. kd-나무는 최근접 이웃 검색의 성능을 향상시키기 위해 널리 사용되고 있고, kd-나무의 질은 최근접 이웃 검색의 성능에 상당한 영향을 준다. kd-나무의 질을 수량화하기 위하여, 해당 학위 논문에서는 검색 질의를 처리하는 동안 지나가는 노드의 개수의 기대값을 계산하는 새로운 확률적 비용 모델을 제시한다. 또한 본 논문에서 제시한 비용 모델이 실제 지나가는 노드의 개수와 실제 검색 질의 성능과의 상관관계가 매우 높음을 보여준다. 그리고 질의 특징점들이 kd-나무를 만드는데 사용된 특징점들의 분포를 따른다고 가정할 때 중간값 기반으로 kd-나무에서의 각 노드를 분할하는 방법이 제시한 비용 모델에서의 최저값, 즉 최적에 가까운 방법임을 증명하였다. 또한 이 가정이 SIFT 기반 이미지 검색에서의 유효함을 보인다.
