@Test public void testComputeBuckets() { EquiDepthStreamHistogram histo = new EquiDepthStreamHistogram(3); histo.addValue(bytesA); histo.addValue(bytesB); histo.addValue(bytesC); histo.addValue(bytesD); histo.addValue(bytesE); List<Bucket> buckets = histo.computeBuckets(); assertEquals(3, buckets.size()); Bucket bucket = buckets.get(0); assertEquals(2, bucket.getCountEstimate()); assertInBucket(bucket, bytesA); assertInBucket(bucket, bytesB); bucket = buckets.get(1); assertEquals(2, bucket.getCountEstimate()); assertInBucket(bucket, bytesC); assertInBucket(bucket, bytesD); bucket = buckets.get(2); assertEquals(1, bucket.getCountEstimate()); assertInBucketInclusive(bucket, bytesE); histo.bars.clear(); a_b.incrementCount(); histo.bars.add(a_b); Bar b_d = new Bar(bytesB, bytesD); b_d.incrementCount(3); histo.bars.add(b_d); histo.bars.add(d_e); buckets = histo.computeBuckets(); bucket = buckets.get(0); byte[][] splits = Bytes.split(bytesB, bytesD, 8); assertArrayEquals(splits[3], bucket.getRightBoundExclusive()); bucket = buckets.get(1); assertArrayEquals(splits[3], bucket.leftBoundInclusive); }
public List<Bucket> computeBuckets() { Preconditions.checkState(bars.size() >= numBuckets, "Not enough data points to compute buckets"); List<Bucket> buckets = new ArrayList<>(); long idealBuckSize = (long) Math.ceil(totalCount / (double) numBuckets); long currCount = 0; int barsIdx = 0; byte[] prevBound = bars.get(0).leftBoundInclusive; Bar currBar = null; for (int i = 0; i < numBuckets; i++) { while (currCount <= idealBuckSize && barsIdx < bars.size()) { currBar = bars.get(barsIdx++); currCount += currBar.getSize(); } long surplus = Math.max(currCount - idealBuckSize, 0); int closestSplitIdx = (int) ((1 - ((double) surplus / currBar.getSize())) * 9); byte[][] splits = Bytes.split(currBar.leftBoundInclusive, currBar.rightBoundExclusive, 8); Bucket bucket = new Bucket(prevBound, splits[closestSplitIdx]); bucket.incrementCountEstimate(currCount - surplus); prevBound = splits[closestSplitIdx]; buckets.add(bucket); currCount = surplus; } return buckets; }
EquiDepthStreamHistogram { public List<Bucket> computeBuckets() { Preconditions.checkState(bars.size() >= numBuckets, "Not enough data points to compute buckets"); List<Bucket> buckets = new ArrayList<>(); long idealBuckSize = (long) Math.ceil(totalCount / (double) numBuckets); long currCount = 0; int barsIdx = 0; byte[] prevBound = bars.get(0).leftBoundInclusive; Bar currBar = null; for (int i = 0; i < numBuckets; i++) { while (currCount <= idealBuckSize && barsIdx < bars.size()) { currBar = bars.get(barsIdx++); currCount += currBar.getSize(); } long surplus = Math.max(currCount - idealBuckSize, 0); int closestSplitIdx = (int) ((1 - ((double) surplus / currBar.getSize())) * 9); byte[][] splits = Bytes.split(currBar.leftBoundInclusive, currBar.rightBoundExclusive, 8); Bucket bucket = new Bucket(prevBound, splits[closestSplitIdx]); bucket.incrementCountEstimate(currCount - surplus); prevBound = splits[closestSplitIdx]; buckets.add(bucket); currCount = surplus; } return buckets; } }
EquiDepthStreamHistogram { public List<Bucket> computeBuckets() { Preconditions.checkState(bars.size() >= numBuckets, "Not enough data points to compute buckets"); List<Bucket> buckets = new ArrayList<>(); long idealBuckSize = (long) Math.ceil(totalCount / (double) numBuckets); long currCount = 0; int barsIdx = 0; byte[] prevBound = bars.get(0).leftBoundInclusive; Bar currBar = null; for (int i = 0; i < numBuckets; i++) { while (currCount <= idealBuckSize && barsIdx < bars.size()) { currBar = bars.get(barsIdx++); currCount += currBar.getSize(); } long surplus = Math.max(currCount - idealBuckSize, 0); int closestSplitIdx = (int) ((1 - ((double) surplus / currBar.getSize())) * 9); byte[][] splits = Bytes.split(currBar.leftBoundInclusive, currBar.rightBoundExclusive, 8); Bucket bucket = new Bucket(prevBound, splits[closestSplitIdx]); bucket.incrementCountEstimate(currCount - surplus); prevBound = splits[closestSplitIdx]; buckets.add(bucket); currCount = surplus; } return buckets; } EquiDepthStreamHistogram(int numBuckets);  EquiDepthStreamHistogram(int numBuckets, int expansionFactor); }
EquiDepthStreamHistogram { public List<Bucket> computeBuckets() { Preconditions.checkState(bars.size() >= numBuckets, "Not enough data points to compute buckets"); List<Bucket> buckets = new ArrayList<>(); long idealBuckSize = (long) Math.ceil(totalCount / (double) numBuckets); long currCount = 0; int barsIdx = 0; byte[] prevBound = bars.get(0).leftBoundInclusive; Bar currBar = null; for (int i = 0; i < numBuckets; i++) { while (currCount <= idealBuckSize && barsIdx < bars.size()) { currBar = bars.get(barsIdx++); currCount += currBar.getSize(); } long surplus = Math.max(currCount - idealBuckSize, 0); int closestSplitIdx = (int) ((1 - ((double) surplus / currBar.getSize())) * 9); byte[][] splits = Bytes.split(currBar.leftBoundInclusive, currBar.rightBoundExclusive, 8); Bucket bucket = new Bucket(prevBound, splits[closestSplitIdx]); bucket.incrementCountEstimate(currCount - surplus); prevBound = splits[closestSplitIdx]; buckets.add(bucket); currCount = surplus; } return buckets; } EquiDepthStreamHistogram(int numBuckets);  EquiDepthStreamHistogram(int numBuckets, int expansionFactor); void addValue(byte[] value); List<Bucket> computeBuckets(); long getTotalCount(); }
EquiDepthStreamHistogram { public List<Bucket> computeBuckets() { Preconditions.checkState(bars.size() >= numBuckets, "Not enough data points to compute buckets"); List<Bucket> buckets = new ArrayList<>(); long idealBuckSize = (long) Math.ceil(totalCount / (double) numBuckets); long currCount = 0; int barsIdx = 0; byte[] prevBound = bars.get(0).leftBoundInclusive; Bar currBar = null; for (int i = 0; i < numBuckets; i++) { while (currCount <= idealBuckSize && barsIdx < bars.size()) { currBar = bars.get(barsIdx++); currCount += currBar.getSize(); } long surplus = Math.max(currCount - idealBuckSize, 0); int closestSplitIdx = (int) ((1 - ((double) surplus / currBar.getSize())) * 9); byte[][] splits = Bytes.split(currBar.leftBoundInclusive, currBar.rightBoundExclusive, 8); Bucket bucket = new Bucket(prevBound, splits[closestSplitIdx]); bucket.incrementCountEstimate(currCount - surplus); prevBound = splits[closestSplitIdx]; buckets.add(bucket); currCount = surplus; } return buckets; } EquiDepthStreamHistogram(int numBuckets);  EquiDepthStreamHistogram(int numBuckets, int expansionFactor); void addValue(byte[] value); List<Bucket> computeBuckets(); long getTotalCount();  }