RWS hashing & RNG are counterproductive for the similarity metric about semantic HOT 3 OPEN

Instead, we want something more like locality-sensitive hashing, which has the continuity property. I’ve also been pointed towards principal component analysis, tho I don’t know much about it just yet.

from semantic.

Some references following a conversation with @kavgan:

• Mining of Massive Datasets, Chapter 3: Finding Similar Items, by Jure Leskovec, Anand Rajaraman, & Jeff Ullman — see also the full book
• Min Hashing, from a University of Utah course taught by Jeff M. Phillips
• The pq-Gram Distance between Ordered Labeled Trees, by Nikolaus Augsten, Michael Böhlen, & Johann Gamper

from semantic.

The conclusion I arrived at from my conversation with @kavgan:

Reading further, I realize that I misunderstood the roles of LSH, MinHash, and shingling. We’ve got ~three different problems here:

• A similarity metric for labels. Our current system just hashes them so similar text in e.g. leaf nodes is essentially ignored; shingling and so forth would seem applicable.
• A similarity metric for subtrees. We currently use random-walk similarity with the problems detailed in that issue. The Jaccard similarity on bags of p,q-grams seems applicable, with MinHashing being an efficient approximation thereof.
• A mechanism to select the most-similar pairs of subtrees from two lists. We currently use a k-d tree for nearest-neighbour lookups based on the random-walk similarity, with the problems that entails, plus some biases that have been hard to eliminate. LSH comes into play here, grouping candidate pairs together into bands.

So where I’ve been focusing on alternatives for computing the d-dimensional unit vectors which RWS entails (specifically, how to do it without hashing or the random number generator), LSH would eliminate the need for these unit vectors altogether.

Notably, each sub-problem is orthogonal. I’d suggest we tackle MinHashing and LSH before shingling; improvements to leaf similarity will be most noticeable with improvements to small branch similarity already in place.

from semantic.