Framework for faster search with multi-attribute range filters
Grant: A Framework for Approximate Nearest Neighbor Search with Multi-Attribute Range Filters
Databases
Summary
Finding items similar to a search query often requires filtering by attributes, like price or color. Previous methods mostly handled simple filters, such as one attribute or exact matches, which limits their usefulness. The authors propose Grant, a new method that efficiently handles multiple range-based filters while still quickly finding similar items in large, high-dimensional data. Their experiments show Grant outperforms existing techniques and works well without needing past search data.
What this means in practice
- •For e-commerce engineers: Support fast product searches that combine multiple attribute ranges, like price and size, alongside similarity matching for recommendations.$Commercial implications: Enables building commercial product search engines with advanced filtering and efficient similarity ranking.
- •For multimedia retrieval teams: Enable quick search of media items using features like image similarity combined with filter ranges such as date or resolution.
Authors
Daichi Amagata
Abstract
Recently, academia and industry have considered the problem of approximate nearest neighbor search (ANNS) with filters. In this setting, each object consists of a high-dimensional vector and attribute values. Given a query vector, filters for attribute values, and $k$, this problem retrieves $k$ vectors approximately nearest to the query vector among a set of objects passing the filters. This paper considers range filters, i.e., users can specify a range constraint for each attribute. Most existing works do not consider this setting, and they assume (i) only a single attribute or (ii) matching filters that require the same attribute values or categories. Existing techniques for these assumptions are not available for our setting or are trivially not efficient. Although standard solutions, such as pre-filter and post-filter, can handle our problem, they are also inefficient. Some works tackle the same problem as ours, but their techniques necessitate historical query workloads, which significantly limit practical use cases. To remove these limitations, this work proposes Grant, a novel framework that solves this problem efficiently while accepting arbitrary range filters and ANNS data structures. Grant can guarantee a search time sub-linear to the number of objects, which is not held by existing techniques. We conduct extensive experiments, and their results demonstrate that Grant outperforms existing techniques.