Advances in Hybrid Search and Query Optimization

The field of hybrid search and query optimization is rapidly evolving, with a focus on developing efficient and general solutions for combining high-dimensional vector search with complex relational filtering. Recent developments have introduced novel frameworks and techniques for achieving truly general filtered search, such as cooperative query execution strategies and graph-based indexing. These advancements have led to significant improvements in query throughput and accuracy, outperforming existing state-of-the-art methods. Notably, the integration of machine learning and optimization techniques has enabled the learning of filter-aware distance metrics and the development of more effective indexing structures. Some noteworthy papers in this area include: Compass, which introduces a unified framework for general filtered search across vector and structured data, outperforming existing frameworks in comprehensive empirical evaluations. Allan-Poe, a novel All-in-one graph index accelerated by GPUs for efficient hybrid search, achieving superior end-to-end query accuracy and outperforming state-of-the-art methods in throughput. PathFinder, a new indexing framework that allows users to selectively create ANNS indexes optimized for filters on specific attributes, demonstrating up to 9.8x improvement in query throughput.

Sources

Compass: General Filtered Search across Vector and Structured Data

Sorting by Strip Swaps is NP-Hard

Incremental Selection of Most-Filtering Conjectures and Proofs of the Selected Conjectures

Efficient Query Repair for Aggregate Constraints

All-in-one Graph-based Indexing for Hybrid Search on GPUs

Fast Answering Pattern-Constrained Reachability Queries with Two-Dimensional Reachability Index

PathFinder: Efficiently Supporting Conjunctions and Disjunctions for Filtered Approximate Nearest Neighbor Search

Accelerating Graph Similarity Search through Integer Linear Programming

Learning Filter-Aware Distance Metrics for Nearest Neighbor Search with Multiple Filters

Depth-13 Sorting Networks for 28 Channels

A Compendium of Reductions: reductions.network

Built with on top of