Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations.

Piotr Indyk Haike Xu

Published in: NeurIPS (2023)

Keyphrases

approximate nearest neighbor search
worst case
nearest neighbor
hash functions
lower bound
nearest neighbor search
metric space
kd tree
locality sensitive hashing
databases
computational complexity
high dimensional