add simhash

[kid1412z]

Hi Haifeng,
I add the LSH search based on signature of simhash, during the implementation, I found that there are a lot of repeated code and we cannot reuse some code already has been implemented. I think we may extract the Hash functions as devices so that all LSH search could share them. But it's not quite easy when I tried, because even the Euclidean hash functions used by LSH and MPLSH is slightly different from each other. It will take time to do this refactor.
BTW, do you have some recommended data sets to test this commit?

commit summary:

• add simhash(simply use weights[1,1,1...1]) and the LSH search for signatures

[haifengl]

Thank you very much for the great work! In smile.sort (of SmileMath) package, we have a HeapSelect class. I guess that it does the same thing as your MaxHeap.

I am not familiar with SimLSH. What test data did they use in the original paper?

I totally agree that there are a lot of duplicated code between LSH and MPLSH. I was very lazy and simply copied LSH to MPLSH and then modify it. Please feel free to refactor it.

[kid1412z]

In LSH.java line:534

n2[i] = neighbors[i + 1];

Is it right that copy from index 1 not 0 ?

[haifengl]

That is the case of hit < k. Note that we add k fake neighbors with 0 distance (line 506 - 512). The purpose of that piece code to remove these fake neighbors. But why starting with 1? I don't remember. Probably should be a more dynamic determined number to filter out all fake neighbors. Maybe it is a bug. Thanks!

[kid1412z]

line 506 puts n fake neighbors with distance Double.MAX, if it's a max heap, the real neighbors are far from top.

Neighbor<double[], E> neighbor = new Neighbor<double[], E>(null, null, 0, Double.MAX_VALUE);

I pushed a test that indicate there's a bug exists in HeapSelect.

[haifengl]

Thank you very much for finding the bug! I am out of town without easy access to computer. I will check it asap.

[haifengl]

This is actually not a bug. Note that thee peek methods returns the k-th smallest value seen so far. k is 10 in your test case. The values you insert are 0.0, 0.1 0.2 0.3 0.4 MAX_VALUE MAX_VALUE ....

Of course, the peek method will return MAX_VALUE in this case.

[haifengl]

Any updates?

[kid1412z]

There's no specified data set in this paper, I decide to use MSRP for testing, and I am completing it.

[haifengl]

Thanks for updates! I will debug line 534 ASAP. So busy in these days.

[haifengl]

Line 534 is a bug. I fix it. Thanks!

[kid1412z]

Hi Haifeng,
I have completed the test, but had no time to do the refactor.

recall test result：

    SNLSH KNN recall is 0.6253140096618396
    SNLSH Nearest recall is 0.6492753623188405
    SNLSH range recall is 0.3713021310103753

[haifengl]

Thanks! Are you sure to keep MaxHeap? BTW, I imported SmileNLP, which includes stuffs such as tokenizer. Do you still want to use Google library?

[kid1412z]

I will try to change to the existing lib, I used the murmur hash in Google library, do we need to implement it ourselves?

[haifengl]

If you believe that murmur is very important for this class, I will implement it. It doesn't look complicated. All other algorithms don't depend on third party libraries. Very few applications use LSH but they will have include this google library in their distribution due to this dependency. Not a necessary. Thanks!

[haifengl]

I import Apache Cassandra's murmur implementation to smile.hash.MurmurHash. It is Apache licensed and thus okay.

[haifengl]

We have tokenizer in SmileNLP.

[kid1412z]

module smile-nlp depends on smile-core, so I can't use nlp in core.

[haifengl]

Can you assume that the input data is already tokenized? This also give the user flexibility to use their own tokenizer (e.g. for some specific language).

[haifengl]

Will this be reused in other algorithms? If not, shall we move it into SNLSH?

[haifengl]

Thanks for refactors. If you can remove MaxHeap, I will pull in. Thanks!

[kid1412z]

Hi Haifeng,
I completed the simhash lsh. Thanks.

[haifengl]

Thanks! The MaxHeap file is still there although it is not in use now. Shall we remove it?

[kid1412z]

Sorry, I forgot to push the change.

[haifengl]

Thank you!