Hacker News Reader

Reminds 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.

I 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.

As 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.

IIRC, 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.

Reply on news.ycombinator.com