Nearest Neighbor Search Based on Bit String Partition and Multiple Index

被引：0
作者：
Miao J. [1 ]
Li Z. [1 ]
Zhou Z. [1 ]
Yang C. [1 ]
Liu Z. [1 ]
Liu W. [1 ]
机构：
[1] School of Information Science and Technology, Dalian Maritime University, Dalian
来源：
Jisuanji Fuzhu Sheji Yu Tuxingxue Xuebao/Journal of Computer-Aided Design and Computer Graphics | 2019年 / 31卷 / 05期
关键词：
Bit string partition; Hash representation; Multi-table index; Nearest neighbor search; Query expansion;
D O I：
10.3724/SP.J.1089.2019.17341
中图分类号：
学科分类号：
摘要：
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. © 2019, Beijing China Science Journal Publishing Co. Ltd. All right reserved.
引用
收藏
页码：771 / 779
页数：8
相关论文
共 24 条
  • [21] Ji T.X., Liu X.L., Deng C., Et al., Query-adaptive hash code ranking for fast nearest neighbor search, Proceedings of the 22nd ACM International Conference on Multimedia, pp. 1005-1008, (2014)
  • [22] Liu X.L., Deng C., Lang B., Et al., Query-adaptive reciprocal hash tables for nearest neighbor search, IEEE Transactions on Image Processing, 25, 2, pp. 907-919, (2016)
  • [23] Liu X.L., He J.F., Lang B., Reciprocal hash tables for nearest neighbor search, Proceedings of the 27th AAAI Conference on Artificial Intelligence, pp. 626-632, (2013)
  • [24] Norouzi M., Punjani A., Fleet D.J., Fast search in hamming space with multi-index hashing, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 3108-3115, (2012)
123