{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T22:10:04Z","timestamp":1755900604424,"version":"3.44.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"NSF","doi-asserted-by":"publisher","award":["NSF-BSF 2109922, NSF IIS 2314527"],"award-info":[{"award-number":["NSF-BSF 2109922, NSF IIS 2314527"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,10]]},"abstract":"<jats:p>We investigate an approximation algorithm for various aggregate queries on partially materialized data cubes. Data cubes are interpreted as probability distributions, and cuboids from a partial materialization populate the terms of a series expansion of the target query distribution. Unknown terms in the expansion are just assumed to be 0 in order to recover an approximate query result. We identify this method as a variant of related approaches from other fields of science, that is, the Bahadur representation and, more generally, (biased) Fourier expansions of Boolean functions. Existing literature indicates a rich but intricate theoretical landscape. Focusing on the data cube application, we start by investigating worst-case error bounds. We build upon prior work to obtain provably optimal materialization strategies with respect to query workloads. In addition, we propose a new heuristic method governing materialization decisions. Finally, we show that well-approximated queries are guaranteed to have well-approximated roll-ups.<\/jats:p>","DOI":"10.1145\/3651147","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-23","source":"Crossref","is-referenced-by-count":1,"title":["The Moments Method for Approximate Data Cube Queries"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2041-7201","authenticated-orcid":false,"given":"Peter","family":"Lindner","sequence":"first","affiliation":[{"name":"\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne (EPFL), Lausanne, VD, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1583-496X","authenticated-orcid":false,"given":"Sachin","family":"Basil John","sequence":"additional","affiliation":[{"name":"\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne (EPFL), Lausanne, VD, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9130-7205","authenticated-orcid":false,"given":"Christoph","family":"Koch","sequence":"additional","affiliation":[{"name":"\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne (EPFL), Lausanne, VD, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4144-0868","authenticated-orcid":false,"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Ryan","author":"Geys Helena","year":"2002","unstructured":"Marc. Aerts, Helena Geys, Geert Molenberghs, and Louise M. Ryan. 2002. Topics in Modelling of Clustered Data. Chapman & Hall\/CRC, New York, NY, USA."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465355"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/645920.672836"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/72.377984"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/18.suppl_2.S27"},{"key":"e_1_2_1_6_1","first-page":"158","article-title":"A representation of the joint distribution of responses to n dichotomous items. Stanford University Press, Stanford, CA, USA","volume":"9","author":"Bahadur R. R.","year":"1961","unstructured":"R. R. Bahadur. 1961. A representation of the joint distribution of responses to n dichotomous items. Stanford University Press, Stanford, CA, USA, Chapter 9, 158--168.","journal-title":"Chapter"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","unstructured":"Sachin Basil John. 2023. Interactive-time Exploration Querying and Analysis of Large High-dimensional Datasets. PhD thesis. \u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne Lausanne Switzerland. https:\/\/doi.org\/10.5075\/epfl-thesis-9017","DOI":"10.5075\/epfl-thesis-9017"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565838.3565839"},{"key":"e_1_2_1_9_1","unstructured":"Mihir Bellare. 1991. The Spectral Norm of Finite Functions. Technical Report MIT\/LCS\/TR-495. Massachusetts Institute of Technology."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/93.1.197"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000004"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","unstructured":"G. Dall'Aglio S. Kotz and G. Salinetti (Eds.). 1991. Advances in Probability Distributions with Given Marginals. Springer Netherlands Dordrecht The Netherlands. https:\/\/doi.org\/10.1007\/978--94-011--3466--8","DOI":"10.1007\/978--94-011--3466--8"},{"volume-title":"Topics in Modelling of Clustered Data, , Marc","author":"Declerck Lieven","key":"e_1_2_1_13_1","unstructured":"Lieven Declerck. 2002. Bahadur Parameter Space. In Topics in Modelling of Clustered Data, , Marc. Aerts, Helena Geys, Geert Molenberghs, and Louise M. Ryan (Eds.). Chapman & Hall\/CRC, New York, NY, USA, Chapter Appendix A."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1080\/00949659808811900"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177731829"},{"key":"e_1_2_1_16_1","volume-title":"Hart","author":"Duda Richard O.","year":"1973","unstructured":"Richard O. Duda and Peter E. Hart. 1973. Pattern classification and scene analysis. Wiley, New York, NY, USA, and London, UK."},{"key":"e_1_2_1_17_1","volume-title":"COLT 2012 - The 25th Annual Conference on Learning Theory, June 25--27, 2012, Edinburgh, Scotland (JMLR Proceedings","volume":"17","author":"Feldman Vitaly","year":"2012","unstructured":"Vitaly Feldman. 2012. Learning DNF Expressions from Fourier Spectrum. In COLT 2012 - The 25th Annual Conference on Learning Theory, June 25--27, 2012, Edinburgh, Scotland (JMLR Proceedings, Vol. 23), , Shie Mannor, Nathan Srebro, and Robert C. Williamson (Eds.). MIT Press, Cambridge, MA, USA, 17.1--17.19. http:\/\/proceedings.mlr.press\/v23\/feldman12b\/feldman12b.pdf"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmva.2018.08.003"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the Fourth Annual Workshop on Computational Learning Theory, COLT 1991","author":"Furst Merrick L.","year":"1991","unstructured":"Merrick L. Furst, Jeffrey C. Jackson, and Sean W. Smith. 1991. Improved Learning of $mathitAC^,0$ Functions. In Proceedings of the Fourth Annual Workshop on Computational Learning Theory, COLT 1991, Santa Cruz, California, USA, August 5--7, 1991, , Manfred K. Warmuth and Leslie G. Valiant (Eds.). Morgan Kaufmann, San Francisco, CA, USA, 317--325."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009726021843"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233333"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the Seventh International Workshop on Artificial Intelligence and Statistics, AISTATS 1999","author":"Humphreys Keith","year":"1999","unstructured":"Keith Humphreys and D. M. Titterington. 1999. The exploration of new methods for learning in binary Boltzmann machines. In Proceedings of the Seventh International Workshop on Artificial Intelligence and Statistics, AISTATS 1999, Fort Lauderdale, Florida, USA, January 3--6, 1999, , David Heckerman and Joe Whittaker (Eds.). Society for Artificial Intelligence and Statistics, San Francisco, CA, USA. http:\/\/uncertainty99.microsoft.com\/binabolt.htm"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019--9958(68)90300--8"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1533"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627435.2750361"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.106"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167--9473(93)E0055--9"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.60"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2018.2862383"},{"volume-title":"Probabilistic Graphical Models - Principles and Techniques","author":"Koller Daphne","key":"e_1_2_1_30_1","unstructured":"Daphne Koller and Nir Friedman. 2009. Probabilistic Graphical Models - Principles and Techniques. MIT Press, Cambridge, MA, USA."},{"volume-title":"The Chi-squared Distribution","author":"Lancaster H.O.","key":"e_1_2_1_31_1","unstructured":"H.O. Lancaster. 1969. The Chi-squared Distribution. J. Wiley and Sons, Inc., New York, NY, USA."},{"key":"e_1_2_1_32_1","unstructured":"P. F. Lazarsfeld. 1956. Some observations on dichotomous systems. Technical Report. Columbia University Sociology Department New York NY USA."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.2307\/2532944"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306--4573(94)90071-X"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9--15","volume":"4444","author":"McKenna Ryan","year":"2019","unstructured":"Ryan McKenna, Daniel Sheldon, and Gerome Miklau. 2019. Graphical-model based estimation and inference for differential privacy. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9--15 June 2019, Long Beach, California, USA (Proceedings of Machine Learning Research, Vol. 97), , Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.). MIT Press, Cambridge, MA, USA, 4435--4444. http:\/\/proceedings.mlr.press\/v97\/mckenna19a.html"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/0--387--28980--1"},{"volume-title":"Analysis of Boolean Functions","author":"O'Donnell Ryan","key":"e_1_2_1_37_1","unstructured":"Ryan O'Donnell. 2014. Analysis of Boolean Functions. Cambridge University Press, Cambridge, MA, USA."},{"key":"e_1_2_1_38_1","unstructured":"Ryan O'Donnell. 2021. Analysis of Boolean Functions. arxiv: 2105.10386v1 [cs.DM] Revised edition of citeodonnell2014analysis."},{"key":"e_1_2_1_39_1","volume-title":"Syed Hamid Nawab, and Andrew Singer","author":"Oppenheim Alan V.","year":"1997","unstructured":"Alan V. Oppenheim, John Buck, Michael Daniel, Alan S. Willsky, Syed Hamid Nawab, and Andrew Singer. 1997. Signals & Systems second ed.). Prentice Hall, Upper Saddle River, NJ, USA."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.2307\/2531733"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1006\/jmva.2001.2059"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176347885"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3-030--34372--9"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the Ninth International Workshop on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research","volume":"269","author":"Teh Yee Whye","year":"2003","unstructured":"Yee Whye Teh and Max Welling. 2003. On Improving the Efficiency of the Iterative Proportional Fitting Procedure. In Proceedings of the Ninth International Workshop on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research, Vol. R4), , Christopher M. Bishop and Brendan J. Frey (Eds.). PMLR, Cambridge, MA, USA, 262--269. https:\/\/proceedings.mlr.press\/r4\/teh03a.html Reissued by PMLR on 01 April 2021."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0047--259X(90)90084-U"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304199"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/288627.288645"},{"key":"e_1_2_1_48_1","unstructured":"C. T. Yu Chris Buckley K. Lam and Gerard Salton. 1983. A Generalized Term Dependence Model in Information Retrieval. Technical Report. University of Illinois Chicago Cornell University Hong Kong University. https:\/\/ecommons.cornell.edu\/handle\/1813\/6383"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651147","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651147","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:39:46Z","timestamp":1755898786000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651147"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651147"],"URL":"https:\/\/doi.org\/10.1145\/3651147","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}