Class/Object

com.twitter.algebird

ExpHist

Related Docs: object ExpHist | package algebird

Permalink

case class ExpHist(conf: Config, buckets: Vector[Bucket], total: Long, time: Timestamp) extends Product with Serializable

Exponential Histogram algorithm from http://www-cs-students.stanford.edu/~datar/papers/sicomp_streams.pdf

An Exponential Histogram is a sliding window counter that can guarantee a bounded relative error. You configure the data structure with

- epsilon, the relative error you're willing to tolerate - windowSize, the number of time ticks that you want to track

You interact with the data structure by adding (number, timestamp) pairs into the exponential histogram. querying it for an approximate counts with guess.

The approximate count is guaranteed to be within conf.epsilon relative error of the true count seen across the supplied windowSize.

Next steps:

- efficient serialization - Query EH with a shorter window than the configured window - Discussion of epsilon vs memory tradeoffs

conf

the config values for this instance.

buckets

Vector of timestamps of each (powers of 2) ticks. This is the key to the exponential histogram representation. See ExpHist.Canonical for more info.

total

total ticks tracked. total == buckets.map(_.size).sum

time

current timestamp of this instance.

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

Instance Constructors

  1. new ExpHist(conf: Config, buckets: Vector[Bucket], total: Long, time: Timestamp)

    Permalink

    conf

    the config values for this instance.

    buckets

    Vector of timestamps of each (powers of 2) ticks. This is the key to the exponential histogram representation. See ExpHist.Canonical for more info.

    total

    total ticks tracked. total == buckets.map(_.size).sum

    time

    current timestamp of this instance.

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. def add(delta: Long, ts: Timestamp): ExpHist

    Permalink

    Increment ExpHist by delta at the supplied timestamp.

  5. def addAll(unsorted: Vector[Bucket]): ExpHist

    Permalink

    Efficiently add many buckets at once.

    Efficiently add many buckets at once.

    unsorted

    vector of buckets. All timestamps must be >= this.time.

    returns

    ExpHist instance with all buckets added, stepped forward to the max timestamp in unsorted.

  6. def approximateSum: Approximate[Long]

    Permalink

    Returns an Approximate instance encoding the bounds and the closest long to the estimated sum tracked by this instance.

  7. final def asInstanceOf[T0]: T0

    Permalink
    Definition Classes
    Any
  8. val buckets: Vector[Bucket]

    Permalink

    Vector of timestamps of each (powers of 2) ticks.

    Vector of timestamps of each (powers of 2) ticks. This is the key to the exponential histogram representation. See ExpHist.Canonical for more info.

  9. def clone(): AnyRef

    Permalink
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  10. val conf: Config

    Permalink

    the config values for this instance.

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

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

    Permalink
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( classOf[java.lang.Throwable] )
  13. def fold: Fold[Bucket, ExpHist]

    Permalink

    Returns a Fold instance that uses add to accumulate deltas into this exponential histogram instance.

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

    Permalink
    Definition Classes
    AnyRef → Any
  15. def guess: Double

    Permalink

    Estimate of the count seen across the last conf.windowSize timestamps.

    Estimate of the count seen across the last conf.windowSize timestamps. Guaranteed to be within conf.epsilon of the true count.

  16. def inc(ts: Timestamp): ExpHist

    Permalink

    Increment ExpHist by 1 at the supplied timestamp.

  17. final def isInstanceOf[T0]: Boolean

    Permalink
    Definition Classes
    Any
  18. def lowerBoundSum: Long

    Permalink

    Smallest possible count seen in the last conf.windowSize timestamps.

  19. final def ne(arg0: AnyRef): Boolean

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

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

    Permalink
    Definition Classes
    AnyRef
  22. def oldestBucketSize: Long

    Permalink
  23. def relativeError: Double

    Permalink

    relative error of guess, guaranteed to be <= conf.epsilon.

  24. def step(newTime: Timestamp): ExpHist

    Permalink

    Steps this instance forward to the new supplied time.

    Steps this instance forward to the new supplied time. Any buckets with a timestamp <= (newTime - conf.windowSize) will be evicted.

    newTime

    the new current time.

    returns

    ExpHist instance stepped forward to newTime.

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

    Permalink
    Definition Classes
    AnyRef
  26. val time: Timestamp

    Permalink

    current timestamp of this instance.

  27. val total: Long

    Permalink

    total ticks tracked.

    total ticks tracked. total == buckets.map(_.size).sum

  28. def upperBoundSum: Long

    Permalink

    Largest possible count seen in the last conf.windowSize timestamps.

  29. final def wait(): Unit

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

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

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

Inherited from Serializable

Inherited from Serializable

Inherited from Product

Inherited from Equals

Inherited from AnyRef

Inherited from Any

Ungrouped