LSH: solve the EXACT Near Neighbor Search?

Question

I'm curious if it's possible to find exact match using LSH. On MIT website about LSH they state:

Locality-Sensitive Hashing (LSH) is an algorithm for solving the approximate or exact Near Neighbor Search in high dimensional spaces

https://www.mit.edu/~andoni/LSH/

I kinda made some search around internet and google scholar but it seems like there's no sign about it. Is there anyone know if it's possible and can point me to the paper about it? Much appreciated.

Answer 1

You have to iterate through all cells that overlap your query range.

Then you'll find all neighbors. But of course this gets more costly, in particular in high dimensional data, or with large query ranges. If your query range is small, you may get away with just a few cells.

Answer 2

There are a lot of heuristic approaches, but if you want something really state of the art, check "Confirmation Sampling for Exact Nearest Neighbor Search".