Skip to content

algorithm.md

Latest commit

 

History

History
105 lines (64 loc) · 6.76 KB

algorithm.md

File metadata and controls

105 lines (64 loc) · 6.76 KB
Raw

Algorithm Internals

This document explains how the Zhang-Wang (ZW) fast approximate quantile algorithm works, as implemented in this crate.

Background

Computing exact quantiles over a data stream requires storing all elements and sorting them — O(n) space and O(n log n) time. For large or unbounded streams, this is impractical. Approximate quantile algorithms trade a bounded error tolerance (epsilon) for dramatically reduced memory usage.

The ZW algorithm, described in Zhang & Wang, SSDBM 2007, achieves O((1/epsilon) * log(epsilon * n)) space with O(log(1/epsilon)) amortized update time.

Core Concepts

Rank and Epsilon Guarantee

For a stream of n elements, querying rank r (where 0.0 <= r <= 1.0) should return the element at position floor(r * n) in the sorted order. The epsilon guarantee means the returned element's true rank is within [r - epsilon, r + epsilon], i.e., within epsilon * n positions of the exact answer.

RankInfo

Each element in a summary is stored as a RankInfo<T> tuple:

RankInfo { val: T, rmin: i64, rmax: i64 }
  • val — the data element
  • rmin — the minimum possible rank of this element
  • rmax — the maximum possible rank of this element

Ranks are one-based throughout the crate, matching the paper: a freshly sorted block of b elements gets rmin = rmax = 1, 2, ..., b. The interval [rmin, rmax] captures the uncertainty introduced by compression. As summaries are merged and compressed, these bounds widen but remain within the epsilon guarantee.

Operations

Update (Insertion)

New elements are inserted into a level-0 buffer (s[0]). When this buffer reaches the block size b:

  1. Sort the buffer and assign exact one-based ranks (rmin = rmax = position).
  2. Compress the sorted buffer to roughly b/2 entries by selecting a subset that preserves the rank coverage.
  3. Propagate the compressed summary upward through levels: if level k is empty, store there; otherwise, take the summary stored at level k, merge it with the incoming one, compress the result, and continue to level k+1.

This cascading merge is analogous to binary counting — level k is "full" roughly every 2^k blocks, giving logarithmic levels.

Merge

Merging two sorted summaries S_a and S_b produces a combined summary S_m where each element's rank bounds are updated to account for elements from the other summary. For an element e from S_a, let pred be the largest element of S_b below e and succ the smallest element of S_b above it:

  • rmin: rmin_a(e) + rmin_b(pred), or just rmin_a(e) when there is no predecessor.
  • rmax: rmax_a(e) + rmax_b(succ) - 1, or rmax_a(e) + rmax_b(pred) when there is no successor.

These are the one-based formulas from the paper; they only hold because sorted blocks are ranked from 1. The merge proceeds like a standard sorted-list merge, advancing through both inputs in order and moving elements rather than cloning them whenever the input is owned.

Compress

Compression reduces a summary of size n to at most block_size + 1 entries while preserving the epsilon guarantee. It works by:

  1. Computing s0_range, the maximum rmax in the summary.
  2. Dividing the rank space [0, s0_range] into block_size equal intervals.
  3. For each interval boundary, selecting the first element whose rmax reaches or exceeds that boundary.

This ensures uniform coverage of the rank space. Every input to compress must already satisfy the precision condition 2 * epsilon * range >= max(rmax - rmin); the constructor's block sizing guarantees it, and debug builds assert it.

Query

Querying rank r on a summary of n elements:

  1. Compute the one-based target rank: rank = min(floor(r * n) + 1, n).
  2. Compute the error window: epsilon_n = floor(epsilon * n).
  3. Build a merged summary S_m from all levels (cached after the first build, invalidated on update).
  4. Binary search for the first element with rmin >= rank, then scan forward while rmin <= rank + epsilon_n for an element with rmax <= rank + epsilon_n.
  5. If none is found, scan backward over the elements with rmin >= rank - epsilon_n; any of them with rmax <= rank + epsilon_n also satisfies the guarantee.
  6. As a last resort, return the element whose rank interval is centred closest to rank. This never happens for summaries built by the crate, but it keeps a query from silently returning the maximum element.

FixedSizeEpsilonSummary

When the stream size n is known upfront and epsilon * n > 8:

  • Block size b = floor(log2(epsilon * n) / epsilon)
  • Number of levels = bit width of floor(n / b), plus one for level 0. Full blocks propagate through the levels like binary carries, so the level count is the number of bits needed to count them.

When epsilon * n <= 8 the summary switches to exact mode: a single level with b = n + 1 that never fills, so every element is kept and queries are exact. The ZW block size is only meaningful once log2(epsilon * n) is comfortably above 1; below that the derived blocks become too small (down to a single element) and neither the precision condition nor the rank-error guarantee can hold. Exact mode costs at most 8 / epsilon stored elements, the same order as a single block.

UnboundEpsilonSummary

When the stream size is unknown, the algorithm uses a doubling strategy:

  1. Maintain a "current" FixedSizeEpsilonSummary (s_c) sized for the current sub-stream.
  2. Sub-stream boundaries lie at positions floor((2^x - 1) / epsilon) for x = 1, 2, ...; the next boundary is computed on demand and tracked with a counter, so there is no table to exhaust.
  3. When the count reaches boundary x:
    • Finalize s_c (compress all its levels into a single summary).
    • Push s_c onto a list of completed summaries.
    • Create a new s_c sized for the interval up to boundary x + 1.
  4. At query time, merge all completed summaries with the current s_c.

Each sub-stream summary is built with epsilon / 2, so the merged result stays within epsilon overall. Short sub-streams (epsilon * n_i <= 8) use exact mode like any other fixed-size summary.

Query Caching

Both summary types cache the merged summary (cached_s_m) using RefCell<Option<...>>. This allows query() to take &self (immutable reference) while lazily computing and caching the merged result. The cache is invalidated on every update() call.

Space Complexity

  • FixedSizeEpsilonSummary: O((1/epsilon) * log(epsilon * n)) elements stored across all levels.
  • UnboundEpsilonSummary: O((1/epsilon) * log^2(epsilon * n)) due to the list of completed summaries.

In practice, for epsilon = 0.01 and n = 1,000,000, the summaries store a few thousand entries rather than the full million.