-
Notifications
You must be signed in to change notification settings - Fork 194
FAQ
Ilya Razenshteyn edited this page Dec 8, 2015
·
25 revisions
- Q: You say that FALCONN uses LSH. What is LSH anyway?
- A: LSH is locality-sensitive hashing, a way to partition a metric space into nicely-shaped cells. See a brief LSH primer for an introduction.
- Q: My favorite paper about the nearest neighbor search claims that LSH requires lots of memory and is thus impractical. Is that true?
- A: Yes and no. As defined originally, LSH indeed can require lots of memory and for large datasets that may be infeasible. However, in 2007, researchers came up with a simple and incredibly efficient way to reduce the space used by the LSH-based data structure, called multiprobe LSH. FALCONN supports multiprobe LSH and works very well with the whole data structure being as small as the dataset itself or even smaller.