LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index
Summary: LazyLSH enables a single base index to support multiple fractional lp metrics (0<p<1) for approximate NN, avoiding permetric indices. Keeps theoretical guarantees and improves kNN accuracy under fractional distances with lower overhead.
(summarized by gpt-5-nano on Feb 09 2026)
@inproceedings{zheng_sigmod16,
title = {{LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index}},
author = {Zheng, Yuxin and Guo, Qi and Tung, Anthony K. H. and Wu, Sai},
series = {{SIGMOD} '16},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/2882903.2882930},
url = {https://dl.acm.org/doi/10.1145/2882903.2882930},
year = {2016}
}