Abstract
The essential contribution of Dynamic Partial Function (DPF) is to effectively quantify the perceptual similarity between images. This method closely models human cognitive activities when scrutinizing two images. However, due to DPF being non-metric and its violation of triangular inequality, most conventional index schemes that require metric-space properties fail to index images based on DPF. As a result, clustering techniques seem to be the only options for efficient, yet approximate retrievals of k nearest neighbors (kNN) to the query image in the Query-by-Example (QBE) paradigm. In this thesis, we introduce a novel technique, Closer, for the exact indexing of DPF. The idea utilizes a metric range function to tightly bound DPF along the traversal of index tree. Unpromising tree branches with their descendants can be efficiently disregarded from further consideration. Only a few surviving candidates are verified with DPF to finalize the kNN query. We show our scheme is correct, and demonstrate Closer can accurately search for true kNN with short delay, even in relevance feedback applications.