Hokusai - Sketching Streams in Real Time

Sergiy Matusevych, Alexander J. Smola, Amr Ahmed

In the world of big data, "now" is easy, but "then" is expensive. If you want to know how many times a specific search query appeared in the last five minutes, a standard sketch algorithm can tell you instantly. But what if you want to know how many times a specific term was searched at exactly noon on a specific day three years ago? Traditionally, this requires digging through terabytes of historical log files—a process that takes minutes or hours, not milliseconds.

The paper "Hokusai — Sketching Streams in Real Time" by Matusevych, Smola, and Ahmed introduces a system designed to solve this. Named after the famous Japanese artist known for "The Great Wave," Hokusai "sketches" data streams to provide real-time historical frequency estimates with a remarkably small memory footprint.

The Challenge of Historical Streams

Data scientists often need to query the frequency of items (like URLs, queries, or IP addresses) over arbitrary time intervals. While the Count-Min Sketch (CMS) is a standard tool for estimating frequencies in a stream, it typically only provides a "total count so far."

To get historical "point-in-time" data, one would theoretically need to save a snapshot of the sketch every minute. For a system running for years, storing these snapshots in RAM would require terabytes of space, making real-time retrieval impossible. Hokusai addresses the challenge: How do we store years of historical frequency data in a way that fits in RAM and remains queryable in constant time?

Methods: Aggregation and Extrapolation

Hokusai builds on the linearity of the Count-Min Sketch. Because sketches can be added together to represent the union of two time periods, the authors employ three main strategies to manage memory:

Time Aggregation

Instead of keeping every minute's sketch, Hokusai uses a binary aggregation strategy. It keeps sketches for the last $2^0, 2^1, 2^2 \dots$ minutes. As data ages, its time resolution becomes coarser, but the number of sketches to store only grows logarithmically with time.

Binary time aggregation strategy used in Hokusai to store historical data logarithmically.

Item Aggregation (Bit Folding)

To save even more space, Hokusai reduces the "item resolution" of older sketches. By "folding" a sketch (summing its halves), they effectively reduce the bit-depth of the hash functions. Older data becomes more "blurry" (higher collision probability), but takes up significantly less RAM.

Resolution Extrapolation and Markovian Approximations

To estimate a high-resolution count for a past event where only coarse data exists, Hokusai assumes a degree of statistical independence. It uses the marginal counts of the item ($n_x$) and the time bucket ($n_t$) to interpolate the specific count ($n_{xt}$) using the formula $n(x,t) \approx \frac{n_x \cdot n_t}{n}$. For complex sequences like trigrams, Hokusai uses bigram and unigram marginals to estimate counts, avoiding the need to store massive, sparse trigram sketches directly.

Evaluation and Results

The authors evaluated Hokusai using large-scale datasets, including a proprietary web query dataset (378M observations) and a textual dump of English Wikipedia (1.29B tokens).

  • High Throughput: The system handled over 50,000 inserts per second and supported roughly 22,000 read requests per second.
  • Accuracy: For "heavy hitters" (frequent items), the estimates were virtually indistinguishable from the ground truth. Even for lower-frequency items, the interpolation provided a robust baseline.
Comparison of Hokusai sketch results against exact counts for a popular web query over five days.
  • Multigram Efficiency: Using bigram approximations to estimate trigram counts resulted in less than 15% error compared to direct sketching, while requiring orders of magnitude less memory.

Conclusion

Hokusai demonstrates that by accepting a graceful degradation in precision for older data, we can achieve exponential history storage in linear space. Its use of linearity for folding and summing allows for efficient compression without re-processing raw data, making it a powerful tool for real-time stream analysis. While the interpolation method can struggle with highly non-stationary data, it provides a scalable and efficient solution for tracking the pulse of massive data streams.

Summary updated

BibTeX
@inproceedings{matusevych2012hokusai,
  author = {Sergiy Matusevych and Alexander J. Smola and Amr Ahmed},
  title = {{Hokusai - Sketching Streams in Real Time}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2012},
}
Figure