Locality sensitive false positives

[ekg]

I would like to encourage false positives to occur for inputs that are near (in some comparative sense) members of the set that was used to build the PMHF.

Would the construction algorithm already encourage this to happen for some cases? I haven't tested but perhaps you have thought about this.

If not, what adjustment should I consider making to encourage locality sensitive false positives?

[ekg]

Would it make sense to just change the hash functions used in the construction of the pmhf? If these tend to be locality sensitive then this would tend to drive false positives along the same path through the function.

[rchikhi]

Yes, I believe so that changing the hash function to a LSH one could be fruitful. More importantly, having a benchmark that determines if such a change worked effectively seems like an important component too..

[ekg]

A metric to optimize would be the edit distance between a query and the kmer it is hashed to "flasely".

We want to be more likely to hash to something when the edit distance is lower. That's another metric to check.

To drive this, we could use an actual set of kmers and all edits of them up to some number of substitutions and indels.

[rchikhi]

Oh if you're hashing kmers then yes, that sounds all good. The LSH could then just be the binary value of the canonical l-minimizer of the kmer, where l is picked such that [0;4^l] is the hash range, e.g. for a 32 bits hash range, l=17. I'm sure there are better LSH's though.

[ekg]

Could I just put this kind of l-minimizer hash in as the custom hash function? What else might I need to adjust?

[rchikhi]

That's probably it. You can have a look at https://github.com/rizkg/BBHash/blob/master/example_custom_hash.cpp which shows how to use a custom hash

[rchikhi]

So I took a stab at implementing this. I generated some random 31-mers. The hash function inside BBHash is now the hash of their l-mer minimizer. Then for each inserted element X, I counted the number of times BBHash returns the same index for X as for an element at hamming distance 1 of X (dubbed a "desired collision").

Out of 930000 queries	Number of desired collisions
With regular BBhash hashing  (no minimizer)	82
minimizer-based hash, l=6	4615
l=10	426300
l=15	364356
l=20	248890

Code: https://gist.github.com/rchikhi/7acb1c5f23c4ad7f3641775f69d28cf8