Class

com.twitter.algebird

CMSMonoid

Related Doc: package algebird

Permalink

class CMSMonoid[K] extends Monoid[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 scala.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 scala.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.

Source
CountMinSketch.scala
Linear Supertypes
Monoid[CMS[K]], Semigroup[CMS[K]], Serializable, AnyRef, Any
Type Hierarchy
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. CMSMonoid
  2. Monoid
  3. Semigroup
  4. Serializable
  5. AnyRef
  6. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. All

Instance Constructors

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

    Permalink

    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

    Permalink
    Definition Classes
    AnyRef → Any
  2. final def ##(): Int

    Permalink
    Definition Classes
    AnyRef → Any
  3. final def ==(arg0: Any): Boolean

    Permalink
    Definition Classes
    AnyRef → Any
  4. final def asInstanceOf[T0]: T0

    Permalink
    Definition Classes
    Any
  5. def assertNotZero(v: CMS[K]): Unit

    Permalink
    Definition Classes
    Monoid
  6. def clone(): AnyRef

    Permalink
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  7. def create(data: Seq[K]): CMS[K]

    Permalink

    Creates a sketch out of multiple items.

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

    Permalink

    Creates a sketch out of a single item.

  9. final def eq(arg0: AnyRef): Boolean

    Permalink
    Definition Classes
    AnyRef
  10. def equals(arg0: Any): Boolean

    Permalink
    Definition Classes
    AnyRef → Any
  11. def finalize(): Unit

    Permalink
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( classOf[java.lang.Throwable] )
  12. final def getClass(): Class[_]

    Permalink
    Definition Classes
    AnyRef → Any
  13. def hashCode(): Int

    Permalink
    Definition Classes
    AnyRef → Any
  14. final def isInstanceOf[T0]: Boolean

    Permalink
    Definition Classes
    Any
  15. def isNonZero(v: CMS[K]): Boolean

    Permalink
    Definition Classes
    Monoid
  16. final def ne(arg0: AnyRef): Boolean

    Permalink
    Definition Classes
    AnyRef
  17. def nonZeroOption(v: CMS[K]): Option[CMS[K]]

    Permalink
    Definition Classes
    Monoid
  18. final def notify(): Unit

    Permalink
    Definition Classes
    AnyRef
  19. final def notifyAll(): Unit

    Permalink
    Definition Classes
    AnyRef
  20. val params: CMSParams[K]

    Permalink
  21. def plus(left: CMS[K], right: CMS[K]): CMS[K]

    Permalink

    Combines the two sketches.

    Combines the two sketches.

    The sketches must use the same hash functions.

    returns

    result of combining l and r

    Definition Classes
    CMSMonoidSemigroup
  22. def sum(sketches: TraversableOnce[CMS[K]]): CMS[K]

    Permalink
    Definition Classes
    CMSMonoidMonoid
  23. def sumOption(sketches: TraversableOnce[CMS[K]]): Option[CMS[K]]

    Permalink

    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
    CMSMonoidSemigroup
    Note

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

  24. final def synchronized[T0](arg0: ⇒ T0): T0

    Permalink
    Definition Classes
    AnyRef
  25. def toString(): String

    Permalink
    Definition Classes
    AnyRef → Any
  26. final def wait(): Unit

    Permalink
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  27. final def wait(arg0: Long, arg1: Int): Unit

    Permalink
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  28. final def wait(arg0: Long): Unit

    Permalink
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  29. val zero: CMS[K]

    Permalink

    Returns the identity element of T for plus.

    Returns the identity element of T for plus.

    Definition Classes
    CMSMonoidMonoid

Inherited from Monoid[CMS[K]]

Inherited from Semigroup[CMS[K]]

Inherited from Serializable

Inherited from AnyRef

Inherited from Any

Ungrouped