K-Means Hashing: An Affinity-Preserving Quantization Method for Learning Binary Compact Codes
Abstract
In computer vision there has been increasing interest in learning hashing codes whose Hamming distance approximates the data similarity. The hashing functions play roles in both quantizing the vector space and generating similarity-preserving codes. Most existing hashing methods use hyper-planes (or kernelized hyper-planes) to quantize and encode. In this paper, we present a hashing method adopting the k-means quantization. We propose a novel Affinity-Preserving K-means algorithm which simultaneously performs k-means clustering and learns the binary indices of the quantized cells. The distance between the cells is approximated by the Hamming distance of the cell indices. We further generalize our algorithm to a product space for learning longer codes. Experiments show our method, named as K-means Hashing (KMH), outperforms various state-of-the-art hashing encoding methods.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Cites
Distinctive Image Features from Scale-Invariant Keypoints
Lowe, D. G. (2004) · International Journal of Computer Vision · doi:10.1023/b:visi.0000029664.99615.94 · Cited by 55,589 · see citing works
(1967) · Cited by 23,719 · see citing works
Video Google: a text retrieval approach to object matching in videos
Sivic, & Zisserman (2003) · Proceedings Ninth IEEE International Conference on Computer Vision · doi:10.1109/iccv.2003.1238663 · Cited by 6,367 · see citing works
Modeling the Shape of the Scene: A Holistic Representation of the Spatial Envelope
Oliva, A., & Torralba, A. B. (2001) · International Journal of Computer Vision · doi:10.1023/a:1011139631724 · Cited by 6,321 · see citing works
Approximate nearest neighbors: towards removing the curse of dimensionality
Indyk, P., & Motwani, R. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276876 · Cited by 4,188 · see citing works
Conditioning of quasi-Newton methods for function minimization
Shanno, D. F. (1970) · Mathematics of Computation · doi:10.1090/s0025-5718-1970-0274029-x · Cited by 3,752 · see citing works
Product Quantization for Nearest Neighbor Search
Jégou, H., Douze, M., & Schmid, C. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2010.57 · Cited by 2,956 · cited 10× · see citing works
“[10] further proposes the Asymmetric Distance Computation (ADC).”
BackgroundMethodInfluentialGray, R. M. (1990) · Readings in Speech Recognition · doi:10.1016/b978-0-08-051584-7.50011-5 · Cited by 2,845 · see citing works
Aggregating local descriptors into a compact image representation
Jeǵou, H., Douze, M., Schmid, C., & Pérez, P. (2010) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2010.5540039 · Cited by 2,679 · see citing works
Weiss, Y., Torralba, A. B., & Fergus, R. (2008) · neural information processing systems · Cited by 2,389 · see citing works
80 Million Tiny Images: A Large Data Set for Nonparametric Object and Scene Recognition
Torralba, A., Fergus, R., & Freeman, W. T. (2008) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2008.128 · Cited by 1,921 · see citing works
Fisher Kernels on Visual Vocabularies for Image Categorization
Perronnin, F., & Dance, C. (2007) · 2007 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2007.383266 · Cited by 1,641 · see citing works
Supervised hashing with kernels
Liu, W., Wang, J., Ji, R., Jiang, Y., & Chang, S. (2012) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2012.6247912 · Cited by 1,418 · see citing works
Iterative quantization: A procrustean approach to learning binary codes
Gong, Y., & Lazebnik, S. (2011) · doi:10.1109/cvpr.2011.5995432 · Cited by 1,089 · see citing works
In defense of Nearest-Neighbor based image classification
Boiman, O., Shechtman, E., & Irani, M. (2008) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2008.4587598 · Cited by 1,079 · see citing works
Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions
Andoni, A., & Indyk, P. (2006) · 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) · doi:10.1109/focs.2006.49 · Cited by 1,067 · see citing works
Kernelized locality-sensitive hashing for scalable image search
Kulis, B., & Grauman, K. L. (2009) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2009.5459466 · Cited by 905 · see citing works
Learning to Hash with Binary Reconstructive Embeddings
Kulis, B., & Darrell, T. (2009) · Cited by 806 · see citing works
Minimal Loss Hashing for Compact Binary Codes
Norouzi, M., & Blei, D. M. (2011) · Cited by 695 · see citing works
Semi-supervised hashing for scalable image retrieval
Wang, J., Kumar, S., & Chang, S. (2010) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2010.5539994 · Cited by 623 · see citing works
Nearest-Neighbor Methods in Learning and Vision
(2006) · The MIT Press eBooks · doi:10.7551/mitpress/4908.001.0001 · Cited by 442 · see citing works
Optimized Product Quantization for Approximate Nearest Neighbor Search
Ge, T., He, K., Ke, Q., & Sun, J. Z. (2013) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2013.379 · Cited by 401 · see citing works
Self-citationNearest-neighbor methods in learning and vision : theory and practice
Shakhnarovich, G., Indyk, P., & Darrell, T. J. (2005) · Cited by 400 · see citing works
Searching in one billion vectors: Re-rank with source coding
Jeǵou, H., Tavenard, R., Douze, M., & Amsaleg, L. (2011) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2011.5946540 · Cited by 317 · see citing works
Locality sensitive hashing: A comparison of hash function types and querying mechanisms
Paulevé, L., Jeǵou, H., & Amsaleg, L. (2010) · Pattern Recognition Letters · doi:10.1016/j.patrec.2010.04.004 · Cited by 298 · see citing works
Fast search in Hamming space with multi-index hashing
Norouzi, M., Punjani, A., & Fleet, D. J. (2012) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2012.6248043 · Cited by 263 · see citing works
Mobile product search with Bag of Hash Bits and boundary reranking
He, J., Feng, J., Liu, X., et al. (2012) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2012.6248030 · Cited by 185 · see citing works
Multidimensional Spectral Hashing
Weiss, Y., Fergus, R., & Torralba, A. B. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-33715-4_25 · Cited by 156 · see citing works
Transform coding for fast approximate nearest neighbor search in high dimensions
Brandt, J. (2010) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2010.5539852 · Cited by 107 · see citing works
Learning Binary Hash Codes for Large-Scale Image Search
Grauman, K. L., & Fergus, R. (2012) · Studies in computational intelligence · doi:10.1007/978-3-642-28661-2_3 · Cited by 90 · see citing works
Large scale visual recognition
Deng, J. H. (2012) · Cited by 10 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Billion-scale similarity search with GPUs
Johnson, J., Douze, M., & Jegou, H. (2021) · IEEE Transactions on Big Data · doi:10.1109/tbdata.2019.2921572 · Cited by 4,228 · see citing works
Deep hashing for compact binary codes learning
Liong, V. E., Lu, J., Wang, G., Moulin, P., & Zhou, J. (2015) · 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2015.7298862 · Cited by 545 · see citing works
Unsupervised Deep Video Hashing via Balanced Code for Large-Scale Video Retrieval
Wu, G., Han, J., Guo, Y., Liu, L., Ding, G., Ni, Q., & Shao, L. (2019) · IEEE Transactions on Image Processing · doi:10.1109/tip.2018.2882155 · Cited by 148 · see citing works
- Authors
- He, K., Wen, F., & Sun, J.
- Affiliations
- Microsoft Research Asia (China) (CN)
- Venue
- 2013 IEEE Conference on Computer Vision and Pattern Recognition
- Publisher
- IEEE
- Published
- 2013-06
- Pages
- 2938-2945
- ISSN
- 1063-6919 (ISSN-L)
- OpenAlex
- W2029205712
- Cited by
- 395
- References
- 31
- Citations by year
- 2025: 1 · 2024: 9 · 2023: 7 · 2022: 13 · 2021: 29 · 2020: 41 · 2019: 45 · 2018: 48 · 2017: 68 · 2016: 45 · 2015: 49 · 2014: 37 · 2013: 3
- FWCI
- 28.51
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Advanced Image and Video Retrieval Techniques
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Image Retrieval and Classification Techniques
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Advanced Neural Network Applications
- Keywords
- hash code learning, binary codes, Hamming distance, K-means clustering, product spaces
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
