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 条
  • [1] Liu W., Mei T., Zhang Y.D., Instant mobile video search with layered audio-video indexing and progressive transmission, IEEE Transactions on Multimedia, 16, 8, pp. 2242-2255, (2014)
  • [2] Li W., Zhou Z., Learning to hash for big data: current status and future trends, Chinese Science Bulletin, 60, 5-6, pp. 485-490, (2015)
  • [3] Wang J.D., Zhang T., Song J.K., Et al., A survey on learning to hash, IEEE Transactions on Pattern Analysis and Machine Intelligence, 40, 4, pp. 769-790, (2018)
  • [4] Jegou H., Douze M., Schmid C., Product quantization for nearest neighbor search, IEEE Transactions on Pattern Analysis and Machine Intelligence, 33, 1, pp. 117-128, (2011)
  • [5] Ge T.Z., He K.M., Ke Q.F., Et al., Optimized product quantization for approximate nearest neighbor search, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 2946-2953, (2013)
  • [6] Babenko A., Lempitsky V., Additive quantization for extreme vector compression, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 931-938, (2014)
  • [7] Martinez J., Hoos H.H., Little J.J., Stacked quantizers for compositional vector compression
  • [8] Wang J.D., Zhang T., Composite quantization
  • [9] Datar M., Immorlica N., Indyk P., Et al., Locality-sensitive hashing scheme based on p-stable distributions, Proceedings of the 20th Annual Symposium on Computational Geometry, pp. 253-262, (2004)
  • [10] Weiss Y., Torralba A., Fergus R., Spectral hashing, Proceed Ings of the 21st International Conference on Neural Information Processing Systems, pp. 1753-1760, (2008)
123