Combining Graph-based Nearest Neighbour Search and Local Product Quantization Methods

In today's world, where data plays a key role in decision making, the Nearest Neighbor Search (NNS) problem is becoming more and more relevant. NNS is the task of finding, from among all elements of a set, those that are closest to a given element, usually measured by some distance metric. This task is of great importance for many applications, including recommender systems, bioinformatics, image and text processing, relational databases, and so on. With the advancement of technology, the amount of data is increasing exponentially, which makes finding nearest neighbors an even more urgent task. In modern applications used for selecting recommendations in online stores, processing large volumes of images and videos, analyzing social networks, it is often necessary to work with high-dimensional spaces, where the direct application of classical search methods becomes inefficient and computationally expensive. This study presents a method of combining graph traversal methods with product quantization (PQ) clustering to accelerate and improve the efficiency of nearest neighbor search. This approach allows us to quickly localize the search space using PQ and start the graph traversal from the most likely location where the closest objects to a given element are located.