support custom Q or R or P of BetaMinhash

[yuhongye]

Is there any plan to support custom Q or R or P of BetaMinhash?

[sherifnada]

Hi @yuhongye

There are currently no plans to support custom Q/R/P values for BetaMinhash. For that usecase, we recommend using HyperMinHash. Would you mind sharing a little bit about any usecases you have for which you'd like this feature?

Best, Shrif

[yuhongye]

We want to take the intersection of multiple sets and be as accurate as possible, so we need a larger p. I tested the accuracy of HyperMinHash and BetaMinHash in calculating the jaccard index, and found that BetaMinHash is better in the case p=14, q=6, r=10. In my knowledge, the accuracy of these two algorithms should be the same, so I went to the source code to find the difference between them, and found four different implementations：

1. calculate the position of the left-most 1-bit, BetaMinhash code is:

   private static short getLeftmostOneBitPosition(boolean[] bits, int p, int q) {
   int _2toTheQ = (1 << q);
   
   // Notice: I think offset should be p, not p + 1, becaulse index start at 0
   int offset = p + 1; 
   for (int i = offset; i < _2toTheQ + offset; i++) {
     if (bits[i]) {
       return (short) (i + 1 - offset);
     }
   }
   return (short) (_2toTheQ + 1);
   }

   and hyperminhash is

   final long zeroSearchSpace = (hllHash << p) | (long) (1 << (p - 1));
   final int leftmostOnePosition = Long.numberOfLeadingZeros(zeroSearchSpace) + 1;

I think BetaMinhash has a bug, I marked it in the comments of the code.

2. calculate the r bits, BetaMinhash get the rightmost r bit of hash[1], and HyperMinHash get the leftmost r bits of hash[1]

3. when calculate c in the algorithm 2.1.4 in the paper, BetaMinhash compare the whole register, but HyperMinhash only compare the mantissa.

   
   // BetaMinhash
   for (BetaMinHash sketch : sketches) {
   itemInIntersection = itemInIntersection &&
     firstSketch.registers[i] == sketch.registers[i];
   }

// HyperMinhash for (HyperMinHash sketch : sketches) { itemInIntersection = itemInIntersection && firstSketch.registers.getMantissaAtRegister(i) == sketch.registers.getMantissaAtRegister(i); }

4. BetaMinhash use the expectedCollision algorithm in the paper when calculate similarity, but HyperMinHash does not.

I want to know the impact of these differences， Thank you! (Hope you can understand my english expression.)