abstract class CountMinSketch extends AnyRef
A Count-min sketch is a probabilistic data structure used for cardinality estimation using sub-linear space. Currently, supported data types include:
ByteShortIntegerLongString
A CountMinSketch is initialized with a random seed, and a pair of parameters:
- relative error (or
eps), and - confidence (or
delta)
Suppose you want to estimate the number of times an element x has appeared in a data
stream so far. With probability delta, the estimate of this frequency is within the
range true frequency <= estimate <= true frequency + eps * N, where N is the
total count of items have appeared the data stream so far.
Under the cover, a CountMinSketch is essentially a two-dimensional long array
with depth d and width w, where
d = ceil(2 / eps)w = ceil(-log(1 - confidence) / log(2))
This implementation is largely based on the CountMinSketch class from stream-lib.
- Source
- CountMinSketch.java
- Alphabetic
- By Inheritance
- CountMinSketch
- AnyRef
- Any
- Hide All
- Show All
- Public
- Protected
Instance Constructors
- new CountMinSketch()
Abstract Value Members
- abstract def add(item: AnyRef, count: Long): Unit
Increments
item's count bycount. - abstract def add(item: AnyRef): Unit
Increments
item's count by one. - abstract def addBinary(item: Array[Byte], count: Long): Unit
Increments
item's count bycount. - abstract def addBinary(item: Array[Byte]): Unit
Increments
item's count by one. - abstract def addLong(item: Long, count: Long): Unit
Increments
item's count bycount. - abstract def addLong(item: Long): Unit
Increments
item's count by one. - abstract def addString(item: String, count: Long): Unit
Increments
item's count bycount. - abstract def addString(item: String): Unit
Increments
item's count by one. - abstract def confidence(): Double
Returns the confidence (or
delta) of thisCountMinSketch. - abstract def depth(): Int
Depth of this
CountMinSketch. - abstract def estimateCount(item: AnyRef): Long
Returns the estimated frequency of
item. - abstract def mergeInPlace(other: CountMinSketch): CountMinSketch
Merges another
CountMinSketchwith this one in place.Merges another
CountMinSketchwith this one in place.Note that only Count-Min sketches with the same
depth,width, and random seed can be merged. - abstract def relativeError(): Double
Returns the relative error (or
eps) of thisCountMinSketch. - abstract def toByteArray(): Array[Byte]
Serializes this
CountMinSketchand returns the serialized form. - abstract def totalCount(): Long
Total count of items added to this
CountMinSketchso far. - abstract def width(): Int
Width of this
CountMinSketch. - abstract def writeTo(out: OutputStream): Unit
Writes out this
CountMinSketchto an output stream in binary format.Writes out this
CountMinSketchto an output stream in binary format. It is the caller's responsibility to close the stream.
Concrete Value Members
- final def !=(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
- final def ##: Int
- Definition Classes
- AnyRef → Any
- final def ==(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
- final def asInstanceOf[T0]: T0
- Definition Classes
- Any
- def clone(): AnyRef
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.CloneNotSupportedException]) @IntrinsicCandidate() @native()
- final def eq(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- def equals(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef → Any
- final def getClass(): Class[_ <: AnyRef]
- Definition Classes
- AnyRef → Any
- Annotations
- @IntrinsicCandidate() @native()
- def hashCode(): Int
- Definition Classes
- AnyRef → Any
- Annotations
- @IntrinsicCandidate() @native()
- final def isInstanceOf[T0]: Boolean
- Definition Classes
- Any
- final def ne(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- final def notify(): Unit
- Definition Classes
- AnyRef
- Annotations
- @IntrinsicCandidate() @native()
- final def notifyAll(): Unit
- Definition Classes
- AnyRef
- Annotations
- @IntrinsicCandidate() @native()
- final def synchronized[T0](arg0: => T0): T0
- Definition Classes
- AnyRef
- def toString(): String
- Definition Classes
- AnyRef → Any
- final def wait(arg0: Long, arg1: Int): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException])
- final def wait(arg0: Long): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException]) @native()
- final def wait(): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException])
Deprecated Value Members
- def finalize(): Unit
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.Throwable]) @Deprecated
- Deprecated
(Since version 9)