{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T05:22:47Z","timestamp":1768108967299,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":36,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,22]]},"DOI":"10.1145\/3736227.3736238","type":"proceedings-article","created":{"date-parts":[[2025,7,10]],"date-time":"2025-07-10T08:03:02Z","timestamp":1752134582000},"page":"1-8","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Insert-Optimized Implementation of Streaming Data Sketches"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-6719-604X","authenticated-orcid":false,"given":"Pascal","family":"Pfeil","sequence":"first","affiliation":[{"name":"Amazon Web Services, Munich, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-4489-1638","authenticated-orcid":false,"given":"Dominik","family":"Horn","sequence":"additional","affiliation":[{"name":"Amazon Web Services, Munich, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3164-0137","authenticated-orcid":false,"given":"Orestis","family":"Polychroniou","sequence":"additional","affiliation":[{"name":"Amazon Web Services, East Palo Alto, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-7736-0669","authenticated-orcid":false,"given":"George","family":"Erickson","sequence":"additional","affiliation":[{"name":"Amazon Web Services, Boston, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-5963-6949","authenticated-orcid":false,"given":"Zhe Heng","family":"Eng","sequence":"additional","affiliation":[{"name":"Amazon Web Services, East Palo Alto, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-8938-6605","authenticated-orcid":false,"given":"Mengchu","family":"Cai","sequence":"additional","affiliation":[{"name":"Amazon Web Services, East Palo Alto, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-2414-2759","authenticated-orcid":false,"given":"Tim","family":"Kraska","sequence":"additional","affiliation":[{"name":"Amazon Web Services, Boston, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,7,10]]},"reference":[{"key":"e_1_3_3_2_2_2","volume-title":"HyperLogLog sketches","author":"affiliates Amazon Web Services, Inc. or its","unstructured":"Amazon Web Services, Inc. or its affiliates. [n. d.]. HyperLogLog sketches. Retrieved Jan 14, 2025 from https:\/\/docs.aws.amazon.com\/redshift\/latest\/dg\/hyperloglog-overview.html"},{"key":"e_1_3_3_2_3_2","doi-asserted-by":"crossref","unstructured":"Ran\u00a0Ben Basat Xiaoqi Chen Gil Einziger and Ori Rottenstreich. 2020. Designing heavy-hitter detection algorithms for programmable switches. IEEE\/ACM Transactions on Networking 28 3 (2020) 1172\u20131185.","DOI":"10.1109\/TNET.2020.2982739"},{"key":"e_1_3_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.5555\/646255.684566"},{"key":"e_1_3_3_2_5_2","doi-asserted-by":"crossref","unstructured":"Graham Cormode and Shan Muthukrishnan. 2005. An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms 55 1 (2005) 58\u201375.","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_3_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781108769938"},{"key":"e_1_3_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.231"},{"key":"e_1_3_3_2_8_2","unstructured":"Otmar Ertl. 2023. UltraLogLog: a practical and more space-efficient alternative to HyperLogLog for approximate distinct counting. arXiv preprint arXiv:https:\/\/arXiv.org\/abs\/2308.16862 (2023)."},{"key":"e_1_3_3_2_9_2","unstructured":"Otmar Ertl. 2024. ExaLogLog: Space-Efficient and Practical Approximate Distinct Counting up to the Exa-Scale. arXiv preprint arXiv:https:\/\/arXiv.org\/abs\/2402.13726 (2024)."},{"key":"e_1_3_3_2_10_2","doi-asserted-by":"crossref","unstructured":"Philippe Flajolet \u00c9ric Fusy Olivier Gandouet and Fr\u00e9d\u00e9ric Meunier. 2007. Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm. Discrete mathematics & theoretical computer scienceProceedings (2007).","DOI":"10.46298\/dmtcs.3545"},{"key":"e_1_3_3_2_11_2","unstructured":"Michael Freitag and Thomas Neumann. 2019. Every row counts: Combining sketches and sampling for accurate group-by result estimates. ratio 1 (2019) 1\u201339."},{"key":"e_1_3_3_2_12_2","volume-title":"Android Code Search - KLL implementation","unstructured":"Google. [n. d.]. Android Code Search - KLL implementation. https:\/\/cs.android.com\/android\/platform\/superproject\/main\/+\/main:packages\/modules\/StatsD\/lib\/libkll\/include\/kll.h."},{"key":"e_1_3_3_2_13_2","volume-title":"Google Benchmark","year":"2025","unstructured":"Google. 2025. Google Benchmark. https:\/\/github.com\/google\/benchmark."},{"key":"e_1_3_3_2_14_2","doi-asserted-by":"crossref","unstructured":"Michael Greenwald and Sanjeev Khanna. 2001. Space-efficient online computation of quantile summaries. ACM SIGMOD Record 30 2 (2001) 58\u201366.","DOI":"10.1145\/376284.375670"},{"key":"e_1_3_3_2_15_2","doi-asserted-by":"crossref","unstructured":"He Huang Jiakun Yu Yang Du Jia Liu Haipeng Dai and Yu-E Sun. 2023. Memory-efficient and flexible detection of heavy hitters in high-speed networks. Proceedings of the ACM on Management of Data 1 3 (2023) 1\u201324.","DOI":"10.1145\/3617334"},{"key":"e_1_3_3_2_16_2","unstructured":"Nikita Ivkin Edo Liberty Kevin Lang Zohar Karnin and Vladimir Braverman. 2019. Streaming quantiles algorithms with small space and update time. arXiv preprint arXiv:https:\/\/arXiv.org\/abs\/1907.00236 (2019)."},{"key":"e_1_3_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.17"},{"key":"e_1_3_3_2_18_2","volume-title":"A fast alternative to the modulo reduction","author":"Lemire Daniel","year":"2016","unstructured":"Daniel Lemire. 2016. A fast alternative to the modulo reduction. http:\/\/lemire.me\/blog\/2016\/06\/27\/a-fast-alternative-to-the-modulo-reduction\/."},{"key":"e_1_3_3_2_19_2","volume-title":"Iterating over set bits quickly","author":"Lemire Daniel","year":"2018","unstructured":"Daniel Lemire. 2018. Iterating over set bits quickly. https:\/\/lemire.me\/blog\/2018\/02\/21\/iterating-over-set-bits-quickly\/."},{"key":"e_1_3_3_2_20_2","doi-asserted-by":"crossref","unstructured":"Haoyu Li Qizhi Chen Yixin Zhang Tong Yang and Bin Cui. 2022. Stingy sketch: a sketch framework for accurate and fast frequency estimation. Proceedings of the VLDB Endowment 15 7 (2022) 1426\u20131438.","DOI":"10.14778\/3523210.3523220"},{"key":"e_1_3_3_2_21_2","unstructured":"Charles Masson Jee\u00a0E Rim and Homin\u00a0K Lee. 2019. Ddsketch: A fast and fully-mergeable quantile sketch with relative-error guarantees. arXiv preprint arXiv:https:\/\/arXiv.org\/abs\/1908.10693 (2019)."},{"key":"e_1_3_3_2_22_2","doi-asserted-by":"crossref","unstructured":"Dimitrios Melissourgos Haibo Wang Shigang Chen Chaoyi Ma and Shiping Chen. 2023. Single Update Sketch with Variable Counter Structure. Proceedings of the VLDB Endowment 16 13 (2023) 4296\u20134309.","DOI":"10.14778\/3625054.3625065"},{"key":"e_1_3_3_2_23_2","doi-asserted-by":"crossref","unstructured":"Ahmed Metwally Divyakant Agrawal and Amr\u00a0El Abbadi. 2006. An integrated efficient solution for computing frequent and top-k elements in data streams. ACM Transactions on Database Systems (TODS) 31 3 (2006) 1095\u20131133.","DOI":"10.1145\/1166074.1166084"},{"key":"e_1_3_3_2_24_2","first-page":"398","volume-title":"International conference on database theory","author":"Metwally Ahmed","year":"2005","unstructured":"Ahmed Metwally, Divyakant Agrawal, and Amr El\u00a0Abbadi. 2005. Efficient computation of frequent and top-k elements in data streams. In International conference on database theory. Springer, 398\u2013412."},{"key":"e_1_3_3_2_25_2","doi-asserted-by":"crossref","unstructured":"Jayadev Misra and David Gries. 1982. Finding repeated elements. Science of computer programming 2 2 (1982) 143\u2013152.","DOI":"10.1016\/0167-6423(82)90012-0"},{"key":"e_1_3_3_2_26_2","first-page":"29","volume-title":"CIDR","author":"Neumann Thomas","year":"2020","unstructured":"Thomas Neumann and Michael\u00a0J Freitag. 2020. Umbra: A Disk-Based System with In-Memory Performance.. In CIDR , Vol.\u00a020. 29."},{"key":"e_1_3_3_2_27_2","volume-title":"PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation","author":"O\u2019Neill Melissa\u00a0E.","year":"2014","unstructured":"Melissa\u00a0E. O\u2019Neill. 2014. PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation. Technical Report HMC-CS-2014-0905. Harvey Mudd College, Claremont, CA."},{"key":"e_1_3_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882948"},{"key":"e_1_3_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3050220.3063772"},{"key":"e_1_3_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183759"},{"key":"e_1_3_3_2_31_2","doi-asserted-by":"crossref","unstructured":"Pinghui Wang Yitong Liu Zhicheng Li and Rundong Li. 2024. An LDP Compatible Sketch for Securely Approximating Set Intersection Cardinalities. Proceedings of the ACM on Management of Data 2 1 (2024) 1\u201327.","DOI":"10.1145\/3639281"},{"key":"e_1_3_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3230543.3230544"},{"key":"e_1_3_3_2_33_2","doi-asserted-by":"crossref","unstructured":"Tong Yang Yang Zhou Hao Jin Shigang Chen and Xiaoming Li. 2017. Pyramid sketch: A sketch framework for frequency estimation of data streams. Proceedings of the VLDB Endowment 10 11 (2017) 1442\u20131453.","DOI":"10.14778\/3137628.3137652"},{"key":"e_1_3_3_2_34_2","unstructured":"Fuheng Zhao Divyakant Agrawal Amr\u00a0El Abbadi and Ahmed Metwally. 2021. SpaceSaving \u00b1 :\u00a0An Optimal Algorithm for Frequency Estimation and Frequent items in the Bounded Deletion Model. arXiv preprint arXiv:https:\/\/arXiv.org\/abs\/2112.03462 (2021)."},{"key":"e_1_3_3_2_35_2","doi-asserted-by":"crossref","unstructured":"Fuheng Zhao Sujaya Maiyya Ryan Wiener Divyakant Agrawal and Amr\u00a0El Abbadi. 2021. KLL \u00b1 \u00a0Approximate Qantile Sketches over Dynamic Datasets. Proceedings of the VLDB Endowment 14 7 (2021) 1215\u20131227.","DOI":"10.14778\/3450980.3450990"},{"key":"e_1_3_3_2_36_2","doi-asserted-by":"crossref","unstructured":"Yang Zhou Omid Alipourfard Minlan Yu and Tong Yang. 2018. Accelerating network measurement in software. ACM SIGCOMM Computer Communication Review 48 3 (2018) 2\u201312.","DOI":"10.1145\/3276799.3276800"},{"key":"e_1_3_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183726"}],"event":{"name":"SIGMOD\/PODS '25: International Conference on Management of Data","location":"Berlin Germany","acronym":"DaMoN '25","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 21st International Workshop on Data Management on New Hardware"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3736227.3736238","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,15]],"date-time":"2025-07-15T09:17:13Z","timestamp":1752571033000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3736227.3736238"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,22]]},"references-count":36,"alternative-id":["10.1145\/3736227.3736238","10.1145\/3736227"],"URL":"https:\/\/doi.org\/10.1145\/3736227.3736238","relation":{},"subject":[],"published":{"date-parts":[[2025,6,22]]},"assertion":[{"value":"2025-07-10","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}