Accelerating Search on Binary Codes in Weighted Hamming Space

An extension version of AAAI 2020: Efficient Querying from Weighted Binary Codes (arxiv link).

Overview

This method is a fast nearest neighbor search framework (FSWBC.cpp) on binary codes in weighted Hamming space based on the multi-index tables[1]. Also, we design a single multi-index hash table (FSWBC_single.cpp) to replace multi-index hash tables, which can reduce the practical storage cost.

Building

Requisites: C++

Data Dir:

databin32.txt and testbin32.txt contain the binary codes generated by Iterative Quantization (ITQ)[2] from the GIST1M dataset.
weight32.txt contains the weights for each query generated by Asymmetric Distance for ITQ [3].

Command: Building

$ g++ array32.cpp -c
$ g++ bucket_group.cpp -c
$ g++ sparse_hashtable.cpp -c
$ g++ FSWBC.cpp -c
$ g++ array32.o bucket_group.o sparse_hashtable.o FSWBC.o -o FSWBC

Then running FSWBC bit_number(optional) and find the time file in data\gist1m\itq-e\32.

And so does FSWBC_single.

Reference

[1] Norouzi, M.; Punjani, A.; and Fleet, D. J. 2014. Fast exact search in hamming space with multi-index hashing. IEEE Trans. on Pattern Anal. and Mach. Intell. 36(6):1107–1119.

[2] Y. Gong, S. Lazebnik, A. Gordo, and F. Perronnin. 2013. Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval. IEEE Trans. on Pattern Anal. and Mach. Intell., vol. 35, no. 12, pp. 2916–2929.

[3] A. Gordo, F. Perronnin, Y. Gong, and S. Lazebnik. 2014. Asymmetric distances for binary embeddings. IEEE Trans. on Pattern Anal. and Mach. Intell., vol. 36, no. 1, pp. 33–47.

Please cite:

@proceedings{weng2020querying,
  title={Efficient Querying From Weighted Binary Codes},
  author={Zhenyu Weng, Yuesheng Zhu},
  booktitle={AAAI},
  year={2020}
}

Acknowledgement

A part of the code is borrowed from Mohammad Norouzi. Thanks for their wonderful works.

Contact