# Falconn++: A Locality-sensitive Filtering Approach for Approximate Nearest Neighbor Search

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 44 references that are in the map.
- First posted on arXiv 3 Jun 2022.

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

- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms](https://mlsanity.com/paper/1807.05614/) (2018)
- [Practical and Optimal LSH for Angular Distance](https://mlsanity.com/paper/1509.02897/) (2015)
- [Approximate Nearest Neighbor Search in High Dimensions](https://mlsanity.com/paper/1806.09823/) (2018)
- [Optimal Data-Dependent Hashing for Approximate Near Neighbors](https://mlsanity.com/paper/1501.01062/) (2015)
- [Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors](https://mlsanity.com/paper/1608.03580/) (2016)
- [Quicker ADC : Unlocking the hidden potential of Product Quantization with SIMD](https://mlsanity.com/paper/1812.09162/) (2018)
- [A Framework for Similarity Search with Space-Time Tradeoffs using Locality-Sensitive Filtering](https://mlsanity.com/paper/1605.02687/) (2016)

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

- [Constructing Tree-based Index for Efficient and Effective Dense Retrieval](https://mlsanity.com/paper/2304.11943/) (2023)
- [VIBE: Vector Index Benchmark for Embeddings](https://mlsanity.com/paper/2505.17810/) (2025)
- [Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2402.11354/) (2024)
- [Probabilistic Kernel Function for Fast Angle Testing](https://mlsanity.com/paper/2505.20274/) (2025)
- [Pointing the Way, Hiding the Destination: Practical Private Dense Retrieval at Scale](https://mlsanity.com/paper/2608.25735/) (2026)
- [Group Testing for Accurate and Efficient Range-Based Near Neighbor Search for Plagiarism Detection](https://mlsanity.com/paper/2311.02573/) (2023)

## Abstract (arXiv)

We present Falconn++, a novel locality-sensitive filtering approach for approximate nearest neighbor search on angular distance. Falconn++ can filter out potential far away points in any hash bucket textitbefore querying, which results in higher quality candidates compared to other hashing-based solutions. Theoretically, Falconn++ asymptotically achieves lower query time complexity than Falconn, an optimal locality-sensitive hashing scheme on angular distance. Empirically, Falconn++ achieves higher recall-speed tradeoffs than Falconn on many real-world data sets. Falconn++ is also competitive with HNSW, an efficient representative of graph-based solutions on high search recall regimes.