final class CMS extends Serializable
The idealized formula for the updating current value for a key (y0 -> y1) is given as:
delta = (t1 - t0) / halflife y1 = y0 * 2^(-delta) + n
However, we want to avoid having to rescale every single cell every time we update; i.e. a cell with a zero value should continue to have a zero value when n=0.
Therefore, we introduce a change of variable to cell values (z) along with a scale factor (scale), and the following formula:
(1) zN = yN * scaleN
Our constraint is expressed as:
(2) If n=0, z1 = z0
In that case:
(3) If n=0, (y1 * scale1) = (y0 * scale0) (4) Substituting for y1, (y0 * 2(-delta) + 0) * scale1 = y0 * scale0 (5) 2(-delta) * scale1 = scale0 (6) scale1 = scale0 * 2^(delta)
Also, to express z1 in terms of z0, we say:
(7) z1 = y1 * scale1 (8) z1 = (y0 * 2(-delta) + n) * scale1 (9) z1 = ((z0 / scale0) * 2(-delta) + n) * scale1 (10) z1 / scale1 = (z0 / (scale1 * 2(-delta))) * 2(-delta) + n (11) z1 / scale1 = z0 / scale1 + n (12) z1 = z0 + n * scale1
So, for cells where n=0, we just update scale0 to scale1, and for cells where n is non-zero, we update z1 in terms of z0 and scale1.
If we convert scale to logscale, we have:
(13) logscale1 = logscale0 + delta * log(2) (14) z1 = z0 + n * exp(logscale1)
When logscale1 gets big, we start to distort z1. For example, exp(36) is close to 2^53. We can measure when n * exp(logscale1) gets big, and in those cases we can rescale all our cells (set each z to its corresponding y) and set the logscale to 0.
(15) y1 = z1 / scale1 (16) y1 = z1 / exp(logscale1) (17) y1 = z1 * exp(-logscale1)
- Alphabetic
- By Inheritance
- CMS
- Serializable
- AnyRef
- Any
- Hide All
- Show All
- Public
- Protected
Instance Constructors
- new CMS(cells: Array[Vector[Double]], logScale: Double, timeInHL: Double)
Value Members
- final def !=(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
- final def ##: Int
- Definition Classes
- AnyRef → Any
- def +(other: CMS): CMS
- final def ==(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
- def add(t: Long, k: K, n: Double): CMS
- final def asInstanceOf[T0]: T0
- Definition Classes
- Any
- def bulkAdd(items: Iterable[(Long, K, Double)]): CMS
- val cells: Array[Vector[Double]]
- def clone(): AnyRef
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.CloneNotSupportedException]) @native()
- final def eq(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- def equals(any: Any): Boolean
- Definition Classes
- CMS → AnyRef → Any
- def finalize(): Unit
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.Throwable])
- def get(k: K): DoubleAt
- final def getClass(): Class[_ <: AnyRef]
- Definition Classes
- AnyRef → Any
- Annotations
- @native()
- def getScale(t: Double): Double
- def hashCode(): Int
- Definition Classes
- CMS → AnyRef → Any
- def innerProductRoot(that: CMS): DoubleAt
Returns the square-root of the inner product of two decaying CMSs.
Returns the square-root of the inner product of two decaying CMSs.
We want the result to decay at the same rate as the CMS for this method to be valid. Taking the square root ensures that this is true. Without it, we would violate the following equality (assuming we had at() on a CMS):
x.innerProduct(y).at(t) = x.at(t).innerProduct(y.at(t))
This is why we don't support innerProduct, only innerProductRoot.
- final def isInstanceOf[T0]: Boolean
- Definition Classes
- Any
- def l2Norm: DoubleAt
- def lastUpdateTime: Long
- val logScale: Double
- 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 range: (DoubleAt, DoubleAt)
Provide lower and upper bounds on values returned for any possible key.
Provide lower and upper bounds on values returned for any possible key.
The first value is a lower bound: even keys that have never been counted will return this value or greater. This will be zero unless the CMS is saturated.
The second value is an upper bound: the key with the largest cardinality will not be reported as being larger than this value (though it might be reported as being smaller).
Together these values indicate how saturated and skewed the CMS might be.
- def scale(x: Double): CMS
- final def synchronized[T0](arg0: => T0): T0
- Definition Classes
- AnyRef
- val timeInHL: Double
- def toString(): String
- Definition Classes
- CMS → AnyRef → Any
- def total: DoubleAt
Get the total count of all items in the CMS.
Get the total count of all items in the CMS.
The total is the same as the l1Norm, since we don't allow negative values.
Total is one of the few non-approximate statistics that DecayingCMS supports. We expect the total to be exact (except for floating-point error).
- 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()