{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T15:41:21Z","timestamp":1787240481503,"version":"build-2736575974"},"reference-count":73,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2025,9,30]]},"abstract":"<jats:p>We introduce an approach to supporting high-dimensional data cubes at interactive query speeds and moderate storage cost. Our approach is based on binary(-domain) data cubes that are judiciously partially materialized; the missing information can be quickly approximated using statistical or linear programming techniques. This enables new applications such as exploratory data analysis for feature engineering and other fields of data science. Moreover, it removes the need to compromise when building a data cube\u2014all columns we might ever wish to use can be included as dimensions. Our approach also speeds up certain dice, roll-up, and drill-down operations on data cubes with hierarchical dimensions compared to traditional data cubes.<\/jats:p>","DOI":"10.1145\/3716373","type":"journal-article","created":{"date-parts":[[2025,5,2]],"date-time":"2025-05-02T07:52:22Z","timestamp":1746172342000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["High-dimensional Data Cubes"],"prefix":"10.1145","volume":"50","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1583-496X","authenticated-orcid":false,"given":"Sachin","family":"Basil John","sequence":"first","affiliation":[{"name":"EPFL","place":["Lausanne, Switzerland"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9130-7205","authenticated-orcid":false,"given":"Christoph","family":"Koch","sequence":"additional","affiliation":[{"name":"EPFL","place":["Lausanne, Switzerland"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2041-7201","authenticated-orcid":false,"given":"Peter","family":"Lindner","sequence":"additional","affiliation":[{"name":"EPFL","place":["Lausanne, Switzerland"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,30]]},"reference":[{"key":"e_1_3_3_2_2","first-page":"506","volume-title":"Proceedings of the 22nd International Conference on Very Large Data Bases (VLDB\u201996)","author":"Agarwal Sameet","year":"1996","unstructured":"Sameet Agarwal, Rakesh Agrawal, Prasad Deshpande, Ashish Gupta, Jeffrey F. Naughton, Raghu Ramakrishnan, and Sunita Sarawagi. 1996. On the computation of multidimensional aggregates. In Proceedings of the 22nd International Conference on Very Large Data Bases (VLDB\u201996). 506\u2013521."},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465355"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-9473(01)00013-5"},{"key":"e_1_3_3_5_2","volume-title":"A Representation of the Joint Distribution of Responses to n Dichotomous Items","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."},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.5555\/645923.671019"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/262762.262764"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45151-X_30"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.5075\/epfl-thesis-9017"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.14778\/3565838.3565839"},{"key":"e_1_3_3_11_2","volume-title":"Discrete Multivariate Analysis: Theory and Practice","author":"Bishop Yvonne M.","year":"2007","unstructured":"Yvonne M. Bishop, Stephen E. Fienberg, and Paul W. Holland. 2007. Discrete Multivariate Analysis: Theory and Practice. Springer Science & Business Media."},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/1242524.1242526"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/248603.248616"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066188"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1965-0178586-1"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176996454"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177692379"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177731829"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1976.1674569"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/0206051"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmva.2018.08.003"},{"issue":"1","key":"e_1_3_3_22_2","doi-asserted-by":"crossref","first-page":"379","DOI":"10.4064\/fm-25-1-379-387","article-title":"G\u00e9n\u00e9ralisation du Th\u00e9or\u00e8me des Probabilit\u00e9s Totales","volume":"25","author":"Fr\u00e9chet Maurice","year":"1935","unstructured":"Maurice Fr\u00e9chet. 1935. G\u00e9n\u00e9ralisation du Th\u00e9or\u00e8me des Probabilit\u00e9s Totales. Fundamenta Mathematicae 25, 1 (1935), 379\u2013387.","journal-title":"Fundamenta Mathematicae"},{"key":"e_1_3_3_23_2","volume-title":"Linear Programming: Methods and Applications","author":"Gass Saul I.","year":"2003","unstructured":"Saul I. Gass. 2003. Linear Programming: Methods and Applications. Courier Corporation."},{"key":"e_1_3_3_24_2","volume-title":"The Travelling Salesman Problem and Related Problems","author":"Gavish Bezalel","year":"1978","unstructured":"Bezalel Gavish and Stephen C. Graves. 1978. The Travelling Salesman Problem and Related Problems. Working Paper. Massachusetts Institute of Technology, Operations Research Center."},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009726021843"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742795"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.16"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233333"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.18.6.1138"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584070"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253291"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.5555\/1215169"},{"key":"e_1_3_3_33_2","volume-title":"Linear Algebra","author":"Hoffman Kenneth","year":"1971","unstructured":"Kenneth Hoffman. 1971. Linear Algebra. Prentice-Hall, Englewood Cliffs, NJ."},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/55.1.179"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.106.620"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/1412331.1412335"},{"key":"e_1_3_3_37_2","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1109\/ICDE.2006.106","volume-title":"Proceedings of the 22nd International Conference on Data Engineering (ICDE\u201906)","author":"Jin Ruoming","year":"2006","unstructured":"Ruoming Jin, Leonid Glimcher, Chris Jermaine, and Gagan Agrawal. 2006. New sampling-based estimators for OLAP queries. In Proceedings of the 22nd International Conference on Data Engineering (ICDE\u201906). 18."},{"issue":"5","key":"e_1_3_3_38_2","first-page":"403","article-title":"Solution of the marginal problem and decomposable distributions","volume":"27","author":"Jirou\u0161ek Radim","year":"1991","unstructured":"Radim Jirou\u0161ek. 1991. Solution of the marginal problem and decomposable distributions. Kybernetika 27, 5 (1991), 403\u2013412.","journal-title":"Kybernetika"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-9473(93)E0055-9"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/2939502.2939503"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816674"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.5555\/1795555"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1016\/B978-155860869-6\/50074-3"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367518"},{"key":"e_1_3_3_46_2","unstructured":"David C. Lay. 2011. Linear algebra and its applications. (4 ed.). Pearson."},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/11775300_47"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/212433.220198"},{"key":"e_1_3_3_49_2","first-page":"528","volume-title":"Proceedings of the 30th International Conference on Very Large Data Bases (VLDB\u201904)","author":"Li Xiaolei","year":"2004","unstructured":"Xiaolei Li, Jiawei Han, and Hector Gonzalez. 2004. High-Dimensional OLAP: A minimal cubing approach. In Proceedings of the 30th International Conference on Very Large Data Bases (VLDB\u201904). 528\u2013539."},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376695"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/3651147"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376682"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1080\/00330124.2015.1099449"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-9473(89)90046-7"},{"key":"e_1_3_3_55_2","first-page":"379","volume-title":"Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB\u201906)","author":"Morfonios Konstantinos","year":"2006","unstructured":"Konstantinos Morfonios and Yannis E. Ioannidis. 2006. CURE for cubes: Cubing using a ROLAP engine. In Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB\u201906). 379\u2013390."},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/1287620.1287623"},{"key":"e_1_3_3_57_2","volume-title":"Parking Violations Issued - Fiscal Year 2021","author":"Finance New York City Department of","year":"2021","unstructured":"New York City Department of Finance. 2021. Parking Violations Issued - Fiscal Year 2021. Retrieved August 4, 2022 from https:\/\/data.cityofnewyork.us\/City-Government\/Parking-Violations-Issued-Fiscal-Year-2021\/kvfd-bves"},{"key":"e_1_3_3_58_2","doi-asserted-by":"crossref","unstructured":"Patrick E. O\u2019Neil Elizabeth J. O\u2019Neil Xuedong Chen and Stephen Revilak. 2009. The star schema benchmark and augmented fact table indexing. In Performance Evaluation and Benchmarking (TPTPC\u201909) Raghunath Othayoth Nambiar and Meikel Poess (Eds.). 237\u2013252.","DOI":"10.1007\/978-3-642-10424-4_17"},{"key":"e_1_3_3_59_2","volume-title":"Probability, Random Variables and Stochastic Processes (4th ed.)","author":"Papoulis Athanasios","year":"2002","unstructured":"Athanasios Papoulis and S. Unnikrishna Pillai. 2002. Probability, Random Variables and Stochastic Processes (4th ed.). McGraw-Hill Professional."},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.5555\/645923.670993"},{"key":"e_1_3_3_61_2","unstructured":"Eyal Rozenberg. 2020. Star Schema Benchmark Data Set Generator (ssb-dbgen). Retrieved August 4 2022 from https:\/\/github.com\/eyalroz\/ssb-dbgen"},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40511-2_10"},{"key":"e_1_3_3_63_2","doi-asserted-by":"publisher","DOI":"10.1145\/312129.312231"},{"key":"e_1_3_3_64_2","first-page":"488","volume-title":"Proceedings of the 24th International Conference on Very Large Data Bases (VLDB\u201998)","author":"Shukla Amit","year":"1998","unstructured":"Amit Shukla, Prasad Deshpande, and Jeffrey F. Naughton. 1998. Materialized view selection for multidimensional datasets. In Proceedings of the 24th International Conference on Very Large Data Bases (VLDB\u201998). 488\u2013499."},{"key":"e_1_3_3_65_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-020-01505-9"},{"key":"e_1_3_3_66_2","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564745"},{"key":"e_1_3_3_67_2","first-page":"318","volume-title":"Proceedings of the 22nd International Conference on Very Large Data Bases (VLDB\u201996)","author":"Srivastava Divesh","year":"1996","unstructured":"Divesh Srivastava, Shaul Dar, H. V. Jagadish, and Alon Y. Levy. 1996. Answering queries with aggregation using views. In Proceedings of the 22nd International Conference on Very Large Data Bases (VLDB\u201996). 318\u2013329."},{"key":"e_1_3_3_68_2","first-page":"262","volume-title":"Proceedings of the International Workshop on Artificial Intelligence and Statistics","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 International Workshop on Artificial Intelligence and Statistics. PMLR, 262\u2013269."},{"key":"e_1_3_3_69_2","doi-asserted-by":"publisher","DOI":"10.1016\/0047-259X(90)90084-U"},{"key":"e_1_3_3_70_2","doi-asserted-by":"publisher","DOI":"10.1145\/288627.288645"},{"issue":"1","key":"e_1_3_3_71_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/2200000001","article-title":"Graphical models, exponential families, and variational inference","volume":"1","author":"Wainwright Martin J.","year":"2007","unstructured":"Martin J. Wainwright and Michael I. Jordan. 2007. Graphical models, exponential families, and variational inference. Foundations and Trends\u00ae in Machine Learning 1, 1\u2013 2 (2007), 1\u2013305.","journal-title":"Foundations and Trends\u00ae in Machine Learning"},{"key":"e_1_3_3_72_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2002.994705"},{"key":"e_1_3_3_73_2","article-title":"On the Kronecker products and their applications","volume":"2013","author":"Zhang Huamin","year":"2013","unstructured":"Huamin Zhang and Feng Ding. 2013. On the Kronecker products and their applications. Journal of Applied Mathematics 2013, 1 (2013).","journal-title":"Journal of Applied Mathematics"},{"key":"e_1_3_3_74_2","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253288"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3716373","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T07:45:15Z","timestamp":1751269515000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3716373"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,30]]},"references-count":73,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9,30]]}},"alternative-id":["10.1145\/3716373"],"URL":"https:\/\/doi.org\/10.1145\/3716373","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,30]]},"assertion":[{"value":"2024-03-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-02","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-30","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}