An Efficient and Robust Framework for Approximate Nearest Neighbor Search with Attribute Constraint

Abstract

This paper introduces an efficient and robust framework for hybrid query (HQ) processing, which combines approximate nearest neighbor search (ANNS) with attribute constraint. HQ aims to find objects that are both similar to a feature vector and match some structured attributes. Existing methods handle ANNS and attribute filtering separately, leading to inefficiency and inaccuracy. Our framework, called native hybrid query (NHQ), uses a proximity graph (PG) as a composite index and applies joint pruning modules for HQ. We can easily adapt existing PGs to this framework for efficient HQ processing. We also propose two new navigable PGs (NPGs) with optimized edge selection and routing, which improve the overall ANNS performance. We implement five HQ methods based on the proposed NPGs and existing PGs in NHQ, and show that they outperform the state-of-the-art methods on 10 real-world datasets (up to 315x faster with the same accuracy).

Mengzhao Wang

PhD candidate

I am currently a second-year Ph.D. student at Zhejiang University. My research interests include high-dimensional data storage, retrieval, and their applications in large language models (LLMs).