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 2022/04/26 00:03:38 UTC
[datasketches-characterization] branch master updated: update KllSketchAccuracyProfile
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/datasketches-characterization.git
The following commit(s) were added to refs/heads/master by this push:
new 8e96933 update KllSketchAccuracyProfile
8e96933 is described below
commit 8e96933681bc354201ee508a32972f295594c393
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Mon Apr 25 17:03:34 2022 -0700
update KllSketchAccuracyProfile
---
...KllFloatsSketchRankGaussianAccuracyProfile.java | 37 ++++++----
.../kll/KllSketchAccuracyProfile.java | 83 ++++++++++++++--------
.../quantiles/BaseQuantilesAccuracyProfile.java | 43 +++++++++--
.../KllFloatsSketchRankGaussianAccuracyJob.conf | 5 +-
src/main/resources/kll/KllSketchAccuracyJob.conf | 10 +--
5 files changed, 120 insertions(+), 58 deletions(-)
diff --git a/src/main/java/org/apache/datasketches/characterization/kll/KllFloatsSketchRankGaussianAccuracyProfile.java b/src/main/java/org/apache/datasketches/characterization/kll/KllFloatsSketchRankGaussianAccuracyProfile.java
index b0e02fd..3b3ecd8 100644
--- a/src/main/java/org/apache/datasketches/characterization/kll/KllFloatsSketchRankGaussianAccuracyProfile.java
+++ b/src/main/java/org/apache/datasketches/characterization/kll/KllFloatsSketchRankGaussianAccuracyProfile.java
@@ -27,6 +27,7 @@ import static org.apache.datasketches.Util.pwr2LawNext;
import org.apache.datasketches.Job;
import org.apache.datasketches.JobProfile;
import org.apache.datasketches.MonotonicPoints;
+import org.apache.datasketches.Properties;
import org.apache.datasketches.characterization.Shuffle;
import org.apache.datasketches.kll.KllFloatsSketch;
import org.apache.datasketches.memory.DefaultMemoryRequestServer;
@@ -41,6 +42,7 @@ import org.apache.datasketches.quantiles.UpdateDoublesSketch;
public class KllFloatsSketchRankGaussianAccuracyProfile implements JobProfile {
private static final DefaultMemoryRequestServer memReqSvr = new DefaultMemoryRequestServer();
private Job job;
+ private Properties props;
//FROM PROPERTIES
//For computing the different stream lengths
@@ -57,6 +59,7 @@ public class KllFloatsSketchRankGaussianAccuracyProfile implements JobProfile {
//Target sketch configuration & error analysis
private int k;
+ private boolean direct;
//DERIVED globals
private KllFloatsSketch sk;
@@ -83,6 +86,7 @@ public class KllFloatsSketchRankGaussianAccuracyProfile implements JobProfile {
@Override
public void start(final Job job) {
this.job = job;
+ props = job.getProperties();
extractProperties();
configureCommon();
doJob();
@@ -97,25 +101,25 @@ public class KllFloatsSketchRankGaussianAccuracyProfile implements JobProfile {
private void extractProperties() {
//stream length
- lgMin = Integer.parseInt(job.getProperties().mustGet("LgMin"));
- lgMax = Integer.parseInt(job.getProperties().mustGet("LgMax"));
- lgDelta = Integer.parseInt(job.getProperties().mustGet("LgDelta"));
- ppo = Integer.parseInt(job.getProperties().mustGet("PPO"));
+ lgMin = Integer.parseInt(props.mustGet("LgMin"));
+ lgMax = Integer.parseInt(props.mustGet("LgMax"));
+ lgDelta = Integer.parseInt(props.mustGet("LgDelta"));
+ ppo = Integer.parseInt(props.mustGet("PPO"));
//numTrials & error quantiles sketch config
- numTrials = 1 << Integer.parseInt(job.getProperties().mustGet("LgTrials"));
- errorSkLgK = Integer.parseInt(job.getProperties().mustGet("ErrSkLgK"));
+ numTrials = 1 << Integer.parseInt(props.mustGet("LgTrials"));
+ errorSkLgK = Integer.parseInt(props.mustGet("ErrSkLgK"));
//plotting & x-axis config
- numPlotPoints = Integer.parseInt(job.getProperties().mustGet("NumPlotPoints"));
+ numPlotPoints = Integer.parseInt(props.mustGet("NumPlotPoints"));
//Target sketch config
- k = Integer.parseInt(job.getProperties().mustGet("K"));
-
+ k = Integer.parseInt(props.mustGet("K"));
+ direct = Boolean.parseBoolean(props.mustGet("direct"));
}
- void configureCommon() {
+ void configureCommon() { //change based on sketch type (KLL vs REQ, etc)
configureSketch();
trueValues = new float[numPlotPoints];
corrTrueValues = new float[numPlotPoints];
- trueValueCorrection = 1; //KLL is always LT
+ trueValueCorrection = 1; //KLL is always LT, if LE this would be 0
errQSkArr = new UpdateDoublesSketch[numPlotPoints];
//configure the error quantiles array
final DoublesSketchBuilder builder = DoublesSketch.builder().setK(1 << errorSkLgK);
@@ -130,9 +134,11 @@ public class KllFloatsSketchRankGaussianAccuracyProfile implements JobProfile {
void configureSketch() {
final WritableMemory wmem = WritableMemory.allocate(10000);
- sk = KllFloatsSketch.newDirectInstance(k, wmem, memReqSvr);
- //sk = KllFloatsSketch.newHeapInstance(K);
- //sk = new KllFloatsSketch(K);
+ if (direct) {
+ sk = KllFloatsSketch.newDirectInstance(k, wmem, memReqSvr);
+ } else {
+ sk = KllFloatsSketch.newHeapInstance(k);
+ }
}
private void doJob() {
@@ -204,15 +210,16 @@ public class KllFloatsSketchRankGaussianAccuracyProfile implements JobProfile {
errQSkArr[pp].reset(); //reset the errQSkArr for next streamLength
}
job.println(LS + "Serialization Bytes: " + sk.getSerializedSizeBytes());
-
}
/**
* A trial consists of updating a virgin sketch with a shuffled stream of streamLength values.
* We capture the estimated ranks for all plotPoints and then update the errQSkArr with those
* error values.
+ * @param sk the sketch under test
* @param stream the source stream
* @param trueValues the true integer ranks at each of the plot points
+ * @param corrTrueValues corrected true values based on the comparison inequality
* @param errQSkArr the quantile error sketches for each plot point to be updated
*/
static void doTrial(final KllFloatsSketch sk, final float[] stream, final float[] trueValues,
diff --git a/src/main/java/org/apache/datasketches/characterization/kll/KllSketchAccuracyProfile.java b/src/main/java/org/apache/datasketches/characterization/kll/KllSketchAccuracyProfile.java
index 337bc9f..0344d40 100644
--- a/src/main/java/org/apache/datasketches/characterization/kll/KllSketchAccuracyProfile.java
+++ b/src/main/java/org/apache/datasketches/characterization/kll/KllSketchAccuracyProfile.java
@@ -29,6 +29,8 @@ import org.apache.datasketches.memory.DefaultMemoryRequestServer;
import org.apache.datasketches.memory.WritableMemory;
/**
+ * This captures the maximum rank error over T trials.
+ * The stream is shuffled prior to each trial.
* This handles either floats or doubles.
* @author Lee Rhodes
*
@@ -42,14 +44,14 @@ public class KllSketchAccuracyProfile extends BaseQuantilesAccuracyProfile {
private double[] doubleQueryValues;
private boolean useBulk;
private String type;
- private boolean direct = false;
+ private boolean direct = false; //heap is default
private boolean useDouble = false; //useFloat is default
//add other types
- KllDoublesSketch dsk = null;
- KllFloatsSketch fsk = null;
+ KllDoublesSketch dskUT = null;
+ KllFloatsSketch fskUT = null;
- @Override
+ @Override //BaseQuantilesAccuracyProfile
public void configure(final Properties props) {
k = Integer.parseInt(props.mustGet("K"));
useBulk = Boolean.parseBoolean(props.mustGet("useBulk"));
@@ -57,28 +59,28 @@ public class KllSketchAccuracyProfile extends BaseQuantilesAccuracyProfile {
type = props.mustGet("type");
if (type.equalsIgnoreCase("double")) { useDouble = true; }
- configureSketch();
+ configureSketchUnderTest();
}
- void configureSketch() {
+ private void configureSketchUnderTest() {
if (useDouble) {
if (direct) {
final WritableMemory dstMem = WritableMemory.allocate(10000);
- dsk = KllDoublesSketch.newDirectInstance(k, dstMem, memReqSvr);
+ dskUT = KllDoublesSketch.newDirectInstance(k, dstMem, memReqSvr);
} else { //heap
- dsk = KllDoublesSketch.newHeapInstance(k);
+ dskUT = KllDoublesSketch.newHeapInstance(k);
}
} else { //useFloat
if (direct) {
final WritableMemory dstMem = WritableMemory.allocate(10000);
- fsk = KllFloatsSketch.newDirectInstance(k, dstMem, memReqSvr);
+ fskUT = KllFloatsSketch.newDirectInstance(k, dstMem, memReqSvr);
} else { //heap
- fsk = KllFloatsSketch.newHeapInstance(k);
+ fskUT = KllFloatsSketch.newHeapInstance(k);
}
}
}
- @Override
+ @Override //BaseQuantilesAccuracyProfile
public void prepareTrial(final int streamLength) {
// prepare input data that will be permuted
if (useDouble) {
@@ -108,57 +110,76 @@ public class KllSketchAccuracyProfile extends BaseQuantilesAccuracyProfile {
}
}
- @Override
+ /**
+ * For each trial:
+ * <ul>
+ * <li>Feed the sketch under test (skUT) a shuffled stream of length SL of "true" values.</li>
+ * <li>Query the skUT for the estimated rank of each true value and capture the maximum
+ * error of all the estimated ranks</li>
+ * <li>Return this maximum error of this trial.</li>
+ * </ul>
+ */
+ @Override //BaseQuantilesAccuracyProfile
public double doTrial() {
- double maxRankError = 0;
+ double worstNegRankError = 0;
+ double worstPosRankError = 0;
if (useDouble) {
shuffle(inputDoubleValues);
- // reset sketch
- dsk.reset();
+ // reset then update sketch
+ dskUT.reset();
for (int i = 0; i < inputDoubleValues.length; i++) {
- dsk.update(inputDoubleValues[i]);
+ dskUT.update(inputDoubleValues[i]);
}
// query sketch and gather results
- maxRankError = 0;
+ worstNegRankError = 0;
+ worstPosRankError = 0;
if (useBulk) {
- final double[] estRanks = dsk.getCDF(doubleQueryValues);
+ final double[] estRanks = dskUT.getCDF(doubleQueryValues);
for (int i = 0; i < inputDoubleValues.length; i++) {
final double trueRank = (double) i / inputDoubleValues.length;
- maxRankError = Math.max(maxRankError, Math.abs(trueRank - estRanks[i]));
+ final double deltaRankErr = estRanks[i] - trueRank;
+ if (deltaRankErr < 0) { worstNegRankError = Math.min(worstNegRankError, deltaRankErr); }
+ else { worstPosRankError = Math.max(worstPosRankError, deltaRankErr); }
}
} else {
for (int i = 0; i < inputDoubleValues.length; i++) {
final double trueRank = (double) i / inputDoubleValues.length;
- final double estRank = dsk.getRank(i);
- maxRankError = Math.max(maxRankError, Math.abs(trueRank - estRank));
+ final double deltaRankErr = dskUT.getRank(i) - trueRank;
+ if (deltaRankErr < 0) { worstNegRankError = Math.min(worstNegRankError, deltaRankErr); }
+ else { worstPosRankError = Math.max(worstPosRankError, deltaRankErr); }
}
}
- } else { //use Float
+ }
+ else { //use Float
shuffle(inputFloatValues);
- // build sketch
- fsk.reset();
+ // reset then update sketch
+ fskUT.reset();
for (int i = 0; i < inputFloatValues.length; i++) {
- fsk.update(inputFloatValues[i]);
+ fskUT.update(inputFloatValues[i]);
}
// query sketch and gather results
- maxRankError = 0;
+ worstNegRankError = 0;
+ worstPosRankError = 0;
if (useBulk) {
- final double[] estRanks = fsk.getCDF(floatQueryValues);
+ final double[] estRanks = fskUT.getCDF(floatQueryValues);
for (int i = 0; i < inputFloatValues.length; i++) {
final double trueRank = (double) i / inputFloatValues.length;
- maxRankError = Math.max(maxRankError, Math.abs(trueRank - estRanks[i]));
+ final double deltaRankErr = estRanks[i] - trueRank;
+ if (deltaRankErr < 0) { worstNegRankError = Math.min(worstNegRankError, deltaRankErr); }
+ else { worstPosRankError = Math.max(worstPosRankError, deltaRankErr); }
}
} else {
for (int i = 0; i < inputFloatValues.length; i++) {
final double trueRank = (double) i / inputFloatValues.length;
- final double estRank = fsk.getRank(i);
- maxRankError = Math.max(maxRankError, Math.abs(trueRank - estRank));
+ final double deltaRankErr = fskUT.getRank(i) - trueRank;
+ if (deltaRankErr < 0) { worstNegRankError = Math.min(worstNegRankError, deltaRankErr); }
+ else { worstPosRankError = Math.max(worstPosRankError, deltaRankErr); }
}
}
}
- return maxRankError;
+ return (worstPosRankError > -worstNegRankError) ? worstPosRankError : worstNegRankError;
}
}
diff --git a/src/main/java/org/apache/datasketches/characterization/quantiles/BaseQuantilesAccuracyProfile.java b/src/main/java/org/apache/datasketches/characterization/quantiles/BaseQuantilesAccuracyProfile.java
index ac9a4d1..0a1d625 100644
--- a/src/main/java/org/apache/datasketches/characterization/quantiles/BaseQuantilesAccuracyProfile.java
+++ b/src/main/java/org/apache/datasketches/characterization/quantiles/BaseQuantilesAccuracyProfile.java
@@ -19,6 +19,13 @@
package org.apache.datasketches.characterization.quantiles;
+import static org.apache.datasketches.GaussianRanks.M1SD;
+import static org.apache.datasketches.GaussianRanks.M2SD;
+import static org.apache.datasketches.GaussianRanks.M3SD;
+import static org.apache.datasketches.GaussianRanks.MED;
+import static org.apache.datasketches.GaussianRanks.P1SD;
+import static org.apache.datasketches.GaussianRanks.P2SD;
+import static org.apache.datasketches.GaussianRanks.P3SD;
import static org.apache.datasketches.Util.pwr2LawNext;
import org.apache.datasketches.Job;
@@ -29,6 +36,26 @@ import org.apache.datasketches.quantiles.DoublesSketch;
import org.apache.datasketches.quantiles.DoublesSketchBuilder;
import org.apache.datasketches.quantiles.UpdateDoublesSketch;
+/**
+ * For capturing the maximum error over T trials a single quantile error threshold.
+ *
+ * <p>Performs the following:</p>
+ * <ul>
+ * <li>Starts the Job</li>
+ * <li>Computes the number of X-axis plot points based on lgMin,lgMax, PPO.</li>
+ * <li>Configures the array of error capturing quantile sketches of size errLgK</li>
+ * <li>Computes the single error threshold errPct</li>
+ * <li>Runs doTrials(), which loops through all plot points and at each plot point
+ * executes doTrial() "trials" times.</li>
+ * <li>The doTrial() is executed by the child class</li>
+ * <li>The doTrial() returns the maximum error over all points in the stream.</li>
+ * <li>Load the maximum rank error from each trial into the error quantiles sketch.</li>
+ * <li>This prints out the "errPct" error over all trials for each specific stream length (SL).</li>
+ * </ul>
+ *
+ * @author lrhodes
+ *
+ */
public abstract class BaseQuantilesAccuracyProfile implements JobProfile {
Job job;
@@ -48,19 +75,21 @@ public abstract class BaseQuantilesAccuracyProfile implements JobProfile {
public void cleanup() {}
//end JobProfile
+ private static final double[] G_QUANTILES_3SD = {M3SD, M2SD, M1SD, MED, P1SD, P2SD, P3SD};
+
private void doTrials() {
final int lgMin = Integer.parseInt(job.getProperties().mustGet("lgMin"));
final int lgMax = Integer.parseInt(job.getProperties().mustGet("lgMax"));
final int ppo = Integer.parseInt(job.getProperties().mustGet("PPO"));
final int numTrials = Integer.parseInt(job.getProperties().mustGet("trials"));
final int errorSketchLgK = Integer.parseInt(job.getProperties().mustGet("errLgK"));
- final int errorPct = Integer.parseInt(job.getProperties().mustGet("errPct"));
builder = DoublesSketch.builder().setK(1 << errorSketchLgK);
configure(job.getProperties());
- job.println("StreamLength\tError");
+ //PRINT HEADER
+ job.println("StreamLength\t-3SD\t-2SD\t-1SD\tMEDIAN\t+1SD\t+2SD\t+3SD");
final int numSteps = MonotonicPoints.countPoints(lgMin, lgMax, ppo);
int streamLength = 1 << lgMin;
@@ -68,13 +97,17 @@ public abstract class BaseQuantilesAccuracyProfile implements JobProfile {
prepareTrial(streamLength);
final UpdateDoublesSketch rankErrorSketch = builder.build();
for (int t = 0; t < numTrials; t++) {
- final double maxRankErrorInTrial = doTrial();
- rankErrorSketch.update(maxRankErrorInTrial);
+ final double worstRankErrorInTrial = doTrial();
+ rankErrorSketch.update(worstRankErrorInTrial);
}
+ final double[] qArr = rankErrorSketch.getQuantiles(G_QUANTILES_3SD);
+
job.println(streamLength + "\t"
- + String.format("%.2f", rankErrorSketch.getQuantile((double) errorPct / 100) * 100));
+ + String.format("%.16f\t%.16f\t%.16f\t%.16f\t%.16f\t%.16f\t%.16f",
+ qArr[0], qArr[1], qArr[2], qArr[3], qArr[4], qArr[5], qArr[6]));
streamLength = pwr2LawNext(ppo, streamLength);
}
+ job.println("");
}
public abstract void configure(Properties props);
diff --git a/src/main/resources/kll/KllFloatsSketchRankGaussianAccuracyJob.conf b/src/main/resources/kll/KllFloatsSketchRankGaussianAccuracyJob.conf
index 088f7cf..9c811eb 100644
--- a/src/main/resources/kll/KllFloatsSketchRankGaussianAccuracyJob.conf
+++ b/src/main/resources/kll/KllFloatsSketchRankGaussianAccuracyJob.conf
@@ -15,9 +15,9 @@
# specific language governing permissions and limitations
# under the License.
-JobProfile=org.apache.datasketches.characterization.quantiles.KllFloatsSketchRankGaussianAccuracyProfile
+JobProfile=org.apache.datasketches.characterization.kll.KllFloatsSketchRankGaussianAccuracyProfile
-# Trials config (indep of sketch)
+# Trials config (independent of sketch)
## Stream lengths
LgMin=11 # The starting stream length
LgMax=11 # How high the stream length goes
@@ -32,6 +32,7 @@ NumPlotPoints=100 # number of plot points along the x-axis
# Specific sketch config
K=200 # sketch size and accuracy parameter
+direct=false
# Date-Time Profile
diff --git a/src/main/resources/kll/KllSketchAccuracyJob.conf b/src/main/resources/kll/KllSketchAccuracyJob.conf
index 8a6a22d..2658fd9 100644
--- a/src/main/resources/kll/KllSketchAccuracyJob.conf
+++ b/src/main/resources/kll/KllSketchAccuracyJob.conf
@@ -15,14 +15,14 @@
# specific language governing permissions and limitations
# under the License.
-JobProfile=org.apache.datasketches.characterization.quantiles.KllSketchAccuracyProfile
-K=200 # sketch size and accuracy parameter
+JobProfile=org.apache.datasketches.characterization.kll.KllSketchAccuracyProfile
+K=400 # sketch size and accuracy parameter
useBulk=true # query ranks using getCDF() instead of separate getRank() for each value
-errLgK=10 # parameter for the rank error distribution sketch
+errLgK=14 # parameter for the rank error distribution sketch
errPct=99 # percentile of the rank error distribution to report
-trials=1000 # Trials at every stream length
+trials=10000 # Trials at every stream length
lgMin=0 # The starting stream length
-lgMax=23 # How high the stream length goes
+lgMax=20 # How high the stream length goes
PPO=8 # The horizontal x-resolution of trials points
type=float
direct=false
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org