Packages

class CMSMonoid[K] extends Monoid[CMS[K]] with CommutativeMonoid[CMS[K]]

Monoid for adding CMS sketches.

Usage

eps and delta are parameters that bound the error of each query estimate. For example, errors in answering point queries (e.g., how often has element x appeared in the stream described by the sketch?) are often of the form: "with probability p >= 1 - delta, the estimate is close to the truth by some factor depending on eps."

The type K is the type of items you want to count. You must provide an implicit CMSHasher[K] for K, and Algebird ships with several such implicits for commonly used types such as Long and BigInt.

If your type K is not supported out of the box, you have two options: 1) You provide a "translation" function to convert items of your (unsupported) type K to a supported type such as Double, and then use the contramap function of CMSHasher to create the required CMSHasher[K] for your type (see the documentation of CMSHasher for an example); 2) You implement a CMSHasher[K] from scratch, using the existing CMSHasher implementations as a starting point.

Note: Because Arrays in Scala/Java not have sane equals and hashCode implementations, you cannot safely use types such as Array[Byte]. Extra work is required for Arrays. For example, you may opt to convert Array[T] to a Seq[T] via toSeq, or you can provide appropriate wrapper classes. Algebird provides one such wrapper class, Bytes, to safely wrap an Array[Byte] for use with CMS.

K

The type used to identify the elements to be counted. For example, if you want to count the occurrence of user names, you could map each username to a unique numeric ID expressed as a Long, and then count the occurrences of those Longs with a CMS of type K=Long. Note that this mapping between the elements of your problem domain and their identifiers used for counting via CMS should be bijective. We require a CMSHasher context bound for K, see CMSHasherImplicits for available implicits that can be imported. Which type K should you pick in practice? For domains that have less than 2^64 unique elements, you'd typically use Long. For larger domains you can try BigInt, for example. Other possibilities include Spire's SafeLong and Numerical data types (https://github.com/non/spire), though Algebird does not include the required implicits for CMS-hashing (cf. CMSHasherImplicits.

Linear Supertypes
CommutativeMonoid[CMS[K]], CommutativeSemigroup[CMS[K]], Monoid[CMS[K]], AdditiveMonoid[CMS[K]], cats.kernel.Monoid[CMS[K]], Semigroup[CMS[K]], AdditiveSemigroup[CMS[K]], cats.kernel.Semigroup[CMS[K]], Serializable, AnyRef, Any
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. CMSMonoid
  2. CommutativeMonoid
  3. CommutativeSemigroup
  4. Monoid
  5. AdditiveMonoid
  6. Monoid
  7. Semigroup
  8. AdditiveSemigroup
  9. Semigroup
  10. Serializable
  11. AnyRef
  12. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. Protected

Instance Constructors

  1. new CMSMonoid(eps: Double, delta: Double, seed: Int, maxExactCountOpt: Option[Int] = None)(implicit arg0: CMSHasher[K])

    eps

    One-sided error bound on the error of each point query, i.e. frequency estimate.

    delta

    A bound on the probability that a query estimate does not lie within some small interval (an interval that depends on eps) around the truth.

    seed

    A seed to initialize the random number generator used to create the pairwise independent hash functions.

    maxExactCountOpt

    An Option parameter about how many exact counts a sparse CMS wants to keep.

Value Members

  1. final def !=(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  2. final def ##: Int
    Definition Classes
    AnyRef → Any
  3. final def ==(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  4. def additive: algebra.Monoid[CMS[K]]

    These are from algebra.Monoid

    These are from algebra.Monoid

    Definition Classes
    Monoid → AdditiveMonoid → Semigroup → AdditiveSemigroup
  5. final def asInstanceOf[T0]: T0
    Definition Classes
    Any
  6. def assertNotZero(v: CMS[K]): Unit
    Definition Classes
    Monoid
  7. def clone(): AnyRef
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.CloneNotSupportedException]) @native()
  8. def combine(l: CMS[K], r: CMS[K]): CMS[K]
    Definition Classes
    Semigroup → Semigroup
  9. def combineAll(t: TraversableOnce[CMS[K]]): CMS[K]
    Definition Classes
    Monoid → Monoid
  10. def combineAllOption(as: IterableOnce[CMS[K]]): Option[CMS[K]]
    Definition Classes
    Monoid → Semigroup
  11. def combineN(a: CMS[K], n: Int): CMS[K]
    Definition Classes
    Monoid → Semigroup
  12. def create(data: Seq[K]): CMS[K]

    Creates a sketch out of multiple items.

  13. def create(item: K): CMS[K]

    Creates a sketch out of a single item.

  14. def empty: CMS[K]
    Definition Classes
    Monoid → Monoid
  15. final def eq(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  16. def equals(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef → Any
  17. def finalize(): Unit
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.Throwable])
  18. final def getClass(): Class[_ <: AnyRef]
    Definition Classes
    AnyRef → Any
    Annotations
    @native()
  19. def hashCode(): Int
    Definition Classes
    AnyRef → Any
    Annotations
    @native()
  20. def isEmpty(a: CMS[K])(implicit ev: Eq[CMS[K]]): Boolean
    Definition Classes
    Monoid
  21. final def isInstanceOf[T0]: Boolean
    Definition Classes
    Any
  22. def isNonZero(v: CMS[K]): Boolean
    Definition Classes
    Monoid
  23. def isZero(a: CMS[K])(implicit ev: Eq[CMS[K]]): Boolean
    Definition Classes
    AdditiveMonoid
  24. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  25. def nonZeroOption(v: CMS[K]): Option[CMS[K]]
    Definition Classes
    Monoid
  26. final def notify(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native()
  27. final def notifyAll(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native()
  28. val params: CMSParams[K]
  29. def plus(left: CMS[K], right: CMS[K]): CMS[K]

    Combines the two sketches.

    Combines the two sketches.

    The sketches must use the same hash functions.

    Definition Classes
    CMSMonoid → AdditiveSemigroup
  30. def positiveSumN(a: CMS[K], n: Int): CMS[K]
    Attributes
    protected[this]
    Definition Classes
    AdditiveSemigroup
  31. def repeatedCombineN(a: CMS[K], n: Int): CMS[K]
    Attributes
    protected[this]
    Definition Classes
    Semigroup
  32. def sum(sketches: TraversableOnce[CMS[K]]): CMS[K]
    Definition Classes
    CMSMonoid → Monoid → AdditiveMonoid
  33. def sumN(a: CMS[K], n: Int): CMS[K]
    Definition Classes
    AdditiveMonoid → AdditiveSemigroup
  34. def sumOption(sketches: TraversableOnce[CMS[K]]): Option[CMS[K]]

    Returns an instance of T calculated by summing all instances in iter in one pass.

    Returns an instance of T calculated by summing all instances in iter in one pass. Returns None if iter is empty, else Some[T].

    returns

    None if iter is empty, else an option value containing the summed T

    Definition Classes
    CMSMonoid → Semigroup
    Note

    Override if there is a faster way to compute this sum than iter.reduceLeftOption using plus.

  35. final def synchronized[T0](arg0: => T0): T0
    Definition Classes
    AnyRef
  36. def toString(): String
    Definition Classes
    AnyRef → Any
  37. def trySum(as: TraversableOnce[CMS[K]]): Option[CMS[K]]
    Definition Classes
    AdditiveMonoid → AdditiveSemigroup
  38. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException])
  39. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException])
  40. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException]) @native()
  41. val zero: CMS[K]
    Definition Classes
    CMSMonoid → AdditiveMonoid

Inherited from CommutativeMonoid[CMS[K]]

Inherited from CommutativeSemigroup[CMS[K]]

Inherited from Monoid[CMS[K]]

Inherited from AdditiveMonoid[CMS[K]]

Inherited from cats.kernel.Monoid[CMS[K]]

Inherited from Semigroup[CMS[K]]

Inherited from AdditiveSemigroup[CMS[K]]

Inherited from cats.kernel.Semigroup[CMS[K]]

Inherited from Serializable

Inherited from AnyRef

Inherited from Any

Ungrouped