Optimized Transform Coding for Approximate KNN Search

Minwoo Park, Kiran Gunda, Himaanshu Gupta and Khurram Shafique

In Proceedings British Machine Vision Conference 2014
http://dx.doi.org/10.5244/C.28.34

Abstract

Transform coding (TC) is an efficient and effective vector quantization approach where the resulting compact representation can be the basis for a more elaborate hierarchical framework for sub-linear approximate search. However, as compared to the state-of-the-art product quantization methods, there is a significant performance gap in terms of matching accuracy. One of the main shortcomings of TC is that the solution for bit allocation relies on an assumption that probability density of each component of the vector can be made identical after normalization. Motivated by this, we propose an optimized transform coding (OTC) such that bit allocation is optimized directly on the binned kernel estimator of each component of the vector. Experiments on public datasets show that our optimized transform coding approach achieves performance comparable to the state-of-the-art product quantization methods, while maintaining speed comparable to TC.

Session

Poster Session

Files

Extended Abstract (PDF, 1 page, 114K)

Paper (PDF, 12 pages, 606K)

Bibtex File

Citation

Minwoo Park, Kiran Gunda, Himaanshu  Gupta, and Khurram Shafique. Optimized Transform Coding for Approximate KNN Search. Proceedings of the British Machine Vision Conference. BMVA Press, September 2014.

BibTex

@inproceedings{BMVC.28.34
	title = {Optimized Transform Coding for Approximate KNN Search},
	author = {Park, Minwoo and Gunda, Kiran and Gupta, Himaanshu and Shafique, Khurram},
	year = {2014},
	booktitle = {Proceedings of the British Machine Vision Conference},
	publisher = {BMVA Press},
	editors = {Valstar, Michel and French, Andrew and Pridmore, Tony}
	doi = { http://dx.doi.org/10.5244/C.28.34 }
}