# Navigable Proximity Graph-Driven Native Hybrid Queries with Structured and Unstructured Constraints

arXiv: https://arxiv.org/abs/2203.13601 · HTML: https://mlsanity.com/paper/2203.13601/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 64 references that are in the map.
- First posted on arXiv 25 Mar 2022.

## Builds on (most cited first, 13 of 13)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Composing Text and Image for Image Retrieval - An Empirical Odyssey](https://mlsanity.com/paper/1812.07119/) (2018)
- [Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph](https://mlsanity.com/paper/1707.00143/) (2017)
- [A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2101.12631/) (2021)
- [LiveSketch: Query Perturbations for Guided Sketch-based Visual Search](https://mlsanity.com/paper/1904.06611/) (2019)
- [Graph-based Nearest Neighbor Search: From Practice to Theory](https://mlsanity.com/paper/1907.00845/) (2019)
- [A Survey of Knowledge Graph Embedding and Their Applications](https://mlsanity.com/paper/2107.07842/) (2021)
- [The Design and Implementation of a Real Time Visual Search System on JD E-commerce Platform](https://mlsanity.com/paper/1908.07389/) (2019)
- [Learning to Route in Similarity Graphs](https://mlsanity.com/paper/1905.10987/) (2019)
- [HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces](https://mlsanity.com/paper/1804.06829/) (2018)
- [Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search](https://mlsanity.com/paper/2006.11459/) (2020)
- [Building a Large-scale Multimodal Knowledge Base System for Answering Visual Queries](https://mlsanity.com/paper/1507.05670/) (2015)

## Built on by (most cited first, 7 of 7)

- [PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2312.03940/) (2023)
- [SQUASH: Serverless and Distributed Quantization-based Attributed Vector Similarity Search](https://mlsanity.com/paper/2502.01528/) (2025)
- [Benchmarking Filtered Approximate Nearest Neighbor Search Algorithms on Transformer-based Embedding Vectors](https://mlsanity.com/paper/2507.21989/) (2025)
- [Text2VectorSQL: Towards a Unified Interface for Vector Search and SQL Queries](https://mlsanity.com/paper/2506.23071/) (2025)
- [Filtered Approximate Nearest Neighbor Search in Vector Databases: System Design and Performance Analysis](https://mlsanity.com/paper/2602.11443/) (2026)
- [CubeGraph: Efficient Retrieval-Augmented Generation for Spatial and Temporal Data](https://mlsanity.com/paper/2604.06616/) (2026)
- [HNSW with Accuracy Guarantees Using Graph Spanners](https://mlsanity.com/paper/2607.02338/) (2026)

## Abstract (arXiv)

As research interest surges, vector similarity search is applied in multiple fields, including data mining, computer vision, and information retrieval. Given a set of objects (e.g., a set of images) and a query object, we can easily transform each object into a feature vector and apply the vector similarity search to retrieve the most similar objects. However, the original vector similarity search cannot well support textithybrid queries, where users not only input unstructured query constraint (i.e., the feature vector of query object) but also structured query constraint (i.e., the desired attributes of interest). Hybrid query processing aims at identifying these objects with similar feature vectors to query object and satisfying the given attribute constraints. Recent efforts have attempted to answer a hybrid query by performing attribute filtering and vector similarity search separately and then merging the results later, which limits efficiency and accuracy because they are not purpose-built for hybrid queries. In this paper, we propose a native hybrid query (NHQ) framework based on proximity graph (PG), which provides the specialized textitcomposite index and joint pruning modules for hybrid queries. We easily deploy existing various PGs on this framework to process hybrid queries efficiently. Moreover, we present two novel navigable PGs (NPGs) with optimized edge selection and routing strategies, which obtain better overall performance than existing PGs. After that, we deploy the proposed NPGs in NHQ to form two hybrid query methods, which significantly outperform the state-of-the-art competitors on all experimental datasets (10× faster under the same textitRecall), including eight public and one in-house real-world datasets. Our code and datasets have been released at urlhttps://github.com/AshenOn3/NHQ.