#306

Committed 30 Apr 2024 10:01PM UTC coverage: 97.645% (-0.5%) from 98.139%

Build # #306

Build Type

push

Committed by

Commit Message

Merge pull request #555 from apache/fix_pom_xml_header

Fix pom xml header

Run Details

26865 of 27513 relevant lines covered (97.64%)

0.98 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

86.36

/src/main/java/org/apache/datasketches/req/BaseReqSketch.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */

package org.apache.datasketches.req;

import org.apache.datasketches.quantilescommon.FloatsSortedView;
import org.apache.datasketches.quantilescommon.QuantileSearchCriteria;
import org.apache.datasketches.quantilescommon.QuantilesFloatsAPI;
import org.apache.datasketches.quantilescommon.QuantilesFloatsSketchIterator;

/**
 * This abstract class provides a single place to define and document the public API
 * for the Relative Error Quantiles Sketch.
 *
 * @see <a href="https://datasketches.apache.org/docs/Quantiles/SketchingQuantilesAndRanksTutorial.html">
 * Sketching Quantiles and Ranks Tutorial</a>
 *
 * @author Lee Rhodes
 */
abstract class BaseReqSketch implements QuantilesFloatsAPI {
  static final byte INIT_NUMBER_OF_SECTIONS = 3;
  //These two factors are used by upper and lower bounds
  private static final double relRseFactor = Math.sqrt(0.0512 / INIT_NUMBER_OF_SECTIONS);
  private static final double fixRseFactor = .084;

  @Override
  public abstract double[] getCDF(float[] splitPoints, QuantileSearchCriteria searchCrit);

  /**
   * If true, the high ranks are prioritized for better accuracy. Otherwise
   * the low ranks are prioritized for better accuracy.  This state is chosen during sketch
   * construction.
   * @return the high ranks accuracy state.
   */
  public abstract boolean getHighRankAccuracyMode();

  @Override
  public abstract int getK();

  @Override
  public abstract float getMaxItem();

  @Override
  public abstract float getMinItem();

  /**
   * Returns an a priori estimate of relative standard error (RSE, expressed as a number in [0,1]).
   * Derived from Lemma 12 in https://arxiv.org/abs/2004.01668v2, but the constant factors were
   * adjusted based on empirical measurements.
   *
   * @param k the given size of k
   * @param rank the given normalized rank, a number in [0,1].
   * @param hra if true High Rank Accuracy mode is being selected, otherwise, Low Rank Accuracy.
   * @param totalN an estimate of the total number of items submitted to the sketch.
   * @return an a priori estimate of relative standard error (RSE, expressed as a number in [0,1]).
   */
  public static double getRSE(final int k, final double rank, final boolean hra, final long totalN) {
    return getRankUB(k, 2, rank, 1, hra, totalN); //more conservative to assume > 1 level
  }

  @Override
  public abstract long getN();

  @Override
  public abstract double[] getPMF(float[] splitPoints, QuantileSearchCriteria searchCrit);

  @Override
  public abstract float getQuantile(double rank, QuantileSearchCriteria searchCrit);

  @Override
  public abstract float[] getQuantiles(double[] normRanks, QuantileSearchCriteria searchCrit);

  @Override
  public abstract float getQuantileLowerBound(double rank);

  public abstract float getQuantileLowerBound(double rank, int numStdDev);

  @Override
  public abstract float getQuantileUpperBound(double rank);

  public abstract float getQuantileUpperBound(double rank, int numStdDev);

  @Override
  public abstract double getRank(float quantile, QuantileSearchCriteria searchCrit);

  /**
   * Gets an approximate lower bound rank of the given normalized rank.
   * @param rank the given rank, a number between 0 and 1.0.
   * @param numStdDev the number of standard deviations. Must be 1, 2, or 3.
   * @return an approximate lower bound rank.
   */
  public abstract double getRankLowerBound(double rank, int numStdDev);

  @Override
  public abstract double[] getRanks(float[] quantiles, QuantileSearchCriteria searchCrit);

  /**
   * Gets an approximate upper bound rank of the given rank.
   * @param rank the given rank, a number between 0 and 1.0.
   * @param numStdDev the number of standard deviations. Must be 1, 2, or 3.
   * @return an approximate upper bound rank.
   */
  public abstract double getRankUpperBound(double rank, int numStdDev);

  @Override
  public abstract int getNumRetained();

  @Override
  public abstract int getSerializedSizeBytes();

  @Override
  public abstract FloatsSortedView getSortedView();

  @Override
  public boolean hasMemory() {
    return false;
  }

  @Override
  public boolean isDirect() {
    return false;
  }

  @Override
  public abstract boolean isEmpty();

  @Override
  public abstract boolean isEstimationMode();

  @Override
  public boolean isReadOnly() {
    return false;
  }

  @Override
  public abstract QuantilesFloatsSketchIterator iterator();

  /**
   * Merge other sketch into this one. The other sketch is not modified.
   * @param other sketch to be merged into this one.
   * @return this
   */
  public abstract ReqSketch merge(final ReqSketch other);

  /**
   * {@inheritDoc}
   * <p>The parameters k, highRankAccuracy, and reqDebug will not change.</p>
   */
  @Override
  public abstract void reset();

  @Override
  public abstract byte[] toByteArray();

  @Override
  public abstract String toString();

  @Override
  public abstract void update(final float item);

  /**
   * A detailed, human readable view of the sketch compactors and their data.
   * Each compactor string is prepended by the compactor lgWeight, the current number of retained
   * quantiles of the compactor and the current nominal capacity of the compactor.
   * @param fmt the format string for the quantiles; example: "%4.0f".
   * @param allData all the retained quantiles for the sketch will be output by
   * compactor level.  Otherwise, just a summary will be output.
   * @return a detailed view of the compactors and their data
   */
  public abstract String viewCompactorDetail(String fmt, boolean allData);

  static boolean exactRank(final int k, final int levels, final double rank,
      final boolean hra, final long totalN) {
    final int baseCap = k * INIT_NUMBER_OF_SECTIONS;
    if (levels == 1 || totalN <= baseCap) { return true; }
    final double exactRankThresh = (double)baseCap / totalN;
    return hra && rank >= 1.0 - exactRankThresh || !hra && rank <= exactRankThresh;
  }

  static double getRankLB(final int k, final int levels, final double rank,
      final int numStdDev, final boolean hra, final long totalN) {
    if (exactRank(k, levels, rank, hra, totalN)) { return rank; }
    final double relative = relRseFactor / k * (hra ? 1.0 - rank : rank);
    final double fixed = fixRseFactor / k;
    final double lbRel = rank - numStdDev * relative;
    final double lbFix = rank - numStdDev * fixed;
    return Math.max(lbRel, lbFix);
  }

  static double getRankUB(final int k, final int levels, final double rank,
      final int numStdDev, final boolean hra, final long totalN) {
    if (exactRank(k, levels, rank, hra, totalN)) { return rank; }
    final double relative = relRseFactor / k * (hra ? 1.0 - rank : rank);
    final double fixed = fixRseFactor / k;
    final double ubRel = rank + numStdDev * relative;
    final double ubFix = rank + numStdDev * fixed;
    return Math.min(ubRel, ubFix);
  }

}

1	/*
2	* Licensed to the Apache Software Foundation (ASF) under one
3	* or more contributor license agreements. See the NOTICE file
4	* distributed with this work for additional information
5	* regarding copyright ownership. The ASF licenses this file
6	* to you under the Apache License, Version 2.0 (the
7	* "License"); you may not use this file except in compliance
8	* with the License. You may obtain a copy of the License at
9	*
10	* http://www.apache.org/licenses/LICENSE-2.0
11	*
12	* Unless required by applicable law or agreed to in writing,
13	* software distributed under the License is distributed on an
14	* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15	* KIND, either express or implied. See the License for the
16	* specific language governing permissions and limitations
17	* under the License.
18	*/
19
20	package org.apache.datasketches.req;
21
22	import org.apache.datasketches.quantilescommon.FloatsSortedView;
23	import org.apache.datasketches.quantilescommon.QuantileSearchCriteria;
24	import org.apache.datasketches.quantilescommon.QuantilesFloatsAPI;
25	import org.apache.datasketches.quantilescommon.QuantilesFloatsSketchIterator;
26
27	/**
28	* This abstract class provides a single place to define and document the public API
29	* for the Relative Error Quantiles Sketch.
30	*
31	* @see <a href="https://datasketches.apache.org/docs/Quantiles/SketchingQuantilesAndRanksTutorial.html">
32	* Sketching Quantiles and Ranks Tutorial</a>
33	*
34	* @author Lee Rhodes
35	*/
36	abstract class BaseReqSketch implements QuantilesFloatsAPI {	1✔
37	static final byte INIT_NUMBER_OF_SECTIONS = 3;
38	//These two factors are used by upper and lower bounds
39	private static final double relRseFactor = Math.sqrt(0.0512 / INIT_NUMBER_OF_SECTIONS);	1✔
40	private static final double fixRseFactor = .084;
41
42	@Override
43	public abstract double[] getCDF(float[] splitPoints, QuantileSearchCriteria searchCrit);
44
45	/**
46	* If true, the high ranks are prioritized for better accuracy. Otherwise
47	* the low ranks are prioritized for better accuracy. This state is chosen during sketch
48	* construction.
49	* @return the high ranks accuracy state.
50	*/
51	public abstract boolean getHighRankAccuracyMode();
52
53	@Override
54	public abstract int getK();
55
56	@Override
57	public abstract float getMaxItem();
58
59	@Override
60	public abstract float getMinItem();
61
62	/**
63	* Returns an a priori estimate of relative standard error (RSE, expressed as a number in [0,1]).
64	* Derived from Lemma 12 in https://arxiv.org/abs/2004.01668v2, but the constant factors were
65	* adjusted based on empirical measurements.
66	*
67	* @param k the given size of k
68	* @param rank the given normalized rank, a number in [0,1].
69	* @param hra if true High Rank Accuracy mode is being selected, otherwise, Low Rank Accuracy.
70	* @param totalN an estimate of the total number of items submitted to the sketch.
71	* @return an a priori estimate of relative standard error (RSE, expressed as a number in [0,1]).
72	*/
73	public static double getRSE(final int k, final double rank, final boolean hra, final long totalN) {
74	return getRankUB(k, 2, rank, 1, hra, totalN); //more conservative to assume > 1 level	1✔
75	}
76
77	@Override
78	public abstract long getN();
79
80	@Override
81	public abstract double[] getPMF(float[] splitPoints, QuantileSearchCriteria searchCrit);
82
83	@Override
84	public abstract float getQuantile(double rank, QuantileSearchCriteria searchCrit);
85
86	@Override
87	public abstract float[] getQuantiles(double[] normRanks, QuantileSearchCriteria searchCrit);
88
89	@Override
90	public abstract float getQuantileLowerBound(double rank);
91
92	public abstract float getQuantileLowerBound(double rank, int numStdDev);
93
94	@Override
95	public abstract float getQuantileUpperBound(double rank);
96
97	public abstract float getQuantileUpperBound(double rank, int numStdDev);
98
99	@Override
100	public abstract double getRank(float quantile, QuantileSearchCriteria searchCrit);
101
102	/**
103	* Gets an approximate lower bound rank of the given normalized rank.
104	* @param rank the given rank, a number between 0 and 1.0.
105	* @param numStdDev the number of standard deviations. Must be 1, 2, or 3.
106	* @return an approximate lower bound rank.
107	*/
108	public abstract double getRankLowerBound(double rank, int numStdDev);
109
110	@Override
111	public abstract double[] getRanks(float[] quantiles, QuantileSearchCriteria searchCrit);
112
113	/**
114	* Gets an approximate upper bound rank of the given rank.
115	* @param rank the given rank, a number between 0 and 1.0.
116	* @param numStdDev the number of standard deviations. Must be 1, 2, or 3.
117	* @return an approximate upper bound rank.
118	*/
119	public abstract double getRankUpperBound(double rank, int numStdDev);
120
121	@Override
122	public abstract int getNumRetained();
123
124	@Override
125	public abstract int getSerializedSizeBytes();
126
127	@Override
128	public abstract FloatsSortedView getSortedView();
129
130	@Override
131	public boolean hasMemory() {
132	return false;	×
133	}
134
135	@Override
136	public boolean isDirect() {
137	return false;	×
138	}
139
140	@Override
141	public abstract boolean isEmpty();
142
143	@Override
144	public abstract boolean isEstimationMode();
145
146	@Override
147	public boolean isReadOnly() {
148	return false;	×
149	}
150
151	@Override
152	public abstract QuantilesFloatsSketchIterator iterator();
153
154	/**
155	* Merge other sketch into this one. The other sketch is not modified.
156	* @param other sketch to be merged into this one.
157	* @return this
158	*/
159	public abstract ReqSketch merge(final ReqSketch other);
160
161	/**
162	* {@inheritDoc}
163	* <p>The parameters k, highRankAccuracy, and reqDebug will not change.</p>
164	*/
165	@Override
166	public abstract void reset();
167
168	@Override
169	public abstract byte[] toByteArray();
170
171	@Override
172	public abstract String toString();
173
174	@Override
175	public abstract void update(final float item);
176
177	/**
178	* A detailed, human readable view of the sketch compactors and their data.
179	* Each compactor string is prepended by the compactor lgWeight, the current number of retained
180	* quantiles of the compactor and the current nominal capacity of the compactor.
181	* @param fmt the format string for the quantiles; example: "%4.0f".
182	* @param allData all the retained quantiles for the sketch will be output by
183	* compactor level. Otherwise, just a summary will be output.
184	* @return a detailed view of the compactors and their data
185	*/
186	public abstract String viewCompactorDetail(String fmt, boolean allData);
187
188	static boolean exactRank(final int k, final int levels, final double rank,
189	final boolean hra, final long totalN) {
190	final int baseCap = k * INIT_NUMBER_OF_SECTIONS;	1✔
191	if (levels == 1 \|\| totalN <= baseCap) { return true; }	1✔
192	final double exactRankThresh = (double)baseCap / totalN;	1✔
193	return hra && rank >= 1.0 - exactRankThresh \|\| !hra && rank <= exactRankThresh;	1✔
194	}
195
196	static double getRankLB(final int k, final int levels, final double rank,
197	final int numStdDev, final boolean hra, final long totalN) {
198	if (exactRank(k, levels, rank, hra, totalN)) { return rank; }	1✔
199	final double relative = relRseFactor / k * (hra ? 1.0 - rank : rank);	1✔
200	final double fixed = fixRseFactor / k;	1✔
201	final double lbRel = rank - numStdDev * relative;	1✔
202	final double lbFix = rank - numStdDev * fixed;	1✔
203	return Math.max(lbRel, lbFix);	1✔
204	}
205
206	static double getRankUB(final int k, final int levels, final double rank,
207	final int numStdDev, final boolean hra, final long totalN) {
208	if (exactRank(k, levels, rank, hra, totalN)) { return rank; }	1✔
209	final double relative = relRseFactor / k * (hra ? 1.0 - rank : rank);	1✔
210	final double fixed = fixRseFactor / k;	1✔
211	final double ubRel = rank + numStdDev * relative;	1✔
212	final double ubFix = rank + numStdDev * fixed;	1✔
213	return Math.min(ubRel, ubFix);	1✔
214	}
215
216	}

apache / datasketches-java / #306

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous