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.
- Alphabetic
- By Inheritance
- ExpHist
- Serializable
- Product
- Equals
- AnyRef
- Any
- Hide All
- Show All
- Public
- Protected
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]
- def clone(): AnyRef
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.CloneNotSupportedException]) @native()
- val conf: Config
- final def eq(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- def finalize(): Unit
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.Throwable])
- def fold: Fold[Bucket, ExpHist]
Returns a Fold instance that uses
addto accumulate deltas into this exponential histogram instance. - final def getClass(): Class[_ <: AnyRef]
- Definition Classes
- AnyRef → Any
- Annotations
- @native()
- 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
- Annotations
- @native()
- final def notifyAll(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native()
- def oldestBucketSize: Long
- def productElementNames: Iterator[String]
- Definition Classes
- Product
- 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
- def toString(): String
- Definition Classes
- ExpHist → AnyRef → Any
- val total: Long
- def upperBoundSum: Long
Largest possible count seen in the last conf.windowSize timestamps.
- final def wait(): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException])
- final def wait(arg0: Long, arg1: Int): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException])
- final def wait(arg0: Long): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException]) @native()