{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T05:45:39Z","timestamp":1777614339550,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":46,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,8,24]],"date-time":"2024-08-24T00:00:00Z","timestamp":1724457600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/https:\/\/doi.org\/10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62372362"],"award-info":[{"award-number":["62372362"]}],"id":[{"id":"10.13039\/https:\/\/doi.org\/10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,8,25]]},"DOI":"10.1145\/3637528.3671695","type":"proceedings-article","created":{"date-parts":[[2024,8,25]],"date-time":"2024-08-25T04:54:55Z","timestamp":1724561695000},"page":"2432-2443","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["QSketch: An Efficient Sketch for Weighted Cardinality Estimation in Streams"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8078-5834","authenticated-orcid":false,"given":"Yiyan","family":"Qi","sequence":"first","affiliation":[{"name":"International Digital Economy Academy (IDEA), Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0354-9536","authenticated-orcid":false,"given":"Rundong","family":"Li","sequence":"additional","affiliation":[{"name":"MOE KLINNS Lab, Xi'an Jiaotong University, Xi'an, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1434-837X","authenticated-orcid":false,"given":"Pinghui","family":"Wang","sequence":"additional","affiliation":[{"name":"MOE KLINNS Lab, Xi'an Jiaotong University, Xi'an, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-7625-1512","authenticated-orcid":false,"given":"Yufang","family":"Sun","sequence":"additional","affiliation":[{"name":"MOE KLINNS Lab, Xi'an Jiaotong University, Xi'an, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-6893-4406","authenticated-orcid":false,"given":"Rui","family":"Xing","sequence":"additional","affiliation":[{"name":"MOE KLINNS Lab, Shaanxi Normal University, Xi'an, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,8,24]]},"reference":[{"key":"e_1_3_2_2_1_1","unstructured":"2010. Twitter. https:\/\/anlab-kaist.github.io\/traces\/"},{"key":"e_1_3_2_2_2_1","unstructured":"2018. CAIDA. https:\/\/www.caida.org\/"},{"key":"e_1_3_2_2_3_1","unstructured":"2022. https:\/\/github.com\/mkarppa\/hyperlogloglog\/blob\/master\/hyperlogloglog\/ PackedVector.hpp#L130"},{"key":"e_1_3_2_2_4_1","unstructured":"2024. https:\/\/github.com\/Rezerolird\/QSketch"},{"key":"e_1_3_2_2_5_1","first-page":"1748","article-title":"Newton raphson method","volume":"6","author":"Akram Saba","year":"2015","unstructured":"Saba Akram and Quarrat Ul Ann. 2015. Newton raphson method. International Journal of Scientific & Engineering Research 6, 7 (2015), 1748--1752.","journal-title":"International Journal of Scientific & Engineering Research"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"crossref","first-page":"879","DOI":"10.1198\/jasa.2011.ap10217","article-title":"Distinct counting with a self-learning bitmap","volume":"106","author":"Chen Aiyou","year":"2011","unstructured":"Aiyou Chen, Jin Cao, Larry Shepp, and Tuan Nguyen. 2011. Distinct counting with a self-learning bitmap. JASA 106, 495 (2011), 879--890.","journal-title":"JASA"},{"key":"e_1_3_2_2_7_1","volume-title":"Cardinality change-based early detection of large-scale cyber-attacks","author":"Chen Wenji","unstructured":"Wenji Chen, Yang Liu, and Yong Guan. 2013. Cardinality change-based early detection of large-scale cyber-attacks. In IEEE INFOCOM. 1788--1796."},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"crossref","unstructured":"Edith Cohen and Haim Kaplan. 2007. Summarizing data using bottom-k sketches. In PODC. 225--234.","DOI":"10.1145\/1281100.1281133"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453884"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"crossref","unstructured":"Reuven Cohen Liran Katzir and Aviv Yehezkel. 2017. A minimal variance estimator for the cardinality of big data set intersection. In ACM SIGKDD. 95-- 103.","DOI":"10.1145\/3097983.3097999"},{"key":"e_1_3_2_2_11_1","volume-title":"Approximate aggregation techniques for sensor databases","author":"Considine Jeffrey","unstructured":"Jeffrey Considine, Feifei Li, George Kollios, and John Byers. 2004. Approximate aggregation techniques for sensor databases. In IEEE ICDE. 449--460."},{"key":"e_1_3_2_2_12_1","volume-title":"Mathematical methods of statistics","author":"Cram\u00e9r Harald","unstructured":"Harald Cram\u00e9r. 1999. Mathematical methods of statistics. Vol. 26. Princeton university press."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"crossref","unstructured":"Marianne Durand and Philippe Flajolet. 2003. Loglog counting of large cardinalities. In ESA. 605--617.","DOI":"10.1007\/978-3-540-39658-1_55"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"crossref","unstructured":"Cristian Estan George Varghese and Mike Fisk. 2003. Bitmap algorithms for counting active flows on high speed links. In SIGCOMM. 153--166.","DOI":"10.1145\/948205.948225"},{"key":"e_1_3_2_2_15_1","unstructured":"Ronald A Fisher and Frank Yates. 1938. Statistical tables: For biological agricultural and medical research. Oliver and Boyd."},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02241657"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.46298\/dmtcs.3545"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_3_2_2_19_1","first-page":"541","article-title":"Distinct sampling for highly-accurate answers to distinct values queries and event reports","volume":"1","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, Vol. 1. 541--550.","journal-title":"VLDB"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.06.020"},{"key":"e_1_3_2_2_21_1","first-page":"499","article-title":"Cardinality estimation: An experimental survey","volume":"11","author":"Harmouch Hazar","year":"2017","unstructured":"Hazar Harmouch and Felix Naumann. 2017. Cardinality estimation: An experimental survey. PVLDB 11, 4 (2017), 499--512.","journal-title":"PVLDB"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"crossref","unstructured":"Daniel M Kane Jelani Nelson and David PWoodruff. 2010. An optimal algorithm for the distinct elements problem. In PODS. 41--52.","DOI":"10.1145\/1807085.1807094"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"crossref","unstructured":"Matti Karppa and Rasmus Pagh. 2022. HyperLogLogLog: Cardinality Estimation With One Log More. In ACM SIGKDD. 753--761.","DOI":"10.1145\/3534678.3539246"},{"key":"e_1_3_2_2_24_1","article-title":"A modified finite Newton method for fast solution of large scale linear SVMs","volume":"6","author":"Keerthi S Sathiya","year":"2005","unstructured":"S Sathiya Keerthi, Dennis DeCoste, and Thorsten Joachims. 2005. A modified finite Newton method for fast solution of large scale linear SVMs. Journal of Machine Learning Research 6, 3 (2005).","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2365934.2365942"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461553"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3594512.3594526"},{"key":"e_1_3_2_2_28_1","first-page":"361","article-title":"Rcv1: A new benchmark collection for text categorization research","author":"Lewis David D","year":"2004","unstructured":"David D Lewis, Yiming Yang, Tony Russell-Rose, and Fan Li. 2004. Rcv1: A new benchmark collection for text categorization research. JMLR 5, Apr (2004), 361--397.","journal-title":"JMLR 5"},{"key":"e_1_3_2_2_29_1","unstructured":"Ping Li and Christian K\u00f6nig. 2010. b-Bit minwise hashing. In WWW. 671--680."},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"crossref","unstructured":"Xiaohui Long and Torsten Suel. 2005. Three-level caching for efficient query processing in large web search engines. In WebConf. 257--266.","DOI":"10.1145\/1060745.1060785"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1961659.1961663"},{"key":"e_1_3_2_2_32_1","unstructured":"Christopher R Palmer Georgos Siganos Michalis Faloutsos Christos Faloutsos and Phillip B Gibbons. 2001. The connectivity and fault-tolerance of the Internet topology. (2001)."},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"crossref","unstructured":"Yiyan Qi Pinghui Wang Yuanming Zhang Junzhou Zhao Guangjian Tian and Xiaohong Guan. 2020. Fast generating a large number of gumbel-max variables. In WebConf. 796--807.","DOI":"10.1145\/3366423.3380160"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"crossref","unstructured":"Daniel Ting. 2014. Streamed Approximate Counting of Distinct Elements: Beating Optimal Batch Methods. In ACM SIGKDD. 442--451.","DOI":"10.1145\/2623330.2623669"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"crossref","unstructured":"Daniel Ting. 2016. Towards optimal cardinality estimation of unions and intersections with sketches. In ACM SIGKDD. 1195--1204.","DOI":"10.1145\/2939672.2939772"},{"key":"e_1_3_2_2_36_1","volume-title":"Evolutionary study of web spam: Webb spam corpus 2011 versus webb spam corpus","author":"Wang De","year":"2006","unstructured":"De Wang, Danesh Irani, and Calton Pu. 2012. Evolutionary study of web spam: Webb spam corpus 2011 versus webb spam corpus 2006. In IEEE CollaborateCom. 40--49."},{"key":"e_1_3_2_2_37_1","first-page":"1086","article-title":"A data streaming method for monitoring host connection degrees of high-speed links","volume":"6","author":"Wang Pinghui","year":"2011","unstructured":"Pinghui Wang, Xiaohong Guan, Tao Qin, and Qiuzhen Huang. 2011. A data streaming method for monitoring host connection degrees of high-speed links. IEEE TIFS 6, 3 (2011), 1086--1098.","journal-title":"IEEE TIFS"},{"key":"e_1_3_2_2_38_1","volume-title":"Half-Xor: A Fully-Dynamic Sketch for Estimating the Number of Distinct Values in Big Tables","author":"Wang Pinghui","year":"2024","unstructured":"Pinghui Wang, Dongdong Xie, Junzhou Zhao, Jinsong Li, Zhicheng Li, Rundong Li, and Yang Ren. 2024. Half-Xor: A Fully-Dynamic Sketch for Estimating the Number of Distinct Values in Big Tables. IEEE Transactions on Knowledge and Data Engineering (2024)."},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"crossref","unstructured":"Wu Wei Bin Li Chen Ling and Chengqi Zhang. 2017. Consistent Weighted Sampling Made More Practical. In WebConf. 1035--1043.","DOI":"10.1145\/3038912.3052598"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/78922.78925"},{"key":"e_1_3_2_2_41_1","volume-title":"Computing the distribution of a linear combination of inverted gamma variables. Science Direct Working Paper S1574-0358","author":"Witkovsky Viktor","year":"2001","unstructured":"Viktor Witkovsky. 2001. Computing the distribution of a linear combination of inverted gamma variables. Science Direct Working Paper S1574-0358 (2001), 04."},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"crossref","unstructured":"Qingjun Xiao Shigang Chen Min Chen and Yibei Ling. 2015. Hyper-compact virtual estimators for big network data based on register sharing. In ACM SIGMETRICS. 417--428.","DOI":"10.1145\/2796314.2745870"},{"key":"e_1_3_2_2_43_1","volume-title":"Better with fewer bits: Improving the performance of cardinality estimation of large data streams","author":"Xiao Qingjun","unstructured":"Qingjun Xiao, You Zhou, and Shigang Chen. 2017. Better with fewer bits: Improving the performance of cardinality estimation of large data streams. In IEEE INFOCOM. 1--9."},{"key":"e_1_3_2_2_44_1","volume-title":"Fit a spread estimator in small memory","author":"Yoon M","unstructured":"M Yoon, Tao Li, Shigang Chen, and J-K Peir. 2009. Fit a spread estimator in small memory. In IEEE INFOCOM. 504--512."},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3237857"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"crossref","unstructured":"Qi Zhao Abhishek Kumar and Jun Xu. 2005. Joint Data Streaming and Sampling Techniques for Detection of Super Sources and Destinations.. In ACM SIGCOMM. 77--90.","DOI":"10.1145\/1330107.1330117"}],"event":{"name":"KDD '24: The 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining","location":"Barcelona Spain","acronym":"KDD '24","sponsor":["SIGMOD ACM Special Interest Group on Management of Data","SIGKDD ACM Special Interest Group on Knowledge Discovery in Data"]},"container-title":["Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3637528.3671695","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3637528.3671695","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:06:00Z","timestamp":1750291560000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3637528.3671695"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,24]]},"references-count":46,"alternative-id":["10.1145\/3637528.3671695","10.1145\/3637528"],"URL":"https:\/\/doi.org\/10.1145\/3637528.3671695","relation":{},"subject":[],"published":{"date-parts":[[2024,8,24]]},"assertion":[{"value":"2024-08-24","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}