Hokusai - Sketching Streams in Real Time

Sergiy Matusevych, Alex Smola, Amr Ahmed
Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, PMLR R10:592-601, 2012.

Abstract

We describe Hokusai, a real time system which is able to capture frequency information for streams of arbitrary sequences of symbols. The algorithm uses the CountMin sketch as its basis and exploits the fact that sketching is linear. It provides real time statistics of arbitrary events, e.g. streams of queries as a function of time. We use a factorizing approximation to provide point estimates at arbitrary (time, item) combinations. Queries can be answered in constant time.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR10-matusevych12a, title = {Hokusai - Sketching Streams in Real Time}, author = {Matusevych, Sergiy and Smola, Alex and Ahmed, Amr}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {592--601}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/matusevych12a/matusevych12a.pdf}, url = {https://proceedings.mlr.press/r10/matusevych12a.html}, abstract = {We describe Hokusai, a real time system which is able to capture frequency information for streams of arbitrary sequences of symbols. The algorithm uses the CountMin sketch as its basis and exploits the fact that sketching is linear. It provides real time statistics of arbitrary events, e.g. streams of queries as a function of time. We use a factorizing approximation to provide point estimates at arbitrary (time, item) combinations. Queries can be answered in constant time.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Hokusai - Sketching Streams in Real Time %A Sergiy Matusevych %A Alex Smola %A Amr Ahmed %B Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2012 %E Nando de Freitas %E Kevin Murphy %F pmlr-vR10-matusevych12a %I PMLR %P 592--601 %U https://proceedings.mlr.press/r10/matusevych12a.html %V R10 %X We describe Hokusai, a real time system which is able to capture frequency information for streams of arbitrary sequences of symbols. The algorithm uses the CountMin sketch as its basis and exploits the fact that sketching is linear. It provides real time statistics of arbitrary events, e.g. streams of queries as a function of time. We use a factorizing approximation to provide point estimates at arbitrary (time, item) combinations. Queries can be answered in constant time. %Z Reissued by PMLR on 04 October 2026.
APA
Matusevych, S., Smola, A. & Ahmed, A.. (2012). Hokusai - Sketching Streams in Real Time. Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R10:592-601 Available from https://proceedings.mlr.press/r10/matusevych12a.html. Reissued by PMLR on 04 October 2026.

Related Material