{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,8]],"date-time":"2026-08-08T17:42:55Z","timestamp":1786210975121,"version":"3.56.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,11]]},"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, or desired 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. In this work, 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 guarantees, a favorable space-accuracy tradeoff, and a worst-case logarithmic complexity for updating and for query execution. We demonstrate experimentally with both 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.14778\/3632093.3632098","type":"journal-article","created":{"date-parts":[[2024,1,20]],"date-time":"2024-01-20T11:26:31Z","timestamp":1705749991000},"page":"319-331","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["OmniSketch: Efficient Multi-Dimensional High-Velocity Stream Analytics with Arbitrary Predicates"],"prefix":"10.14778","volume":"17","author":[{"given":"Wieger R.","family":"Punter","sequence":"first","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Odysseas","family":"Papapetrou","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, The Netherlands"}],"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":[[2024,1,20]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2011. The CAIDA UCSD Anonymized Internet Traces. https:\/\/www.caida.org\/catalog\/datasets\/passive_dataset"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_3_1","first-page":"7","article-title":"Space\/Time Trade-Offs in Hash Coding with Allowable","volume":"13","author":"Bloom Burton H.","year":"1970","unstructured":"Burton H. Bloom. 1970. Space\/Time Trade-Offs in Hash Coding with Allowable Errors. Commun. ACM 13, 7 (jul 1970), 422--426.","journal-title":"Errors. Commun. ACM"},{"key":"e_1_2_1_4_1","volume-title":"29th International Colloquium, ICALP 2002 (Lecture Notes in Computer Science)","volume":"2380","author":"Charikar Moses","year":"2002","unstructured":"Moses Charikar, Kevin C. Chen, and Martin Farach-Colton. 2002. Finding Frequent Items in Data Streams. In Automata, Languages and Programming, 29th International Colloquium, ICALP 2002 (Lecture Notes in Computer Science), Vol. 2380. Springer, 693--703."},{"key":"e_1_2_1_5_1","first-page":"1","article-title":"Synopses for Massive Data: Samples, Histograms, Wavelets","volume":"4","author":"Cormode Graham","year":"2012","unstructured":"Graham Cormode, Minos Garofalakis, Peter J. Haas, and Christopher M. Jermaine. 2012. Synopses for Massive Data: Samples, Histograms, Wavelets, Sketches. Foundations and Trends in Databases 4, 1--3 (2012), 1--294.","journal-title":"Sketches. Foundations and Trends in Databases"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_7_1","first-page":"1","article-title":"A Framework for Estimating Stream Expression Cardinalities. In ICDT (LIPIcs), Vol. 48","volume":"6","author":"Dasgupta Anirban","year":"2016","unstructured":"Anirban Dasgupta, Kevin J. Lang, Lee Rhodes, and Justin Thaler. 2016. A Framework for Estimating Stream Expression Cardinalities. In ICDT (LIPIcs), Vol. 48. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 6:1--6:17.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476276"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1016\/0022-0000(85)90041-8","article-title":"Probabilistic Counting Algorithms for Data Base Applications","volume":"31","author":"Flajolet Philippe","year":"1985","unstructured":"Philippe Flajolet and G. Nigel Martin. 1985. Probabilistic Counting Algorithms for Data Base Applications. J. Comput. Syst. Sci. 31, 2 (1985), 182--209.","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_10_1","article-title":"Tracking Set-Expression Cardinalities over Continuous Update Streams","volume":"13","author":"Ganguly Sumit","year":"2004","unstructured":"Sumit Ganguly, Minos Garofalakis, and Rajeev Rastogi. 2004. Tracking Set-Expression Cardinalities over Continuous Update Streams. VLDB J. 13, 4 (2004).","journal-title":"VLDB J."},{"key":"e_1_2_1_11_1","volume-title":"VLDB 2001, Proceedings of 27th International Conference on Very Large Data Bases, September 11--14","author":"Gibbons Phillip B.","year":"2001","unstructured":"Phillip B. Gibbons. 2001. Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports. In VLDB 2001, Proceedings of 27th International Conference on Very Large Data Bases, September 11--14, 2001, Roma, Italy. Morgan Kaufmann, 541--550. http:\/\/www.vldb.org\/conf\/2001\/P541.pdf"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 28th International Conference on Very Large Data Bases","author":"Gilbert Anna C.","unstructured":"Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, and Martin J. Strauss. 2002. How to Summarize the Universe: Dynamic Maintenance of Quantiles. In Proceedings of the 28th International Conference on Very Large Data Bases (Hong Kong, China) (VLDB '02). VLDB Endowment, 454--465."},{"key":"e_1_2_1_13_1","unstructured":"David Kotz Tristan Henderson Ilya Abyzov and Jihwang Yeo. 2022. CRAWDAD dartmouth\/campus (v. 2009-09-09)."},{"key":"e_1_2_1_14_1","first-page":"9","article-title":"On the Algebra of Data Sketches","volume":"14","author":"Lemiesz Jakub","year":"2021","unstructured":"Jakub Lemiesz. 2021. On the Algebra of Data Sketches. Proc. VLDB Endow. 14, 9 (may 2021), 1655--1667.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_15_1","first-page":"8","article-title":"Efficient Framework for Operating on Data Sketches","volume":"16","author":"Lemiesz Jakub","year":"2023","unstructured":"Jakub Lemiesz. 2023. Efficient Framework for Operating on Data Sketches. Proc. VLDB Endow. 16, 8 (jun 2023), 1967--1978.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_16_1","first-page":"8","article-title":"Theory and Applications of B-Bit Minwise","volume":"54","author":"Li Ping","year":"2011","unstructured":"Ping Li and Arnd Christian K\u00f6nig. 2011. Theory and Applications of B-Bit Minwise Hashing. Commun. ACM 54, 8 (aug 2011), 101--109.","journal-title":"Hashing. Commun. ACM"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772759"},{"key":"e_1_2_1_18_1","volume-title":"Art B. Owen, and Cun-Hui Zhang","author":"Li Ping","year":"2012","unstructured":"Ping Li, Art B. Owen, and Cun-Hui Zhang. 2012. One Permutation Hashing for Efficient Search and Learning. CoRR abs\/1208.1259 (2012). arXiv:1208.1259 http:\/\/arxiv.org\/abs\/1208.1259"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2934872.2934906"},{"key":"e_1_2_1_20_1","first-page":"11","article-title":"Enabling Efficient and General Subpopulation Analytics in Multidimensional Data Streams","volume":"15","author":"Manousis Antonis","year":"2022","unstructured":"Antonis Manousis, Zhuo Cheng, Ran Ben Basat, Zaoxing Liu, and Vyas Sekar. 2022. Enabling Efficient and General Subpopulation Analytics in Multidimensional Data Streams. Proc. VLDB Endow. 15, 11 (jul 2022), 3249--3262.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","DOI":"10.1561\/9781933019604","volume-title":"Data Streams: Algorithms and Applications. Foundations and Trends in Theoretical Computer Science 1, 2","author":"Muthukrishnan S.","year":"2005","unstructured":"S. Muthukrishnan. 2005. Data Streams: Algorithms and Applications. Foundations and Trends in Theoretical Computer Science 1, 2 (2005)."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems","author":"Pagh Rasmus","unstructured":"Rasmus Pagh, Morten St\u00f6ckel, and David P. Woodruff. 2014. Is Min-Wise Hashing Optimal for Summarizing Set Intersection?. In Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (Snowbird, Utah, USA) (PODS '14). ACM, 109--120."},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/s00778-015-0380-7","article-title":"Sketching distributed sliding-window data streams","volume":"24","author":"Papapetrou Odysseas","year":"2015","unstructured":"Odysseas Papapetrou, Minos N. Garofalakis, and Antonios Deligiannakis. 2015. Sketching distributed sliding-window data streams. VLDB J. 24, 3 (2015), 345--368.","journal-title":"VLDB J."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3632093.3632098","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,20]],"date-time":"2024-01-20T11:30:02Z","timestamp":1705750202000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3632093.3632098"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["10.14778\/3632093.3632098"],"URL":"https:\/\/doi.org\/10.14778\/3632093.3632098","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,11]]},"assertion":[{"value":"2024-01-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}