Packages

object ExpHist extends Serializable

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

Type Members

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

    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
  3. case class Config(epsilon: Double, windowSize: Long) extends Product with Serializable

    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

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

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. final def asInstanceOf[T0]: T0
    Definition Classes
    Any
  5. def clone(): AnyRef
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.CloneNotSupportedException]) @native()
  6. def empty(conf: Config): ExpHist

    Returns an empty instance with the supplied Config.

  7. final def eq(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  8. def equals(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef → Any
  9. def finalize(): Unit
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.Throwable])
  10. def from(i: Long, ts: Timestamp, conf: Config): ExpHist

    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.

  11. final def getClass(): Class[_ <: AnyRef]
    Definition Classes
    AnyRef → Any
    Annotations
    @native()
  12. def hashCode(): Int
    Definition Classes
    AnyRef → Any
    Annotations
    @native()
  13. final def isInstanceOf[T0]: Boolean
    Definition Classes
    Any
  14. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  15. final def notify(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native()
  16. final def notifyAll(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native()
  17. final def synchronized[T0](arg0: => T0): T0
    Definition Classes
    AnyRef
  18. def toString(): String
    Definition Classes
    AnyRef → Any
  19. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException])
  20. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException])
  21. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException]) @native()
  22. object Bucket extends Serializable
  23. object Canonical

    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.

  24. object Timestamp extends Serializable

Inherited from Serializable

Inherited from AnyRef

Inherited from Any

Ungrouped