ExpHist

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

Instance Constructors

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

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

final def !=(arg0: Any): Boolean

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

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

Definition Classes
AnyRef → Any
def add(delta: Long, ts: Timestamp): ExpHist

Increment ExpHist by delta at the supplied timestamp.
def addAll(unsorted: Vector[Bucket]): ExpHist

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.
def approximateSum: Approximate[Long]

Returns an Approximate instance encoding the bounds and the closest long to the estimated sum tracked by this instance.
final def asInstanceOf[T0]: T0

Definition Classes
Any
val buckets: Vector[Bucket]

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.
def clone(): AnyRef

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

the config values for this instance.
final def eq(arg0: AnyRef): Boolean

Definition Classes
AnyRef
def finalize(): Unit

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

Returns a Fold instance that uses add to accumulate deltas into this exponential histogram instance.
final def getClass(): Class[_]

Definition Classes
AnyRef → Any
def guess: Double

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.
def inc(ts: Timestamp): ExpHist

Increment ExpHist by 1 at the supplied timestamp.
final def isInstanceOf[T0]: Boolean

Definition Classes
Any
def lowerBoundSum: Long

Smallest possible count seen in the last conf.windowSize timestamps.
final def ne(arg0: AnyRef): Boolean

Definition Classes
AnyRef
final def notify(): Unit

Definition Classes
AnyRef
final def notifyAll(): Unit

Definition Classes
AnyRef
def oldestBucketSize: Long
def relativeError: Double

relative error of guess, guaranteed to be <= conf.epsilon.
def step(newTime: Timestamp): ExpHist

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.
final def synchronized[T0](arg0: ⇒ T0): T0

Definition Classes
AnyRef
val time: Timestamp

current timestamp of this instance.
val total: Long

total ticks tracked.
total ticks tracked. total == buckets.map(_.size).sum
def upperBoundSum: Long

Largest possible count seen in the last conf.windowSize timestamps.
final def wait(): Unit

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

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

Definition Classes
AnyRef
Annotations
@throws( ... )

Related Docs: object ExpHist | package algebird

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

Instance Constructors

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

Value Members

final def !=(arg0: Any): Boolean

final def ##(): Int

final def ==(arg0: Any): Boolean

def add(delta: Long, ts: Timestamp): ExpHist

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

def approximateSum: Approximate[Long]

final def asInstanceOf[T0]: T0

val buckets: Vector[Bucket]

def clone(): AnyRef

val conf: Config

final def eq(arg0: AnyRef): Boolean

def finalize(): Unit

def fold: Fold[Bucket, ExpHist]

final def getClass(): Class[_]

def guess: Double

def inc(ts: Timestamp): ExpHist

final def isInstanceOf[T0]: Boolean

def lowerBoundSum: Long

final def ne(arg0: AnyRef): Boolean

final def notify(): Unit

final def notifyAll(): Unit

def oldestBucketSize: Long

def relativeError: Double

def step(newTime: Timestamp): ExpHist

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

val time: Timestamp

val total: Long

def upperBoundSum: Long

final def wait(): Unit

final def wait(arg0: Long, arg1: Int): Unit

final def wait(arg0: Long): Unit

Inherited from Serializable

Inherited from Serializable

Inherited from Product

Inherited from Equals

Inherited from AnyRef

Inherited from Any

Ungrouped