Semi-supervised inverted file index approach for approximate nearest neighbor search

Authors

  • Anton Bazdyrev Educational and Research Institute for Applied System Analysis of the National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute", Kyiv, Ukraine https://orcid.org/0000-0001-8191-897X

DOI:

https://doi.org/10.20535/SRIT.2308-8893.2023.4.05

Keywords:

approximate nearest neighbor search, inverted file index, high-dimensional data, machine learning

Abstract

This paper introduces a novel modification to the Inverted File (IVF) index approach for approximate nearest neighbor search, incorporating supervised learning techniques to enhance the efficacy of intermediate clustering and achieve more balanced cluster sizes. The proposed method involves creating clusters using a neural network by solving a task to classify query vectors into the same bucket as their corresponding nearest neighbor vectors in the original dataset. When combined with minimizing the standard deviation of the bucket sizes, the indexing process becomes more efficient and accurate during the approximate nearest neighbor search. Through empirical evaluation on a test dataset, we demonstrate that the proposed semi-supervised IVF index approach outperforms the industry-standard IVF implementation with fixed parameters, including the total number of clusters and the number of clusters allocated to queries. This novel approach has promising implications for enhancing nearest-neighbor search efficiency in high-dimensional datasets across various applications, including information retrieval, natural language search, recommendation systems, etc.

Author Biography

Anton Bazdyrev, Educational and Research Institute for Applied System Analysis of the National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute", Kyiv

Ph.D. student at Educational and Research Institute for Applied System Analysis of the National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute", Kyiv, Ukraine.

References

P. Indyk and R. Motwani, “Approximate nearest neighbors: towards removing the curse of dimensionality,” in Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), 1998.

H. Jégou, M. Douze, and C. Schmid, “Product Quantization for Nearest Neighbor Search,” IEEE Xplore. [Online]. Available: https://ieeexplore.ieee.org/document/5432202

G. Voronoi, “Une méthode géométrique pour la détermination des régions de visibilité dans le voisinage d’un point de l’espace (A geometric method for determining regions of visibility in the vicinity of a point in space),” Journal de Mathématiques Pures et Appliquées (Journal of Pure and Applied Mathematics), 1908.

J. Johnson, M. Douze, and H. Jégou, “Optimizing Product Quantization for Nearest Neighbor Search,” IEEE Xplore. [Online]. Available: https://ieeexplore.ieee.org/document/6619223

D. E. Rumelhart and J. L. McClelland, “Learning Internal Representations by Error Propagation,” IEEE Xplore. [Online]. Available: https://ieeexplore.ieee.org/document/6302929

Ian Goodfellow, Yoshua Bengio, and Aaron Courville, Deep Learning. 2016. Available: https://www.deeplearningbook.org/

X. Glorot and Y. Bengio, Understanding the difficulty of training deep feedforward neural networks. 2010. [Online]. Available: https://proceedings.mlr.press/v9/glorot10a/glorot10a.pdf

D.P. Kingma, Adam: A Method for Stochastic Optimization. 2014. [Online]. Available: https://arxiv.org/abs/1412.6980

PyTorch. [Online]. Available: https://pytorch.org/

faiss::IndexIVF Class Reference. [Online]. Available: https://faiss.ai/cpp_api/struct/structfaiss_1_1IndexIVF.html

Downloads

Published

2023-12-26

Issue

Section

Theoretical and applied problems of intelligent systems for decision making support