Semi-supervised inverted file index approach for approximate nearest neighbor search
DOI:
https://doi.org/10.20535/SRIT.2308-8893.2023.4.05Keywords:
approximate nearest neighbor search, inverted file index, high-dimensional data, machine learningAbstract
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.
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