Improving Cluster-Based Index Structure for Approximate Nearest Neighbor Graph Search by Deep Learning-Based Hill-Climbing

Article Sidebar

PDF
Published: Sep 28, 2022
DOI: https://doi.org/10.55164/ajstr.v25i3.247183
Keywords:
Inverted indexing Nearest Neighbor Search Nearest Neighbor Graph Hill-climbing Neural network

Main Article Content

Munlika Rattaphun
Faculty of Science and Technology, Nakhon Si Thammarat Rajabhat University, Nakhon Si Thammarat, 80280, Thailand;
Amorntip Prayoonwong
Faculty of Science and Technology, Suratthani Rajabhat University, Suratthani, 84100, Thailand;
Chih-Yi Chiu
Department of Computer Science and Information Engineering, National Chiayi University, Chiayi City 600355, Taiwan
Kritaphat Songsri-in
Faculty of Science and Technology, Nakhon Si Thammarat Rajabhat University, Nakhon Si Thammarat, 80280, Thailand;

Abstract

This study presents a novel approach to archive an excellent tradeoff between search accuracy and computation cost in approximate nearest neighbor search. Usually, the k-nearest neighbor (kNN) graph and hill-climbing algorithm are adopted to accelerate the search process. However, using random seeds in the original hill-climbing is inefficient as they initiate an unsuitable search with inappropriate sources. Instead, we propose a neural network model to generate high-quality seeds that can boost query assignment efficiency. We evaluated the experiment on the benchmarks of SIFT1M and GIST1M datasets and showed the proposed seed prediction model effectively improves the search performance.

Article Details

Issue
Vol. 25 No. 3 (2022): July - September 2022
Section
Research Articles
Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

References

Hu, P.; Peng, X.; Zhu, H.; Zhen, L.; Lin, J. Learning cross-modal retrieval with noisy labels. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2021, 5403-5413.

Prétet, L.; Richard, G.; Peeters, G. Learning to rank music tracks using triplet loss. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2020, 511-515.

Jegou, H.; Douze, M.; Schmid, C. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence 2011, 33(1), 117-128.

Ge, T.; He, K.; Ke, Q.; Sun, J. Optimized product quantization for approximate nearest neighbor search. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2013, 2946-2953.

Fu, C.; Cai, D. Efanna: An extremely fast approximate nearest neighbor search algorithm based on knn graph. arXiv preprint arXiv:1609.07228 2016.

Muja, M.; Lowe, D. G. Scalable nearest neighbor algorithms for high dimensional data. IEEE transactions on pattern analysis and machine intelligence, 2014, 36(11), 2227-2240.

Heo, J. P.; Lee, Y.; He, J.; Chang, S. F.; Yoon, S. E. Spherical hashing: Binary code embedding with hyperspheres. IEEE transactions on pattern analysis and machine intelligence, 2015, 37(11), 2304-2316.

Malkov, Y. A.; Yashunin, D. A. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence, 2018, 42(4), 824-836.

Chiu, C. Y.; Prayoonwong, A.; Liao, Y. C. Learning to index for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence, 2019, 42(8), 1942-1956.

Zhang, Y. M.; Huang, K.; Geng, G.; Liu, C. L. Fast kNN graph construction with locality sensitive hashing. In Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 2013, 660-674.

Dong, W.; Moses, C.; Li, K. Efficient k-nearest neighbor graph construction for generic similarity measures. In Proceedings of the 20th International Conference on World Wide Web, 2011. 577-586.

Zhao, W. L.; Yang, J.; Deng, C. H. Scalable nearest neighbor search based on KNN graph. arXiv preprint arXiv:1701.08475 2017.

Hajebi, K.; Abbasi-Yadkori, Y.; Shahbazi, H.; Zhang, H. Fast approximate nearest-neighbor search with k-nearest neighbor graph. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence 2011, pp. 1312-1317.

Rattaphun, M.; Prayoonwong, A.; Chiu, C. Y. Indexing in k-Nearest Neighbor Graph by Hash-Based Hill-Climbing. In Proceedinngs of the 16th International Conference on Machine Visios Application (MVA), 2019, 1-4.

Wang, J.; Wang, J.; Zeng, G.; Tu, Z.; Gan, R.; Li, S. Scalable k-nn graph construction for visual descriptors. In Proceedinngs of IEEE Conference on Computer Vision and Pattern Recognition, 2012, 1106-1113.

Wang, J.; Wang, J.; Zeng, G.; Gan, R.; Li, S.; Guo, B. Fast Neighborhood Graph Search Using Cartesian Concatenation. In Proceedings of the IEEE International Conference on Computer Vision, 2013, 2128-2135.

Fu, C.; Xiang, C.; Wang, C; Cai, D. Fast Approximate Nearest Neighbor Search with the Navigating Spreading-out Graph. VLDB Endowment, 2019, 461-474.

Datar, M.; Immorlica, N.; Indyk, P.; Mirrokni, V. S. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the 20th annual Symposium on Computational Geometry, 2004, 253-262.

Gong, Y.; Lazebnik, S.; Gordo, A.; Perronnin, F. Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(12), 2916-2929.

Ercoli, S.; Bertini, M.; Del Bimbo, A. Compact hash codes for efficient visual descriptors retrieval in large scale databases. IEEE Transactions on Multimedia, 2017, 19(11), 2521-2532.

Babenko, A.; Lempitsky, V. The inverted multi-index. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 37(6), 1247-1260.

Xia, Y.; He, K.; Wen, F.; Sun, J. Joint inverted indexing. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2013, 3416-3423.

Dong, Y.; Indyk, P.; Razenshteyn, I.; Wagner, T. Learning space partitions for nearest neighbor search. arXiv preprint arXiv:1901.08544, 2019.