Falconn++: A Locality-Sensitive Filtering Approach for Approximate Nearest Neighbor Search
Abstract
We present Falconn++, a novel locality-sensitive filtering (LSF) approach for approximate nearest neighbor search on angular distance. Falconn++ can filter out potential far away points in any hash bucket before 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 a higher recall-speed tradeoff 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.
Cite
Text
Pham and Liu. "Falconn++: A Locality-Sensitive Filtering Approach for Approximate Nearest Neighbor Search." Neural Information Processing Systems, 2022.Markdown
[Pham and Liu. "Falconn++: A Locality-Sensitive Filtering Approach for Approximate Nearest Neighbor Search." Neural Information Processing Systems, 2022.](https://mlanthology.org/neurips/2022/pham2022neurips-falconn/)BibTeX
@inproceedings{pham2022neurips-falconn,
title = {{Falconn++: A Locality-Sensitive Filtering Approach for Approximate Nearest Neighbor Search}},
author = {Pham, Ninh and Liu, Tao},
booktitle = {Neural Information Processing Systems},
year = {2022},
url = {https://mlanthology.org/neurips/2022/pham2022neurips-falconn/}
}