the theta_union estimate value will change dramatically with the order of merge

[520lailai]

I compared the datasketches-java and datasketches-cpp, found the different behavior between JAVA and C++.

see the code below:

datasketches::update_theta_sketch update_sketch1 = datasketches::update_theta_sketch::builder().set_lg_k(14).build();
for(int i = 0; i < 16384; i++) update_sketch1.update(i);

datasketches::update_theta_sketch update_sketch2 = datasketches::update_theta_sketch::builder().set_lg_k(14).build();
for(int i = 0; i < 26384; i++) update_sketch2.update(i);

datasketches::update_theta_sketch update_sketch3 = datasketches::update_theta_sketch::builder().set_lg_k(14).build();
for(int i = 0; i < 86384; i++) update_sketch3.update(i);

datasketches::theta_union sk_union1 = datasketches::theta_union::builder().set_lg_k(16).build();
sk_union1.update(update_sketch1);
sk_union1.update(update_sketch2);
sk_union1.update(update_sketch3);
std::cout <<"test2: result1: " << sk_union1.get_result().get_estimate() << std::endl;

datasketches::theta_union sk_union2 = datasketches::theta_union::builder().set_lg_k(16).build();
sk_union2.update(update_sketch1);
sk_union2.update(update_sketch3);
sk_union2.update(update_sketch2);
std::cout <<"test2: result2: " << sk_union2.get_result().get_estimate() << std::endl;   

the result is :
test2: result1: 151281
test2: result2: 126358

The result is incorrect !!!
And there is a big gap between 151281 and 126358, because of different merge order：
[update_sketch1 -> update_sketch2 -> update_sketch3]
[update_sketch1 -> update_sketch3 -> update_sketch2]

but I using datasketches-java do the same things, I didn't find any problems.

because I set update_sketch's lg_k = 14 and theta_union‘s lg_k = 16, If the theta_union‘s lg_k > update_sketch's lg_k there will be a problem, but if theta_union‘s lg_k <= update_sketch's lg_k there will be no problem.

can we fix this problem?

[jmalkin]

Thanks for reporting this. There's clearly an even more basic problem here -- there are only 86384 distinct items and both estimates are well above that! We'll start investigating.

[jmalkin]

The fix for this was included in v4.1.0, which is now officially released.