2012/10/16 by Sergiy Matusevych, Alex Smola, Matusevych, Sergiy +3 · 10 citations
Computer Science · Mathematics · #Advanced Database Systems and Queries #Algorithm #Algorithms and Data Compression #Basis (linear algebra) #Computer science #Constant (computer programming) #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #Databases (cs.DB) #Exploit #FOS: Computer and information sciences #Function (biology) #Mathematics #Operating system #Point (geometry) #Programming language #STREAMS #Sketch #Theoretical computer science #Time complexity #cs.DB #cs.DS
paper · pdf · doi:10.48550/arxiv.1210.4891
published in arXiv (Cornell University), 594-603 (Cornell University) · Appears in Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence (UAI2012)
arxiv created 2012/10/16 · openalex publication_date 2012/10/16 · arxiv updated 2012/10/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08
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.