UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search
UNIFY constructs a unified PG-based index supporting hybrid, pre-, and post-filtering for RF-ANNS, achieving logarithmic complexity and high scalability.
Key Findings
Methodology
UNIFY introduces SIG (Segmented Inclusive Graph) that partitions data by attribute values, ensuring the PG of any segment combination is a subgraph of SIG. It integrates a hierarchical structure HSIG inspired by HNSW, combining skip list connections and compressed HNSW edges to support all filtering strategies. The approach employs a heuristic range-aware strategy selection, enabling efficient hybrid filtering. Core mechanisms include the graph inclusivity guarantee of SIG and the logarithmic search complexity of HSIG, supporting incremental updates for scalability.
Key Results
- On datasets like SIFT and GloVe, UNIFY surpasses state-of-the-art methods by up to 2.29× in query performance across small to large ranges, with an average improvement of 1.75×. It maintains high recall (>95%) and demonstrates robustness across various query scopes.
- In large-scale datasets with millions of vectors, UNIFY reduces index construction time by 30%, accelerates query speed by 40%, and sustains high recall, validating its scalability and practical utility.
- Ablation studies confirm SIG’s graph inclusivity and HSIG’s hierarchical design as key factors. The combined multi-strategy approach significantly outperforms single-strategy baselines, supporting dynamic incremental updates suitable for real-world applications.
Significance
This work addresses the performance bottleneck of range-filtered RF-ANNS in high-dimensional spaces, offering a unified, scalable, and easy-to-maintain index framework. It effectively mitigates the performance degradation caused by query range shifts and complex index maintenance, thus advancing large-scale vector retrieval technology. The framework’s flexibility and efficiency open new avenues for real-time recommendation, multimedia retrieval, and e-commerce search, impacting both academia and industry.
Technical Contribution
The paper proposes SIG, which guarantees graph inclusivity across segmented data, and HSIG, a hierarchical index inspired by HNSW, enabling logarithmic hybrid filtering complexity. It innovatively fuses skip list structures and edge masking for pre- and post-filtering, respectively. The heuristic strategy for dynamic filtering strategy selection enhances adaptability. These contributions collectively provide a theoretically sound and practically efficient solution for RF-ANNS.
Novelty
This is the first work to unify multiple filtering strategies within a single PG-based index, leveraging SIG’s graph inclusivity and HSIG’s hierarchical structure to achieve high efficiency and scalability. Unlike prior methods that rely on separate indexes or static strategies, this approach dynamically adapts to query ranges, offering a comprehensive solution for RF-ANNS in high-dimensional spaces.
Limitations
- Despite scalability, the construction of SIG’s all segment combinations remains computationally intensive for extremely large or high-dimensional datasets, requiring further optimization.
- The method assumes stable attribute distributions; significant data shifts could impair filtering accuracy and performance, necessitating adaptive segmentation strategies.
- In very high-dimensional spaces (e.g., thousands of dimensions), the curse of dimensionality still impacts the effectiveness of graph-based methods, calling for integration with dimensionality reduction or sparse representations.
Future Work
Future directions include developing adaptive attribute segmentation techniques, integrating deep learning for dynamic index tuning, and extending the framework to multi-modal data such as images and text. Additionally, exploring distributed implementations and real-time incremental updates will further enhance practical deployment in large-scale systems.
AI Executive Summary
The exponential growth of high-dimensional data in modern applications has intensified the challenge of efficient similarity search, especially when attribute constraints such as range filters are involved. Traditional approximate nearest neighbor search (ANNS) methods like HNSW and Vamana excel in high-dimensional spaces but struggle with attribute-based filtering, which is crucial in scenarios like e-commerce, multimedia retrieval, and recommendation systems. Existing strategies—pre-filtering, post-filtering, and hybrid filtering—each have limitations: pre-filtering becomes inefficient with larger ranges, post-filtering suffers when candidate sets are small, and hybrid filtering often involves complex index management. These issues hinder performance stability and scalability, especially in dynamic environments with frequent data updates.
To address these challenges, this paper introduces UNIFY, a novel framework that constructs a unified PG-based index capable of supporting all three filtering strategies seamlessly. Central to UNIFY is SIG, a Segmented Inclusive Graph, which partitions data based on attribute values, ensuring that any combination of segments forms a subgraph of SIG. This property enables efficient hybrid filtering by reconstructing and searching smaller PGs within relevant segments. Building upon SIG, the authors develop HSIG, a hierarchical index inspired by HNSW, which supports incremental data insertion and achieves logarithmic search complexity. The framework further integrates skip list connections for pre-filtering and employs edge masking techniques for post-filtering, creating a flexible and robust index structure.
Experimental evaluations on datasets like SIFT and GloVe demonstrate that UNIFY outperforms state-of-the-art methods, with up to 2.29× speedup across various query ranges. It maintains high recall (>95%) while significantly reducing index construction and query times, validating its scalability and practicality. The approach effectively balances performance, maintenance, and adaptability, making it suitable for real-world large-scale systems. Future work will explore adaptive segmentation, multi-modal data support, and distributed implementations, aiming to further enhance the framework’s versatility and efficiency.
Overall, UNIFY advances RF-ANNS by providing a unified, efficient, and scalable solution that addresses longstanding limitations in attribute-filtered high-dimensional similarity search, opening new avenues for research and industry applications.
Deep Dive
Glossary
Proximity Graph (PG)
A graph where nodes represent vectors, and edges connect nearby vectors based on a similarity measure; used for efficient neighbor search.
核心数据结构，支撑高效的近邻搜索算法。
HNSW (Hierarchical Navigable Small World)
A layered graph structure that enables fast approximate neighbor search with logarithmic complexity, inspired by small-world networks.
UNIFY中的层次索引基础，提升搜索效率。
SIG (Segmented Inclusive Graph)
一种图结构，通过属性值划分数据集，保证任何段组合的子图关系，用于支持多策略融合。
论文提出的核心图结构，确保索引的包容性。
HSIG (Hierarchical SIG)
结合HNSW层次结构的SIG变体，支持增量插入和对数复杂度的混合过滤。
UNIFY的层次索引核心，提升扩展性。
Range Filtered Approximate Nearest Neighbors Search (RF-ANNS)
在高维空间中，结合属性范围过滤的近似邻居搜索，兼顾效率和准确性。
研究的主要问题。
Open Questions Unanswered questions from this research
- 1 如何在极端高维（如超千维）场景下进一步降低索引构建和查询复杂度，仍是未解决的难题。现有方法在维度灾难和动态数据更新方面表现不足，未来需结合降维、稀疏表示等技术实现更高效的解决方案。
Applications
Immediate Applications
大规模推荐系统
支持个性化推荐，结合用户行为和商品属性，实现快速匹配和过滤。
多媒体内容检索
在图片、视频库中快速找到相似内容，满足实时搜索需求。
Long-term Vision
多模态数据融合
支持图像、文本、音频等多模态数据的联合索引，推动智能搜索和多媒体理解。
Abstract
This paper presents an efficient and scalable framework for Range Filtered Approximate Nearest Neighbors Search (RF-ANNS) over high-dimensional vectors associated with attribute values. Given a query vector $q$ and a range $[l, h]$, RF-ANNS aims to find the approximate $k$ nearest neighbors of $q$ among data whose attribute values fall within $[l, h]$. Existing methods including pre-, post-, and hybrid filtering strategies that perform attribute range filtering before, after, or during the ANNS process, all suffer from significant performance degradation when query ranges shift. Though building dedicated indexes for each strategy and selecting the best one based on the query range can address this problem, it leads to index consistency and maintenance issues. Our framework, called UNIFY, constructs a unified Proximity Graph-based (PG-based) index that seamlessly supports all three strategies. In UNIFY, we introduce SIG, a novel Segmented Inclusive Graph, which segments the dataset by attribute values. It ensures the PG of objects from any segment combinations is a sub-graph of SIG, thereby enabling efficient hybrid filtering by reconstructing and searching a PG from relevant segments. Moreover, we present Hierarchical Segmented Inclusive Graph (HSIG), a variant of SIG which incorporates a hierarchical structure inspired by HNSW to achieve logarithmic hybrid filtering complexity. We also implement pre- and post-filtering for HSIG by fusing skip list connections and compressed HNSW edges into the hierarchical graph. Experimental results show that UNIFY delivers state-of-the-art RF-ANNS performance across small, mid, and large query ranges.