I'm trying to experiment with the code in scala and wrote the following pieces as a test case

import com.liveramp.hyperminhash._
import java.util.ArrayList
val sketch1 = new BetaMinHash()
val sketch2 = new BetaMinHash()
val set1 = (1 to 10000).map(_.toByte).toArray
val set2 = (5000 to 15000).map(_.toByte).toArray
sketch1.offer(set1)
sketch2.offer(set2)
val sketches = new ArrayList[BetaMinHash]()
sketches.add(sketch1)
sketches.add(sketch2)
val combiner = BetaMinHashCombiner.getInstance();
val combined = combiner.intersectionCardinality(sketches);

combined gives me 0 while the actual result should be something around 5000. Am I doing something wrong here?

Serialization of sparse objects creates a lot of zeros, which becomes costly in some applications when serialization is used as an intermediate step while building up unions. The proposed scheme is backwards-compatible with the current implementation, but also makes use of negative values (which shouldn't be in the registers) to encode run-lengths of zero values.

Also introduced here is an optimization for union operations, which previously applied logic to the first sketch twice. To that end, a fix to deepCopy() was also needed for BetaMinHash, whose deepCopy never actually copied values.

Motivation:

We want to use this library in both spark and elasticsearch (as a custom plugin); spark to create binary serialized forms and elasticsearch to search/aggregate over them in realtime. Our Spark UDAF necessarily has to create many sparse objects before merging them, and this is made much more efficient in terms of runtime by finding a better encoding scheme for such sparse objects. There is no penalty when objects are "dense" (in terms of serialized size). Impact on deserialization time is minimal; each value is checked for negativity. Serialization now requires two passes: one to determine output size and one to do the serialization.

Bumps junit from 4.12 to 4.13.1.

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

Removed double empty lines and add missing newline at end of of file. Not strictly necessary to stay in line with the Google style guide (if we are trying to stay in line with that), but I think the consistency in whitespace usage is good.

I believe the getLeftmostBits method of the BitHelper class should throw IllegalArgumentException(String.format("numBits must be < %d", Long.SIZE)) instead of IllegalArgumentException(String.format("numBits must be < %d", Integer.SIZE)) because the conditional checks numBits against Long.SIZE and not Integer.SIZE.

This PR adds an optimization to use dynamic register sizes. For example, if R=17, then we can use an int to represent a register instead of a long (since we'd need 6 bits for HLL and 17 for Minhash). This can have a meaningful impact when maintaining many sketches with a large number of registers in total. Since we are pre-1.0, this PR breaks the current serialization format.

This PR cleans up a lot of the repo and adds HyperMinHash, an implementation that is based on HyperLogLog with the addition of bias correction from HyperLogLog++.

Context

CD pipeline should be ready to go now. To release a new version of this lib, we'll probably want to use the maven release plugin which moves the current version off of -SNAPSHOT. It'll temporarily change e.g 1.0-SNAPSHOT to 1.0, perform a deploy, then bump to 1.1-SNAPSHOT to resume development. It also has a bunch of other handy features that make life easier when deploying.

Structure of changes

.travis.yml: in order for the build to succeed, two things need to happen successfully:

1. build and test the module
2. sign artifacts and deploy them to Sonatype (which will mirror to Maven Central)

pom.xml: A few small details that the build needs. Perhaps most interesting is the sign profile.

cd/mvnsettings.xml: Specifies the environment variables that will be injected at build time for use in signing and publishing artifacts.

*.java: just a bunch of changes I had to make to get the build working. Ignore the java files since they'll be revamped in future PRs this week.

Misc

I'd love any comments on readability/accessibility of the non java code.

Potential Improvements

• I think it would also be good to add some notes in the README or elsewhere specifying the dev workflow when editing this repo (i.e: how do you make sure everything short of deploying to maven central works? How do you release etc..).

Snyk has created this PR to upgrade org.apache.commons:commons-math3 from 3.4.1 to 3.6.1.

:information_source: Keep your dependencies up-to-date. This makes it easier to fix existing vulnerabilities and to more quickly identify and fix newly disclosed vulnerabilities when they affect your project.

• The recommended version is 3 versions ahead of your current version.
• The recommended version was released 6 years ago, on 2016-03-17.

Note: You are seeing this because you or someone else with access to this repository has authorized Snyk to open upgrade PRs.

For more information:

🧐 View latest project report

🛠 Adjust upgrade PR settings

🔕 Ignore this dependency or unsubscribe from future upgrade PRs

The HyperMinHash Jaccard similarity calculation appears to only compare the "mantissa" portion of the register to increase c, rather than the whole register. The algorithm 2.1.4 in the paper seems to compare the full tuple to increase c. Is there a reason why only the mantissa is compared in your implementation?

First of all, thanks a lot for your useful, nice and interesting Java implementation of HyperMinHash.

My question is about this: https://github.com/LiveRamp/HyperMinHash-java/blob/master/src/main/java/com/liveramp/hyperminhash/BetaMinHashCombiner.java#L54

As I read arXiv:1710.08436, while mergeability is trivial, I think it's not trivial that Jaccard Index estimation for multiple (> 2) sets works properly.

1. Does the estimation still have same accuracy as of 2-set Jaccard Index ?
2. If so, is there any proof ?

Sorry for obscure question. Thanks again.