{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T17:30:52Z","timestamp":1783791052369,"version":"3.55.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,4,28]],"date-time":"2025-04-28T00:00:00Z","timestamp":1745798400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2025,4,28]]},"abstract":"<jats:p>A key need in different disciplines is to perform analytics over fast-paced data streams, similar in nature to the traditional OLAP analytics in relational databases, i.e., with filters and aggregates. Storing unbounded streams, however, is not a realistic approach due to the high storage requirements, and the delays introduced when storing massive data. Accordingly, many synopses\/sketches have been proposed that can summarize the stream in small memory (usually sufficiently small to be stored in RAM), such that aggregate queries can be efficiently approximated, without storing the full stream. However, past synopses predominantly focus on summarizing single-attribute streams, and cannot handle filters and constraints on arbitrary subsets of multiple attributes efficiently. We propose OmniSketch, the first sketch that scales to fast-paced and complex data streams (with many attributes), and supports count aggregates with filters on multiple attributes, dynamically chosen at query time. The sketch offers probabilistic error guarantees, a favorable space\/accuracy trade-off, and a worst-case logarithmic complexity for updating and for query execution. We demonstrate experimentally with real and synthetic data that the sketch outperforms the state-of-the-art, and that it can approximate complex ad-hoc queries within the configured accuracy guarantees, with small memory requirements.<\/jats:p>","DOI":"10.1145\/3733620.3733627","type":"journal-article","created":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T16:20:07Z","timestamp":1745943607000},"page":"28-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["OmniSketch: Streaming Data Analytics with Arbitrary Predicates"],"prefix":"10.1145","volume":"54","author":[{"given":"Wieger R.","family":"Punter","sequence":"first","affiliation":[{"name":"Eindhoven University of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Odysseas","family":"Papapetrou","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Minos","family":"Garofalakis","sequence":"additional","affiliation":[{"name":"ATHENA Research Center &amp; Technical Univ. of Crete"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,4,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_3_1","volume-title":"Histograms, Wavelets, Sketches. Found. Trends Databases, 4(1--3):1--294","author":"Cormode Graham","year":"2012","unstructured":"Graham Cormode, Minos N. Garofalakis, Peter J. Haas, and Christopher M. Jermaine. Synopses for massive data: Samples, Histograms, Wavelets, Sketches. Found. Trends Databases, 4(1--3):1--294, 2012."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476276"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings","volume":"07","author":"Flajolet Philippe","year":"2007","unstructured":"Philippe Flajolet, \u00b4Eric Fusy, Olivier Gandouet, and Fr\u00b4ed\u00b4eric Meunier. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. Discrete Mathematics & Theoretical Computer Science, Proceedings vol. AH, AofA 07, 2007."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-004-0135-3"},{"key":"e_1_2_1_8_1","first-page":"541","volume-title":"VLDB","author":"Gibbons Phillip B.","year":"2001","unstructured":"Phillip B. Gibbons. Distinct sampling for highly-accurate answers to distinct values queries and event reports. In VLDB 2001, page 541--550."},{"key":"e_1_2_1_9_1","first-page":"454","volume-title":"VLDB","author":"Gilbert Anna C.","year":"2002","unstructured":"Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, and Martin J. Strauss. How to summarize the universe: Dynamic maintenance of quantiles. In VLDB 2002, page 454--465."},{"key":"e_1_2_1_10_1","unstructured":"David Kotz Tristan Henderson Ilya Abyzov and Jihwang Yeo. CRAWDAD Dartmouth\/campus (v. 2009-09-09) 2022."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461553"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3594512.3594526"},{"key":"e_1_2_1_13_1","first-page":"671","volume-title":"WWW","author":"Li Ping","year":"2010","unstructured":"Ping Li and Arnd Christian K\u00a8onig. b-Bit minwise hashing. In WWW 2010, pages 671--680."},{"key":"e_1_2_1_14_1","volume-title":"Art B. Owen, and Cun-Hui Zhang. One permutation hashing for efficient search and learning. CoRR, abs\/1208.1259","author":"Li Ping","year":"2012","unstructured":"Ping Li, Art B. Owen, and Cun-Hui Zhang. One permutation hashing for efficient search and learning. CoRR, abs\/1208.1259, 2012."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2934872.2934906"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551867"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781933019604"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594554"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3632093.3632098"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3733620.3733627","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3733620.3733627","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:56:55Z","timestamp":1750298215000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3733620.3733627"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,28]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,4,28]]}},"alternative-id":["10.1145\/3733620.3733627"],"URL":"https:\/\/doi.org\/10.1145\/3733620.3733627","relation":{},"ISSN":["0163-5808"],"issn-type":[{"value":"0163-5808","type":"print"}],"subject":[],"published":{"date-parts":[[2025,4,28]]},"assertion":[{"value":"2025-04-29","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}