CountMinSketchAlt implements ISimpleFrequency<Object> { public static CountMinSketchAlt merge(CountMinSketchAlt... estimators) throws CMSMergeException { CountMinSketchAlt merged = null; if (estimators != null && estimators.length > 0) { int depth = estimators[0].depth; int width = estimators[0].width; long[] hashA = Arrays.copyOf(estimators[0].hashA, estimators[0].hashA.length); long[][] table = new long[depth][width]; int size = 0; for (CountMinSketchAlt estimator : estimators) { if (estimator.depth != depth) { throw new CMSMergeException("Cannot merge estimators of different depth"); } if (estimator.width != width) { throw new CMSMergeException("Cannot merge estimators of different width"); } if (!Arrays.equals(estimator.hashA, hashA)) { throw new CMSMergeException("Cannot merge estimators of different seed"); } for (int i = 0; i < table.length; i++) { for (int j = 0; j < table[i].length; j++) { table[i][j] += estimator.table[i][j]; } } size += estimator.size; } merged = new CountMinSketchAlt(depth, width, size, hashA, table); } return merged; } private  CountMinSketchAlt();  CountMinSketchAlt(int depth, int width, int seed);  CountMinSketchAlt(double epsOfTotalCount, double confidence, int seed); private  CountMinSketchAlt(int depth, int width, int size, long[] hashA, long[][] table); double getRelativeError(); double getConfidence(); @Override boolean add(Object item); @Override boolean add(Object item, long count); @Override long estimateCount(Object item); @Override long size(); static CountMinSketchAlt merge(CountMinSketchAlt... estimators); static byte[] serialize(CountMinSketchAlt sketch); static CountMinSketchAlt deserialize(byte[] data); boolean contains(Object item); static final long PRIME_MODULUS; }
@Test public void merge() throws CMSMergeException, FrequencyException { int numToMerge = 5; int cardinality = 1000000; double epsOfTotalCount = 0.0001; double confidence = 0.99; int seed = 7364181; int maxScale = 20; Random r = new Random(); TreeSet<Integer> vals = new TreeSet<Integer>(); CountMinSketchAlt baseline = new CountMinSketchAlt(epsOfTotalCount, confidence, seed); CountMinSketchAlt[] sketchs = new CountMinSketchAlt[numToMerge]; for (int i = 0; i < numToMerge; i++) { sketchs[i] = new CountMinSketchAlt(epsOfTotalCount, confidence, seed); for (int j = 0; j < cardinality; j++) { int scale = r.nextInt(maxScale); int val = r.nextInt(1 << scale); vals.add(val); sketchs[i].add(val, 1); baseline.add(val, 1); } } CountMinSketchAlt merged = CountMinSketchAlt.merge(sketchs); assertEquals(baseline.size(), merged.size()); assertEquals(baseline.getConfidence(), merged.getConfidence(), baseline.getConfidence() / 100); assertEquals(baseline.getRelativeError(), merged.getRelativeError(), baseline.getRelativeError() / 100); for (int val : vals) { assertEquals(baseline.estimateCount(val), merged.estimateCount(val)); } }
@Test public void testMergeEmpty() throws CMSMergeException { assertNull(CountMinSketchAlt.merge()); }
@Test(expected = CMSMergeException.class) public void testUncompatibleMerge() throws CMSMergeException { CountMinSketchAlt cms1 = new CountMinSketchAlt(1, 1, 0); CountMinSketchAlt cms2 = new CountMinSketchAlt(0.1, 0.1, 0); CountMinSketchAlt.merge(cms1, cms2); }