{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T15:05:29Z","timestamp":1764687929797,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":43,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,9]],"date-time":"2021-06-09T00:00:00Z","timestamp":1623196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"HKRGC","award":["16202317, 16201318, 16201819, 16205420"],"award-info":[{"award-number":["16202317, 16201318, 16201819, 16205420"]}]},{"name":"Alibaba Innovative Research"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,9]]},"DOI":"10.1145\/3448016.3452821","type":"proceedings-article","created":{"date-parts":[[2021,6,18]],"date-time":"2021-06-18T17:22:39Z","timestamp":1624036959000},"page":"1465-1477","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries"],"prefix":"10.1145","author":[{"given":"Yuan","family":"Qiu","sequence":"first","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, Hong Kong"}]},{"given":"Yilei","family":"Wang","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, Hong Kong"}]},{"given":"Ke","family":"Yi","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology & SICS, Shenzhen University, Hong Kong, Hong Kong"}]},{"given":"Feifei","family":"Li","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]},{"given":"Bin","family":"Wu","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]},{"given":"Chaoqun","family":"Zhan","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]}],"member":"320","published-online":{"date-parts":[[2021,6,18]]},"reference":[{"volume-title":"Foundations of databases","author":"Abiteboul Serge","unstructured":"Serge Abiteboul , Richard Hull , and Victor Vianu . 1995. Foundations of databases . Addison-Wesley Longman Publishing Co., Inc. Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of databases .Addison-Wesley Longman Publishing Co., Inc.","key":"e_1_3_2_2_1_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_2_1","DOI":"10.1145\/304182.304207"},{"volume-title":"Proc. ACM SIGMOD International Conference on Management of Data .","author":"Agarwal S.","unstructured":"S. Agarwal , H. Milner , A. Kleiner , A. Talwalkar , M. Jordan , S. Madden , B. Mozafari , and I. Stoica . 2014. Knowing when youre wrong: Building fast and reliable approximate query processing systems . In Proc. ACM SIGMOD International Conference on Management of Data . S. Agarwal, H. Milner, A. Kleiner, A. Talwalkar, M. Jordan, S. Madden, B. Mozafari, and I. Stoica. 2014. Knowing when youre wrong: Building fast and reliable approximate query processing systems. In Proc. ACM SIGMOD International Conference on Management of Data .","key":"e_1_3_2_2_3_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_4_1","DOI":"10.1006\/jcss.1997.1545"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_5_1","DOI":"10.1007\/3-540-45726-7_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_6_1","DOI":"10.1145\/1247480.1247504"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_7_1","DOI":"10.1145\/276304.276343"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_8_1","DOI":"10.1145\/3035918.3035921"},{"key":"e_1_3_2_2_9_1","volume-title":"Proc. International Conference on Very Large Data Bases .","author":"Cormode Graham","year":"2005","unstructured":"Graham Cormode and Minos Garofalakis . 2005 . Sketching streams through the net: Distributed approximate query tracking . In Proc. International Conference on Very Large Data Bases . Graham Cormode and Minos Garofalakis. 2005. Sketching streams through the net: Distributed approximate query tracking. In Proc. International Conference on Very Large Data Bases ."},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_10_1","DOI":"10.1145\/564691.564699"},{"key":"e_1_3_2_2_11_1","volume-title":"Proc. European Symposium on Algorithms. 605--617","author":"Durand Marianne","year":"2003","unstructured":"Marianne Durand and Philippe Flajolet . 2003 . Loglog Counting of Large Cardinalities (Extended Abstract) . In Proc. European Symposium on Algorithms. 605--617 . Marianne Durand and Philippe Flajolet. 2003. Loglog Counting of Large Cardinalities (Extended Abstract). In Proc. European Symposium on Algorithms. 605--617."},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_12_1","DOI":"10.1109\/ICDE.2006.61"},{"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. In Analysis of Algorithms (AOFA) .  Philippe Flajolet \u00c9ric Fusy Olivier Gandouet and Fr\u00e9d\u00e9ric Meunier. 2007. Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm. In Analysis of Algorithms (AOFA) .","key":"e_1_3_2_2_13_1","DOI":"10.46298\/dmtcs.3545"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_14_1","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_3_2_2_15_1","volume-title":"Freitag and Thomas Neumann","author":"Michael","year":"2019","unstructured":"Michael J. Freitag and Thomas Neumann . 2019 . Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates . In Proc. Biennial Conference on Innovative Data Systems Research . Michael J. Freitag and Thomas Neumann. 2019. Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates. In Proc. Biennial Conference on Innovative Data Systems Research ."},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_16_1","DOI":"10.14778\/3236187.3236212"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_17_1","DOI":"10.1145\/235968.233340"},{"key":"e_1_3_2_2_18_1","volume-title":"Database Systems: The Complete Book","author":"Garcia-Molina Hector","year":"2008","unstructured":"Hector Garcia-Molina , Jeffrey D. Ullman , and Jennifer Widom . 2008 . Database Systems: The Complete Book . Prentice Hall . Hector Garcia-Molina, Jeffrey D. Ullman, and Jennifer Widom. 2008. Database Systems: The Complete Book .Prentice Hall."},{"key":"e_1_3_2_2_19_1","volume-title":"Proc. International Conference on Very Large Data Bases. 541--550","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 Proc. International Conference on Very Large Data Bases. 541--550 . Phillip B. Gibbons. 2001. Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports. In Proc. International Conference on Very Large Data Bases. 541--550."},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_20_1","DOI":"10.1145\/581751.581753"},{"volume-title":"Proc. ACM Symposium on Theory of Computing .","author":"Gilbert Anna C.","unstructured":"Anna C. Gilbert , Sudipto Guha , Piotr Indyk , Yannis Kotidis , S. Muthukrishnan , and Martin J. Strauss . 2002 a. Fast, small-space algorithms for approximate histogram maintenance . In Proc. ACM Symposium on Theory of Computing . Anna C. Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, S. Muthukrishnan, and Martin J. Strauss. 2002 a. Fast, small-space algorithms for approximate histogram maintenance. In Proc. ACM Symposium on Theory of Computing .","key":"e_1_3_2_2_21_1"},{"volume-title":"Proc. International Conference on Very Large Data Bases .","author":"Gilbert Anna C.","unstructured":"Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , and Martin J. Strauss . 2002 b. How to Summarize the Universe: Dynamic Maintenance of Quantiles . In Proc. International Conference on Very Large Data Bases . Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, and Martin J. Strauss. 2002 b. How to Summarize the Universe: Dynamic Maintenance of Quantiles. In Proc. International Conference on Very Large Data Bases .","key":"e_1_3_2_2_22_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_23_1","DOI":"10.1145\/375663.375670"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_24_1","DOI":"10.1145\/1132863.1132873"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_25_1","DOI":"10.1006\/jcss.1996.0041"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_26_1","DOI":"10.5555\/3116271.3116497"},{"volume-title":"Online Aggregation. In Proc. ACM SIGMOD International Conference on Management of Data .","author":"Hellerstein J. M.","unstructured":"J. M. Hellerstein , P. J. Haas , and H. J. Wang . 1997 . Online Aggregation. In Proc. ACM SIGMOD International Conference on Management of Data . J. M. Hellerstein, P. J. Haas, and H. J. Wang. 1997. Online Aggregation. In Proc. ACM SIGMOD International Conference on Management of Data .","key":"e_1_3_2_2_27_1"},{"key":"e_1_3_2_2_28_1","volume-title":"Proc. International Conference on Very Large Data Bases .","author":"Jagadish H. V.","year":"1998","unstructured":"H. V. Jagadish , Nick Koudas , S. Muthukrishnan , Viswanath Poosala , Kenneth C. Sevcik , and Torsten Suel . 1998 . Optimal Histograms with Quality Guarantees . In Proc. International Conference on Very Large Data Bases . H. V. Jagadish, Nick Koudas, S. Muthukrishnan, Viswanath Poosala, Kenneth C. Sevcik, and Torsten Suel. 1998. Optimal Histograms with Quality Guarantees. In Proc. International Conference on Very Large Data Bases ."},{"key":"e_1_3_2_2_29_1","volume-title":"Proc. ACM SIGMOD International Conference on Management of Data .","author":"Kandula Srikanth","year":"2016","unstructured":"Srikanth Kandula , Anil Shanbhag , Aleksandar Vitorovic , Matthaios Olma , Robert Grandl , Surajit Chaudhuri , and Bolin Ding . 2016 . Quickr: Lazily Approximating Complex Ad-Hoc Queries in Big Data Clusters . In Proc. ACM SIGMOD International Conference on Management of Data . Srikanth Kandula, Anil Shanbhag, Aleksandar Vitorovic, Matthaios Olma, Robert Grandl, Surajit Chaudhuri, and Bolin Ding. 2016. Quickr: Lazily Approximating Complex Ad-Hoc Queries in Big Data Clusters. In Proc. ACM SIGMOD International Conference on Management of Data ."},{"volume-title":"Proc. ACM Symposium on Principles of Database Systems. 41--52","author":"Kane Daniel M.","unstructured":"Daniel M. Kane , Jelani Nelson , and David P. Woodruff . 2010. An optimal algorithm for the distinct elements problem . In Proc. ACM Symposium on Principles of Database Systems. 41--52 . Daniel M. Kane, Jelani Nelson, and David P. Woodruff. 2010. An optimal algorithm for the distinct elements problem. In Proc. ACM Symposium on Principles of Database Systems. 41--52.","key":"e_1_3_2_2_30_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_31_1","DOI":"10.1109\/ICDM.2016.0033"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_32_1","DOI":"10.1145\/2882903.2915235"},{"key":"e_1_3_2_2_33_1","volume-title":"Lee","author":"Masson Charles","year":"2019","unstructured":"Charles Masson , Jee E. Rim , and Homin K . Lee . 2019 . DDSketch: A Fast and Fully Mergeable Quantile Sketch with Relative Error Guarantees. Proceedings of the VLDB Endowment , Vol. 12 (2019). Charles Masson, Jee E. Rim, and Homin K. Lee. 2019. DDSketch: A Fast and Fully Mergeable Quantile Sketch with Relative Error Guarantees. Proceedings of the VLDB Endowment , Vol. 12 (2019)."},{"volume-title":"Proc. ACM SIGMOD International Conference on Management of Data .","author":"Matias Y.","unstructured":"Y. Matias , J. S. Vitter , and M. Wang . 1998. Wavelet-Based Histograms for Selectivity Estimation . In Proc. ACM SIGMOD International Conference on Management of Data . Y. Matias, J. S. Vitter, and M. Wang. 1998. Wavelet-Based Histograms for Selectivity Estimation. In Proc. ACM SIGMOD International Conference on Management of Data .","key":"e_1_3_2_2_34_1"},{"volume-title":"Proc. ACM SIGMOD International Conference on Management of Data .","author":"Poosala Viswanath","unstructured":"Viswanath Poosala , Peter J. Haas , Yannis E. Ioannidis , and Eugene J. Shekita . 1996. Improved histograms for selectivity estimation of range predicates . In Proc. ACM SIGMOD International Conference on Management of Data . Viswanath Poosala, Peter J. Haas, Yannis E. Ioannidis, and Eugene J. Shekita. 1996. Improved histograms for selectivity estimation of range predicates. In Proc. ACM SIGMOD International Conference on Management of Data .","key":"e_1_3_2_2_35_1"},{"doi-asserted-by":"crossref","unstructured":"Yuan Qiu Yilei Wang Ke Yi Feifei Li Bin Wu and Chaoqun Zhan. 2020. Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries (full version) . http:\/\/www.cse.ust.hk\/ yike\/spj-full.pdf  Yuan Qiu Yilei Wang Ke Yi Feifei Li Bin Wu and Chaoqun Zhan. 2020. Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries (full version) . http:\/\/www.cse.ust.hk\/ yike\/spj-full.pdf","key":"e_1_3_2_2_36_1","DOI":"10.1145\/3448016.3452821"},{"volume-title":"Proc. ACM SIGMOD International Conference on Management of Data . 1607--1623","author":"Sommer Johanna","unstructured":"Johanna Sommer , Matthias Boehm , Alexandre V. Evfimievski , Berthold Reinwald , and Peter J. Haas . 2019. MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions . In Proc. ACM SIGMOD International Conference on Management of Data . 1607--1623 . Johanna Sommer, Matthias Boehm, Alexandre V. Evfimievski, Berthold Reinwald, and Peter J. Haas. 2019. MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions. In Proc. ACM SIGMOD International Conference on Management of Data . 1607--1623.","key":"e_1_3_2_2_37_1"},{"key":"e_1_3_2_2_38_1","volume-title":"Proc. ACM SIGMOD International Conference on Management of Data .","author":"Surajit Surajit","year":"2017","unstructured":"Surajit Surajit , Bolin Ding , and Srikanth Kandula . 2017 . Approximate Query Processing: No Silver Bullet . In Proc. ACM SIGMOD International Conference on Management of Data . Surajit Surajit, Bolin Ding, and Srikanth Kandula. 2017. Approximate Query Processing: No Silver Bullet. In Proc. ACM SIGMOD International Conference on Management of Data ."},{"doi-asserted-by":"crossref","unstructured":"S. Suri C. Toth and Y. Zhou. 2006. Range counting over multidimensional data streams. Discrete and Computational Geometry (2006).  S. Suri C. Toth and Y. Zhou. 2006. Range counting over multidimensional data streams. Discrete and Computational Geometry (2006).","key":"e_1_3_2_2_39_1","DOI":"10.1007\/s00454-006-1269-4"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_40_1","DOI":"10.1145\/564691.564741"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_41_1","DOI":"10.1145\/3299869.3319897"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_42_1","DOI":"10.14778\/2824032.2824051"},{"key":"e_1_3_2_2_43_1","volume-title":"Proceedings of the VLDB Endowment","volume":"12","author":"Zhan C.","unstructured":"C. Zhan , M. Su , C. Wei , X. Peng , L. Lin , S. Wang , Z. Chen , F. Li , Y. Pan , F. Zheng , and C. Chai . 2019. AnalyticDB: real-time OLAP database system at Alibaba cloud . In Proceedings of the VLDB Endowment , Vol. 12 . C. Zhan, M. Su, C. Wei, X. Peng, L. Lin, S. Wang, Z. Chen, F. Li, Y. Pan, F. Zheng, and C. Chai. 2019. AnalyticDB: real-time OLAP database system at Alibaba cloud. In Proceedings of the VLDB Endowment, Vol. 12."}],"event":{"sponsor":["SIGMOD ACM Special Interest Group on Management of Data"],"acronym":"SIGMOD\/PODS '21","name":"SIGMOD\/PODS '21: International Conference on Management of Data","location":"Virtual Event China"},"container-title":["Proceedings of the 2021 International Conference on Management of Data"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448016.3452821","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3448016.3452821","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:05Z","timestamp":1750195685000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448016.3452821"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,9]]},"references-count":43,"alternative-id":["10.1145\/3448016.3452821","10.1145\/3448016"],"URL":"https:\/\/doi.org\/10.1145\/3448016.3452821","relation":{},"subject":[],"published":{"date-parts":[[2021,6,9]]},"assertion":[{"value":"2021-06-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}