XorBinaryFuse8 failed to construct on some data

[konghuarukhr]

public static void main(String[] args) {
        int n = 500000;
        long[] keys = new long[n];
        for (int i = 0; i < n; i++) {
            keys[i] = i;
        }
        XorBinaryFuse8.construct(keys);
    }

Execute this code will report:

java.lang.ArrayIndexOutOfBoundsException: 500001

Is there any paper/draft can help understand xor binary fuse algorithm?

[thomasmueller]

paper/draft can help understand xor binary fuse algorithm?

Yes, here the paper that contains all the theory about the fuse approach: https://arxiv.org/abs/1907.04749 - it doesn't describe the construction algorithm we use here I'm afraid, but it explains the theory.

[thomasmueller]

The code that fails is a copy of the code from https://github.com/FastFilter/fastfilter_cpp/blob/master/src/xorfilter/3wise_xor_binary_fuse_filter_lowmem.h#L142 - I will try to find out what's going on here.

[thomasmueller]

Hm, I found the problem: if mapping fails, then we forget to do reverseOrder[size] = 1 (this is done correctly in the C / C++ code). But now there's another problem: the array size is too small. I'll try to fix that as well.

[thomasmueller]

Could you verify it is fixed now please?

[konghuarukhr]

I find it is not fixed, this is another construction failure:

public static void main(String[] args) {
int n = 11511;
long[] keys = new long[n];
for (int i = 0; i < n; i++) {
keys[i] = i;
}
XorBinaryFuse8.construct(keys);
}

will report:

...

11511 keys; arrayLength 14336 reverseOrderPos 6371 Exception in thread "main" java.lang.IllegalStateException at org.fastfilter.xor.XorBinaryFuse8.addAll(XorBinaryFuse8.java:219)