Hybrid search, which integrates vector and structured retrieval, is essential for efficient and accurate information access over large-scale data in modern AI-based applications.We build upon HNSW, a state-of-the-art approximate nearest neighbor index for efficient hybrid search that organizes data in multi-layer proximity graphs.We exploit information from previously executed queries to inform new ones to start with the right foot-i.e., by selecting more effective entry points for the proximity graph exploration.This strategy accelerates convergence from the earliest search steps and improves accuracy.Finally, we experimentally evaluate our approach on six diverse datasets under varying settings, demonstrating consistent improvements.

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.