4 ms·
Fantastic article! How does this compare to ANN for the use case? https://erikbern.com/2015/10/01/nearest-neighbors-and-vector-models-part-2-how-to-search-in-h
by tipsytoad 4y ago
Fantastic article! How does this compare to ANN for the use case?
https://erikbern.com/2015/10/01/nearest-neighbors-and-vector-models-part-2-how-to-search-in-high-dimensional-spaces.html https://erikbern.com/2015/10/01/nearest-neighbors-and-vector...
- gpderetta 4y agoReminds me of the random projections dimensionality reduction schema which is often used with LSH. In fact the described forest of trees schema can probably be interpreted as an LSH. Disclaimer: I haven't touched this stuff for more than 10 years. Don't know what's the state of the art now.
- uniqueuid 4y agoI agree that random hyperplanes are underpinning both, but as far as I recall, usually only one set of random planes is used in LSH (i.e. one set of trees). The granularity of approximate proximity rests in the number of identical signs, i.e. being on the same side of the plane. There is another good and more technical explanation (using bands) in chapter 2 of mining massive datasets by Leskovec, Rajaraman and Ullman.
- gpderetta 4y agoAs I said, it has been a long time! I have dim memories of using random k basis vectors to convert high dimensionality feature vectors to k dimensions, and doing m times to generate multiple projections as part of a an LSH schema. Min-hashing might have been involved.
- senderista 4y agoIIRC, minhashing is used to approximate Jacquard similarity (a set-theoretic measure), while random hyperplanes (aka simhashing) is used to approximate cosine similarity (a geometric/algebraic measure). So they solve different problems, even though some problems can be cast in terms of either framework.