You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by le...@apache.org on 2020/04/02 05:59:36 UTC
[incubator-datasketches-java] 01/02: Fix Hll bounds for low K.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch FixHLLBounds
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-java.git
commit a0b60003bb6ddcdb02f2d831a1ae4bee975ae1b2
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Wed Apr 1 20:14:45 2020 -0700
Fix Hll bounds for low K.
---
.../java/org/apache/datasketches/hll/HllEstimators.java | 15 +++++++++------
.../org/apache/datasketches/hll/RelativeErrorTables.java | 16 ++++++++--------
.../java/org/apache/datasketches/hll/CouponListTest.java | 2 +-
.../org/apache/datasketches/hll/DirectUnionTest.java | 9 ++++-----
src/test/java/org/apache/datasketches/hll/UnionTest.java | 9 ++++-----
5 files changed, 26 insertions(+), 25 deletions(-)
diff --git a/src/main/java/org/apache/datasketches/hll/HllEstimators.java b/src/main/java/org/apache/datasketches/hll/HllEstimators.java
index 78df59b..0f33746 100644
--- a/src/main/java/org/apache/datasketches/hll/HllEstimators.java
+++ b/src/main/java/org/apache/datasketches/hll/HllEstimators.java
@@ -55,15 +55,17 @@ class HllEstimators {
final boolean oooFlag = absHllArr.isOutOfOrderFlag();
if (oooFlag) {
estimate = absHllArr.getCompositeEstimate();
- rseFactor = HLL_NON_HIP_RSE_FACTOR;
+ rseFactor = HLL_NON_HIP_RSE_FACTOR; //1.03896
} else {
estimate = absHllArr.getHipAccum();
- rseFactor = HLL_HIP_RSE_FACTOR;
+ rseFactor = HLL_HIP_RSE_FACTOR; //.8325546
}
+
final double relErr = (lgConfigK > 12)
- ? (numStdDev * rseFactor) / Math.sqrt(configK)
+ ? -(numStdDev * rseFactor) / Math.sqrt(configK)
: RelativeErrorTables.getRelErr(false, oooFlag, lgConfigK, numStdDev);
- return Math.max(estimate / (1.0 + relErr), numNonZeros);
+ final double lb = Math.max(estimate * (1.0 + relErr), numNonZeros);
+ return lb;
}
static final double hllUpperBound(final AbstractHllArray absHllArr, final int numStdDev) {
@@ -81,9 +83,10 @@ class HllEstimators {
}
final double relErr = (lgConfigK > 12)
- ? ((-1.0) * (numStdDev * rseFactor)) / Math.sqrt(configK)
+ ? (numStdDev * rseFactor) / Math.sqrt(configK)
: RelativeErrorTables.getRelErr(true, oooFlag, lgConfigK, numStdDev);
- return estimate / (1.0 + relErr);
+ final double ub = estimate * (1.0 + relErr);
+ return ub;
}
//THE HLL COMPOSITE ESTIMATOR
diff --git a/src/main/java/org/apache/datasketches/hll/RelativeErrorTables.java b/src/main/java/org/apache/datasketches/hll/RelativeErrorTables.java
index 8942b6d..58f4f05 100644
--- a/src/main/java/org/apache/datasketches/hll/RelativeErrorTables.java
+++ b/src/main/java/org/apache/datasketches/hll/RelativeErrorTables.java
@@ -59,8 +59,8 @@ final class RelativeErrorTables {
return f;
}
- //case 0
- private static double[] HIP_LB = //sd 1, 2, 3
+ //case 1
+ private static double[] HIP_UB = //sd 1, 2, 3
{ //Q(.84134), Q(.97725), Q(.99865) respectively
0.207316195, 0.502865572, 0.882303765, //4
0.146981579, 0.335426881, 0.557052, //5
@@ -73,8 +73,8 @@ final class RelativeErrorTables {
0.012936253, 0.02613829, 0.039387631, //12
};
- //case 1
- private static double[] HIP_UB = //sd 1, 2, 3
+ //case 0
+ private static double[] HIP_LB = //sd 1, 2, 3
{ //Q(.15866), Q(.02275), Q(.00135) respectively
-0.207805347, -0.355574279, -0.475535095, //4
-0.146988328, -0.262390832, -0.360864026, //5
@@ -87,8 +87,8 @@ final class RelativeErrorTables {
-0.012920332, -0.025572893, -0.037896952, //12
};
- //case 2
- private static double[] NON_HIP_LB = //sd 1, 2, 3
+ //case 3
+ private static double[] NON_HIP_UB = //sd 1, 2, 3
{ //Q(.84134), Q(.97725), Q(.99865) respectively
0.254409839, 0.682266712, 1.304022158, //4
0.181817353, 0.443389054, 0.778776219, //5
@@ -101,8 +101,8 @@ final class RelativeErrorTables {
0.016155679, 0.032825719, 0.049677541 //12
};
- //case 3
- private static double[] NON_HIP_UB = //sd 1, 2, 3
+ //case 2
+ private static double[] NON_HIP_LB = //sd 1, 2, 3
{ //Q(.15866), Q(.02275), Q(.00135) respectively
-0.256980172, -0.411905944, -0.52651057, //4
-0.182332109, -0.310275547, -0.412660505, //5
diff --git a/src/test/java/org/apache/datasketches/hll/CouponListTest.java b/src/test/java/org/apache/datasketches/hll/CouponListTest.java
index e668e73..5225c12 100644
--- a/src/test/java/org/apache/datasketches/hll/CouponListTest.java
+++ b/src/test/java/org/apache/datasketches/hll/CouponListTest.java
@@ -113,7 +113,7 @@ public class CouponListTest {
}
double re = sk.getRelErr(true, true, 4, 1);
- assertTrue(re < 0.0);
+ assertTrue(re > 0.0);
}
diff --git a/src/test/java/org/apache/datasketches/hll/DirectUnionTest.java b/src/test/java/org/apache/datasketches/hll/DirectUnionTest.java
index 386dcf2..303519e 100644
--- a/src/test/java/org/apache/datasketches/hll/DirectUnionTest.java
+++ b/src/test/java/org/apache/datasketches/hll/DirectUnionTest.java
@@ -19,20 +19,19 @@
package org.apache.datasketches.hll;
+import static java.lang.Math.min;
import static org.apache.datasketches.hll.TgtHllType.HLL_4;
import static org.apache.datasketches.hll.TgtHllType.HLL_6;
import static org.apache.datasketches.hll.TgtHllType.HLL_8;
-import static java.lang.Math.min;
import static org.testng.Assert.assertEquals;
import static org.testng.Assert.assertFalse;
import static org.testng.Assert.assertTrue;
import static org.testng.Assert.fail;
-import org.testng.annotations.Test;
-
+import org.apache.datasketches.SketchesArgumentException;
import org.apache.datasketches.memory.Memory;
import org.apache.datasketches.memory.WritableMemory;
-import org.apache.datasketches.SketchesArgumentException;
+import org.testng.annotations.Test;
/**
* @author Lee Rhodes
@@ -434,7 +433,7 @@ public class DirectUnionTest {
private static double getBound(int lgK, boolean ub, boolean oooFlag, int numStdDev, double est) {
double re = RelativeErrorTables.getRelErr(ub, oooFlag, lgK, numStdDev);
- return est / (1.0 + re);
+ return est * (1.0 + re);
}
@Test
diff --git a/src/test/java/org/apache/datasketches/hll/UnionTest.java b/src/test/java/org/apache/datasketches/hll/UnionTest.java
index e465554..aaaa361 100644
--- a/src/test/java/org/apache/datasketches/hll/UnionTest.java
+++ b/src/test/java/org/apache/datasketches/hll/UnionTest.java
@@ -19,19 +19,18 @@
package org.apache.datasketches.hll;
+import static java.lang.Math.min;
import static org.apache.datasketches.hll.TgtHllType.HLL_4;
import static org.apache.datasketches.hll.TgtHllType.HLL_6;
import static org.apache.datasketches.hll.TgtHllType.HLL_8;
-import static java.lang.Math.min;
import static org.testng.Assert.assertEquals;
import static org.testng.Assert.assertFalse;
import static org.testng.Assert.assertTrue;
import static org.testng.Assert.fail;
-import org.testng.annotations.Test;
-
-import org.apache.datasketches.memory.Memory;
import org.apache.datasketches.SketchesArgumentException;
+import org.apache.datasketches.memory.Memory;
+import org.testng.annotations.Test;
/**
* @author Lee Rhodes
@@ -440,7 +439,7 @@ public class UnionTest {
private static double getBound(int lgK, boolean ub, boolean oooFlag, int numStdDev, double est) {
double re = RelativeErrorTables.getRelErr(ub, oooFlag, lgK, numStdDev);
- return est / (1.0 + re);
+ return est * (1.0 + re);
}
@Test
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org