Nearest Neighbor Search Based on Bit String Partition and Multiple Index

The bit string represented by hash was one of the most effective methods to solve the similarity search problem of massive data. In view of the problem that the bit string indexing method lead to low search effect, a neighbor search algorithm based on bit string partitioning and multiple index is proposed.Firstly, the essence of bit string partitioning is a combinatorial optimization problem. In this paper, a greedy idea is used to give an approximate solution to the problem. Secondly, in the neighborhood query phase, a new query expansion and fusion mechanism is proposed based on the multi-index structure. Finally, a query adaptive method is used to optimize the imbalance between multiple indexes. On the MNIST, CIFAR-10,SIFT-1M and GIST-1M datasets, experiments and results are presented using Matlab software. The results demonstrate that the proposed method is effective and general in neighborhood search on the index structure based on hash representation.