| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
DataSketches.Quantiles.RelativeErrorQuantile.Internal
Synopsis
- data ReqSketch s = ReqSketch {
- k :: !Word32
- rankAccuracySetting :: !RankAccuracy
- criterion :: !Criterion
- sketchRng :: !(Gen s)
- totalN :: !(URef s Word64)
- minValue :: !(URef s Double)
- maxValue :: !(URef s Double)
- sumValue :: !(URef s Double)
- retainedItems :: !(URef s Int)
- maxNominalCapacitiesSize :: !(URef s Int)
- aux :: !(MutVar s (Maybe ReqAuxiliary))
- compactors :: !(MutVar s (Vector (ReqCompactor s)))
- data ReqSketchSnapshot = ReqSketchSnapshot {}
- getCompactors :: PrimMonad m => ReqSketch (PrimState m) -> m (Vector (ReqCompactor (PrimState m)))
- computeTotalRetainedItems :: PrimMonad m => ReqSketch (PrimState m) -> m Int
- retainedItemCount :: PrimMonad m => ReqSketch (PrimState m) -> m Int
- count :: PrimMonad m => ReqSketch (PrimState m) -> m Word64
- mkAuxiliaryFromReqSketch :: PrimMonad m => ReqSketch (PrimState m) -> m ReqAuxiliary
- data CumulativeDistributionInvariants
Documentation
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.
Constructors
| ReqSketch | |
Fields
| |
Instances
data ReqSketchSnapshot Source #
Constructors
| ReqSketchSnapshot | |
Fields | |
Instances
| Show ReqSketchSnapshot Source # | |
Defined in DataSketches.Quantiles.RelativeErrorQuantile.Internal Methods showsPrec :: Int -> ReqSketchSnapshot -> ShowS # show :: ReqSketchSnapshot -> String # showList :: [ReqSketchSnapshot] -> ShowS # | |
getCompactors :: PrimMonad m => ReqSketch (PrimState m) -> m (Vector (ReqCompactor (PrimState m))) Source #
count :: PrimMonad m => ReqSketch (PrimState m) -> m Word64 Source #
Get the total number of items inserted into the sketch
mkAuxiliaryFromReqSketch :: PrimMonad m => ReqSketch (PrimState m) -> m ReqAuxiliary Source #
data CumulativeDistributionInvariants Source #
Constructors
| CumulativeDistributionInvariantsSplitsAreEmpty | |
| CumulativeDistributionInvariantsSplitsAreNotFinite | |
| CumulativeDistributionInvariantsSplitsAreNotUniqueAndMontonicallyIncreasing |