HORIZON HASKELLDocslts/ghc-9.10.xc74966e2026-09-27Search names, modules, packages, or :: a typeCtrl K

GHC 9.10.3 · lts/ghc-9.10.x · c74966e · 2026-09-27

Moduledata-sketches-0.3.1.0Haskell2010

DataSketches.Quantiles.RelativeErrorQuantile

The Relative Error Quantile (REQ) sketch provides extremely high accuracy at a chosen end of the rank domain. This is best illustrated with some rank domain accuracy plots that compare the KLL quantiles sketch to the REQ sketch.

This first plot illustrates the typical error behavior of the KLL sketch (also the quantiles/DoublesSketch). The error is flat for all ranks (0, 1). The green and yellow lines correspond to +/- one RSE at 68% confidence; the blue and red lines, +- two RSE at 95% confidence; and, the purple and brown lines +- 3 RSE at 99% confidence. The reason all the curves pinch at 0 and 1.0, is because the sketch knows with certainty that a request for a quantile at rank = 0 is the minimum value of the stream; and a request for a quantiles at rank = 1.0, is the maximum value of the stream. Both of which the sketch tracks.

KLL Gaussian Error Quantiles

The next plot is the exact same data and queries fed to the REQ sketch set for High Rank Accuracy (HRA) mode. In this plot, starting at a rank of about 0.3, the contour lines start converging and actually reach zero error at rank 1.0. Therefore the error (the inverse of accuracy) is relative to the requested rank, thus the name of the sketch. This means that the user can perform getQuantile(rank) queries, where rank = .99999 and get accurate results.

ReqSketch Gaussian Error Quantiles - HighRankAccuracy

This next plot is also the same data and queries, except the REQ sketch was configured for Low Rank Accuracy (LRA). In this case the user can perform getQuantiles(rank) queries, where rank = .00001 and get accurate results.

ReqSketch Gaussian Error Quantiles - LowRankAccuracy

  • 4 types
  • 24 values
  • Packagedata-sketches-0.3.1.0
  • Exports28
  • LanguageHaskell2010
  • LicenceLicenseRef-Apache
  • SourceRelativeErrorQuantile.hs

Construction

3 declarations
datadata ReqSketch s
#

This Relative Error Quantiles Sketch is the Haskell implementation based on the paper "Relative Error Streaming Quantiles", https://arxiv.org/abs/2004.01668, and loosely derived from a Python prototype written by Pavel Vesely, ported from the Java equivalent.

This implementation differs from the algorithm described in the paper in the following:

The algorithm requires no upper bound on the stream length. Instead, each relative-compactor counts the number of compaction operations performed so far (via variable state). Initially, the relative-compactor starts with INIT_NUMBER_OF_SECTIONS. Each time the number of compactions (variable state) exceeds 2^{numSections - 1}, we double numSections. Note that after merging the sketch with another one variable state may not correspond to the number of compactions performed at a particular level, however, since the state variable never exceeds the number of compactions, the guarantees of the sketch remain valid.

The size of each section (variable k and sectionSize in the code and parameter k in the paper) is initialized with a value set by the user via variable k. When the number of sections doubles, we decrease sectionSize by a factor of sqrt(2). This is applied at each level separately. Thus, when we double the number of sections, the nominal compactor size increases by a factor of approx. sqrt(2) (+/- rounding).

The merge operation here does not perform "special compactions", which are used in the paper to allow for a tight mathematical analysis of the sketch.

This implementation provides a number of capabilities not discussed in the paper or provided in the Python prototype.

The Python prototype only implemented high accuracy for low ranks. This implementation provides the user with the ability to choose either high rank accuracy or low rank accuracy at the time of sketch construction.

  • The Python prototype only implemented a comparison criterion of "<". This implementation allows the user to switch back and forth between the "<=" criterion and the "<=" criterion.

Instances5TakeSnapshot, Generic, NFData, Rep, Snapshot
valuemkReqSketch
  1. :: PrimMonad m
  2. => Word32

    K

  3. -> RankAccuracy
  4. -> m (ReqSketch (PrimState m))
#

The K parameter can be increased to trade increased space efficiency for higher accuracy in rank and quantile calculations. Due to the way the compaction algorithm works, it must be an even number between 4 and 1024.

A good starting number when in doubt is 6.

Configuration settings

datadata Criterion
#

Constructors

Instances3Eq, Show, InequalitySearch
  • Eq CriterionDefined in data-sketches-core-0.1.0.0 · DataSketches.Quantiles.RelativeErrorQuantile.Types
  • Show CriterionDefined in data-sketches-core-0.1.0.0 · DataSketches.Quantiles.RelativeErrorQuantile.Types
  • InequalitySearch CriterionDefined in data-sketches-core-0.1.0.0 · DataSketches.Quantiles.RelativeErrorQuantile.Types

Sketch summaries

17 declarations
valuerelativeStandardError
  1. :: Int

    k - the given value of k

  2. -> Double

    rank - the given normalized rank, a number in [0,1].

  3. -> RankAccuracy
  4. -> Word64

    totalN - an estimate of the total number of items submitted to the sketch.

  5. -> Double

    an a priori estimate of relative standard error (RSE, expressed as a number in [0,1]).

#

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 modified based on empirical measurements.

valueprobabilityMassFunction
  1. :: PrimMonad m
  2. => ReqSketch (PrimState m)
  3. -> [Double]

    splitPoints - an array of m unique, monotonically increasing double values that divide the real number line into m+1 consecutive disjoint intervals. The definition of an "interval" is inclusive of the left splitPoint (or minimum value) and exclusive of the right splitPoint, with the exception that the last interval will include the maximum value. It is not necessary to include either the min or max values in these splitpoints.

  4. -> m [Double]

    An array of m+1 doubles each of which is an approximation to the fraction of the input stream values (the mass) that fall into one of those intervals. The definition of an "interval" is inclusive of the left splitPoint and exclusive of the right splitPoint, with the exception that the last interval will include maximum value.

#

Returns an approximation to the Probability Mass Function (PMF) of the input stream given a set of splitPoints (values). The resulting approximations have a probabilistic guarantee that be obtained, a priori, from the getRSE(int, double, boolean, long) function.

If the sketch is empty this returns an empty list.

valuequantile
  1. :: PrimMonad m
  2. => ReqSketch (PrimState m)
  3. -> Double

    normRank - the given normalized rank

  4. -> m Double

    the approximate quantile given the normalized rank.

#

Gets the approximate quantile of the given normalized rank based on the lteq criterion.

valuequantiles
  1. :: PrimMonad m
  2. => ReqSketch (PrimState m)
  3. -> [Double]

    normRanks - the given array of normalized ranks.

  4. -> m [Double]

    the array of quantiles that correspond to the given array of normalized ranks.

#

Gets an array of quantiles that correspond to the given array of normalized ranks.

valuerank
  1. :: PrimMonad m
  2. => ReqSketch (PrimState m)
  3. -> Double

    value - the given value

  4. -> m Double

    the normalized rank of the given value in the stream.

#

Computes the normalized rank of the given value in the stream. The normalized rank is the fraction of values less than the given value; or if lteq is true, the fraction of values less than or equal to the given value.

valuerankLowerBound
  1. :: PrimMonad m
  2. => ReqSketch (PrimState m)
  3. -> Double

    rank - the given rank, a value between 0 and 1.0.

  4. -> Int

    numStdDev - the number of standard deviations. Must be 1, 2, or 3.

  5. -> m Double

    an approximate lower bound rank.

#

Returns an approximate lower bound rank of the given normalized rank.

valuerankUpperBound
  1. :: PrimMonad m
  2. => ReqSketch (PrimState m)
  3. -> Double

    rank - the given rank, a value between 0 and 1.0.

  4. -> Int

    numStdDev - the number of standard deviations. Must be 1, 2, or 3.

  5. -> m Double

    an approximate upper bound rank.

#

Returns an approximate upper bound rank of the given rank.

valuecumulativeDistributionFunction
  1. :: PrimMonad m
  2. => ReqSketch (PrimState m)
  3. -> [Double]

    Returns an approximation to the Cumulative Distribution Function (CDF), which is the cumulative analog of the PMF, of the input stream given a set of splitPoint (values).

    The resulting approximations have a probabilistic guarantee that be obtained, a priori, from the getRSE(int, double, boolean, long) function.

    If the sketch is empty this returns Nothing.

  4. -> m (Maybe [Double])
#

Returns an approximation to the Cumulative Distribution Function (CDF), which is the cumulative analog of the PMF, of the input stream given a set of splitPoint (values).

Updating the sketch

6 declarations

If you see this error, please file an issue in the GitHub repository.

datadata CumulativeDistributionInvariants
#
CumulativeDistributionInvariantsSplitsAreEmptyCumulativeDistributionInvariantsSplitsAreNotFiniteCumulativeDistributionInvariantsSplitsAreNotUniqueAndMontonicallyIncreasing
Instances3Eq, Show, Exception