Object/Class

com.twitter.algebird

ExpHist

Related Docs: class ExpHist | package algebird

Permalink

object ExpHist extends Serializable

Source
ExpHist.scala
Linear Supertypes
Serializable, Serializable, AnyRef, Any
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. ExpHist
  2. Serializable
  3. Serializable
  4. AnyRef
  5. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. All

Type Members

  1. case class Bucket(size: Long, timestamp: Timestamp) extends Product with Serializable

    Permalink

    size

    number of items tracked by this bucket.

    timestamp

    timestamp of the most recent item tracked by this bucket.

  2. final case class CanonicalVector(rep: Vector[Int]) extends AnyVal with Product with Serializable

    Permalink
  3. case class Config(epsilon: Double, windowSize: Long) extends Product with Serializable

    Permalink

    ExpHist guarantees that the returned guess will be within epsilon relative error of the true count across a sliding window of size windowSize.

    ExpHist guarantees that the returned guess will be within epsilon relative error of the true count across a sliding window of size windowSize.

    epsilon

    relative error, from [0, 0.5]

    windowSize

    number of time ticks to track

  4. final case class Timestamp(toLong: Long) extends AnyVal with Product with Serializable

    Permalink

    Value class wrapper around timestamps (>= 0) used by each bucket.

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. object Bucket extends Serializable

    Permalink
  5. object Canonical

    Permalink

    The paper that introduces the exponential histogram proves that, given a positive number l, every integer s can be uniquely represented as the sum of

    The paper that introduces the exponential histogram proves that, given a positive number l, every integer s can be uniquely represented as the sum of

    (l or (l + 1)) * 2i + (# from 1 to (l + 1)) 2j

    for i = (0 to j - 1), given some j.

    The paper calls this the "l-canonical" representation of s.

    It turns out that if you follow the exponential histogram bucket-merging algorithm, you end up with the invariant that the number of buckets with size 2^i exactly matches that power of 2's coefficient in s's l-canonical representation.

    Put another way - only sequences of buckets with sizes matching the l-canonical representation of some number s are valid exponential histograms.

    (We use this idea in ExpHist.rebucket to take a sequence of buckets of any size and rebucket them into a sequence where the above invariant holds.)

    This is huge. This means that you can implement addAll(newBuckets) by

    - calculating newS = s + delta contributed by newBuckets - generating the l-canonical sequence of bucket sizes for newS - rebucketing newBuckets ++ oldBuckets into those bucket sizes

    The resulting sequence of buckets is a valid exponential histogram.

  6. object Timestamp extends Serializable

    Permalink
  7. final def asInstanceOf[T0]: T0

    Permalink
    Definition Classes
    Any
  8. def clone(): AnyRef

    Permalink
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  9. def empty(conf: Config): ExpHist

    Permalink

    Returns an empty instance with the supplied Config.

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

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

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

    Permalink
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( classOf[java.lang.Throwable] )
  13. def from(i: Long, ts: Timestamp, conf: Config): ExpHist

    Permalink

    Returns an instance directly from a number i.

    Returns an instance directly from a number i. All buckets in the returned ExpHist will have the same timestamp, equal to ts.

  14. final def getClass(): Class[_]

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

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

    Permalink
    Definition Classes
    Any
  17. final def ne(arg0: AnyRef): Boolean

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

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

    Permalink
    Definition Classes
    AnyRef
  20. final def synchronized[T0](arg0: ⇒ T0): T0

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

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

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

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

    Permalink
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )

Inherited from Serializable

Inherited from Serializable

Inherited from AnyRef

Inherited from Any

Ungrouped