diff options
author | Henning Baldersheim <balder@yahoo-inc.com> | 2021-03-28 15:44:46 +0200 |
---|---|---|
committer | Henning Baldersheim <balder@yahoo-inc.com> | 2021-03-28 15:44:46 +0200 |
commit | 031ab58a44a4964c540e6c84621ec718ed926efd (patch) | |
tree | f074a87266e7c6f3c8323801786c79b7901c9233 /container-search | |
parent | cd9645f8ee72eb99b9453773fb0e51b00cdcc9ef (diff) |
Precompute StudentT.inverseCumulativeProbability for default probability and up to 66 nodes per group.
Diffstat (limited to 'container-search')
-rw-r--r-- | container-search/src/main/java/com/yahoo/search/dispatch/TopKEstimator.java | 32 |
1 files changed, 25 insertions, 7 deletions
diff --git a/container-search/src/main/java/com/yahoo/search/dispatch/TopKEstimator.java b/container-search/src/main/java/com/yahoo/search/dispatch/TopKEstimator.java index d48e337b0c1..aef1ef2f498 100644 --- a/container-search/src/main/java/com/yahoo/search/dispatch/TopKEstimator.java +++ b/container-search/src/main/java/com/yahoo/search/dispatch/TopKEstimator.java @@ -13,6 +13,8 @@ public class TopKEstimator { private final double defaultP; private final boolean estimate; private final double skewFactor; + private final double [] defaultCumulativeProbability; + private final static int MIN_N = 2; private static boolean needEstimate(double p) { return (0.0 < p) && (p < 1.0); @@ -25,24 +27,40 @@ public class TopKEstimator { defaultP = defaultProbability; estimate = needEstimate(defaultP); this.skewFactor = skewFactor; + defaultCumulativeProbability = new double[64]; + for (int i=0; i < defaultCumulativeProbability.length; i++) { + defaultCumulativeProbability[i] = computeCumulativeProbability(i+MIN_N, defaultP); + } } - double estimateExactK(double k, double n, double p) { + private double inverseCumulativeProbability(int n, double p) { + if (p == defaultP && (n >= MIN_N) && (n < defaultCumulativeProbability.length + MIN_N)) { + return defaultCumulativeProbability[n - MIN_N]; + } + return computeCumulativeProbability(n, p); + } + private double computeCumulativeProbability(int n, double p) { + double p_inverse = 1 - (1 - p)/computeN(n); + return studentT.inverseCumulativeProbability(p_inverse); + } + private double computeN(double n) { double p_max = (1 + skewFactor)/n; - n = Math.max(1, 1/p_max); + return Math.max(1, 1/p_max); + } + double estimateExactK(double k, int n_i, double p) { + double n = computeN(n_i); double variance = k * 1/n * (1 - 1/n); - double p_inverse = 1 - (1 - p)/n; - return k/n + studentT.inverseCumulativeProbability(p_inverse) * Math.sqrt(variance); + return k/n + inverseCumulativeProbability(n_i, p) * Math.sqrt(variance); } - double estimateExactK(double k, double n) { + double estimateExactK(double k, int n) { return estimateExactK(k, n, defaultP); } public int estimateK(int k, int n) { - return (estimate && n > 1) + return (estimate && (n >= MIN_N)) ? Math.min(k, (int)Math.ceil(estimateExactK(k, n, defaultP))) : k; } public int estimateK(int k, int n, double p) { - return (needEstimate(p) && (n > 1)) + return (needEstimate(p) && (n >= MIN_N)) ? Math.min(k, (int)Math.ceil(estimateExactK(k, n, p))) : k; } |