Versatile Sketch-Based Attribute Filtering for Hybrid Vector Search

This work addresses the problem of hybrid search in vector databases, which store vectors together with some property attributes. Given a query that consists of a vector and some restrictions on its property attributes, we want to retrieve approximate nearest neighbor vectors for the query while ensuring compliance with predicate conditions, such as point or range filters on a specific vector property attribute. The challenge is compounded by the need to balance two competing requirements: on one hand, ensuring high accuracy in the vector search by leveraging a similarity-based index that is independent of specific attributes, allowing it to serve all queries; on the other hand, the impracticality of replicating such a structure for each attribute or predicate condition. To address these challenges, we propose an agnostic, attribute popularity-aware solution for predicate filtering in approximate nearest neighbor (ANN) search, leveraging the efficiency of graph-based indexing structures for vectors. Our method begins by clustering nodes within the underlying graph structure and constructing lightweight in-memory sketches for the predicates. During query processing, the search selectively applies a two-hop traversal strategy only when necessary, guided by the attribute popularity within the identified cluster. Experimental evaluation across five benchmark datasets demonstrates that our approach consistently outperforms state-of-the-art methods.