Skip to content

Instantly share code, notes, and snippets.

@prathik
Created April 13, 2016 10:20
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save prathik/84dc388589637a5c6d7e2cffa0cfe55a to your computer and use it in GitHub Desktop.
Save prathik/84dc388589637a5c6d7e2cffa0cfe55a to your computer and use it in GitHub Desktop.
IE Intersect from Union cardinality
public long getIntersection(List<HLL> hllList) {
for(HLL hll:hllList) {
logger.debug("Individual cardinality of " + hll.cardinality());
}
logger.debug("get intersection of hllList = " + hllList);
if(hllList.size() == 1) {
HLL hllObject = hllList.get(0);
logger.debug("Single Cardinality " + hllObject.toString() + " = " + hllObject.cardinality());
return hllObject.cardinality();
}
long totalUnion = HLLUtil.unionHLL(hllList).cardinality();
logger.debug("Total Union is " + totalUnion);
long totalSubSum = 0;
for(int k = 1; k < hllList.size(); k++) {
long setTotalSubSum = 0;
List<List<HLL>> hllCombinations = HLLUtil.generateCombination(k, hllList);
logger.debug("HLL Combinations at k = " + k + " is " + hllCombinations.size());
for(List<HLL> hllCombination: hllCombinations) {
setTotalSubSum += getIntersection(hllCombination);
}
totalSubSum += (long) (Math.pow(-1, k+1)*setTotalSubSum);
logger.debug("Total sub sum at k = " + k + ", subsum = " + setTotalSubSum);
}
logger.debug("Total sum of subset intersections = " + totalSubSum);
long totalCardinality = (long) ((totalUnion - totalSubSum)/Math.pow(-1, hllList.size() + 1));
logger.debug("Cardinality is " + totalCardinality);
return totalCardinality;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment