Adaptive Cluster-Distance Bounding for Nearest Neighbor Search in Image Databases

We consider approaches for exact similarity search in a high dimensional space of correlated features representing image datasets, based on principles of clustering and vector quantization. We develop an adaptive cluster distance bound based on separating hyperplanes, that complements our index in selectively retrieving clusters that contain data entries closest to the query. Experiments conducted on real data-sets confirm the efficiency of our approach with random disk IOs reduced by 100X, as compared with the popular vector approximation-file (VA-File) approach, when allowed (roughly) the same number of sequential disk accesses, with relatively low preprocessing storage and computational costs.