Simple and Fast Algorithm for Graph-based Filtered Approximate Nearest Neighbor Search (Full Version)
2026-07-27 • Databases
Databases
AI summaryⓘ
The authors discuss a problem where you want to find items similar to a given example but also match certain qualities like color or brand. This is harder than just finding similar items because you have to filter by different attributes that users pick on the spot. They created a new method that works faster and better than older ones for this task. Their tests show that their approach is more efficient at finding these filtered results.
high-dimensional vectorsembeddingapproximate nearest neighbor searchfiltered searchattribute filteringquery vectormachine learning embeddingsalgorithm efficiency
Authors
Reon Uemura, Keito Kido, Daichi Amagata
Abstract
It has been common to represent many objects as high-dimensional vectors due to the proliferation of machine learning-based embedding techniques. One of the most important functions for analyzing high-dimensional vectors is approximate nearest neighbor search, which, given a query vector, retrieves the vector that is approximately the most similar to the query vector. In many real-world applications, such as e-commerce, objects have not only vectors but also attributes, e.g., category, color, and brand, and they require a scenario where users can specify a query vector and a value for each attribute of interest. This problem, called filtered approximate nearest neighbor search, retrieves approximate nearest neighbors from a set of objects that have the specified attribute values. Efficiently solving this problem is challenging because it has to accept arbitrary query vectors and attribute values, which are not known in advance. Existing techniques suffer from slow search performance and difficulty in dealing with arbitrary combinations of attributes. This work overcomes these challenges and proposes a new algorithm for this problem. We conduct extensive experiments, and the results demonstrate the efficiency of our algorithm.