{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T00:05:59Z","timestamp":1756512359912,"version":"3.44.0"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,2]]},"abstract":"<jats:p>\n            In data exploration, executing queries over a large database can be time-consuming. Previous work has proposed approximate query processing as a way to speed up aggregate queries in this context, but do not address non-aggregate queries. Our paper introduces a novel holistic approach to handle both types of queries by finding an optimized subset of data, referred to as an\n            <jats:italic toggle=\"yes\">approximation set.<\/jats:italic>\n            The goal is to maximize query result quality while using a smaller set of data, thereby significantly reducing the query execution time. We formalize this problem as Holistic Approximate Query Processing and establish its NP-completeness. To tackle this, we propose an approximate solution using\n            <jats:italic toggle=\"yes\">Reinforcement Learning<\/jats:italic>\n            , termed HARLM. While HARLM does not provide theoretical guarantees due to its reliance on Reinforcement Learning, it effectively overcomes challenges related to the large action space and the need for generalization beyond a known query workload. Experimental results on both non-aggregate and aggregate benchmarks show that HARLM significantly outperforms the baselines both in terms of accuracy (30% improvement) and efficiency (10\u201335X).\n          <\/jats:p>","DOI":"10.14778\/3725688.3725695","type":"journal-article","created":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T14:19:21Z","timestamp":1756477161000},"page":"1635-1648","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Holistic Query Approximation via RL Modeling"],"prefix":"10.14778","volume":"18","author":[{"given":"Susan B.","family":"Davidson","sequence":"first","affiliation":[{"name":"University of Pennsylvania"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tova","family":"Milo","sequence":"additional","affiliation":[{"name":"Tel Aviv University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kathy","family":"Razmadze","sequence":"additional","affiliation":[{"name":"Tel Aviv University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gal","family":"Zeevi","sequence":"additional","affiliation":[{"name":"Tel Aviv University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,8,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465355"},{"key":"e_1_2_1_2_1","volume-title":"2008 IEEE International Multitopic Conference. IEEE, 558\u2013564","author":"Ahmad Munir","year":"2008","unstructured":"Munir Ahmad, Muhammad Abdul Qadir, and Muhammad Sanaullah. 2008. Query processing over relational databases with semantic cache: A survey. In 2008 IEEE International Multitopic Conference. IEEE, 558\u2013564."},{"key":"e_1_2_1_3_1","volume-title":"Selecting Sub-tables for Data Exploration. In 2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, 2496\u20132509","author":"Amsterdamer Yael","year":"2023","unstructured":"Yael Amsterdamer, Susan B Davidson, Tova Milo, Kathy Razmadze, and Amit Somech. 2023. Selecting Sub-tables for Data Exploration. In 2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, 2496\u20132509."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 31st ACM International Conference on Information & Knowledge Management. 4788\u20134792","author":"Arad Dana","unstructured":"Dana Arad, Daniel Deutch, and Nave Frost. [n.d.]. LearnShapley: Learning to Predict Rankings of Facts Contribution Based on Query Logs. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management. 4788\u20134792."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389779"},{"key":"e_1_2_1_6_1","volume-title":"Openai gym. arXiv preprint arXiv:1606.01540","author":"Brockman Greg","year":"2016","unstructured":"Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. 2016. Openai gym. arXiv preprint arXiv:1606.01540 (2016)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3080008"},{"key":"e_1_2_1_8_1","unstructured":"Susan B. Davidson Tova Milo Kathy Razmadze and Gal Zeevi. 2024. HARLM Github Repository. https:\/\/github.com\/GalZeevi\/HARLM"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177731829"},{"key":"e_1_2_1_10_1","volume-title":"2016 IEEE International Conference on Computational Intelligence and Computing Research (ICCIC). IEEE, 1\u20139.","author":"Dhanasree K","year":"2016","unstructured":"K Dhanasree and C Shobabindu. 2016. A survey on OLAP. In 2016 IEEE International Conference on Computational Intelligence and Computing Research (ICCIC). IEEE, 1\u20139."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380574"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the VLDB Endowment 13","author":"Fan Ju","unstructured":"Ju Fan, Tongyu Liu, Guoliang Li, Junyou Chen, Yuwei Shen, and Xiaoyong Du. [n.d.]. Relational Data Synthesis using Generative Adversarial Networks: A Design Space Exploration. Proceedings of the VLDB Endowment 13, 11 ([n. d.])."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2207676.2208294"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/64.621228"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3115404.3115418"},{"key":"e_1_2_1_16_1","volume-title":"Advances in psychology.","author":"Hart Sandra G","unstructured":"Sandra G Hart and Lowell E Staveland. 1988. Development of NASA-TLX (Task Load Index): Results of empirical and theoretical research. In Advances in psychology. Vol. 52. Elsevier, 139\u2013183."},{"key":"e_1_2_1_17_1","volume-title":"Deepdb: Learn from data, not from queries! arXiv preprint arXiv:1909.00607","author":"Hilprecht Benjamin","year":"2019","unstructured":"Benjamin Hilprecht, Andreas Schmidt, Moritz Kulessa, Alejandro Molina, Kristian Kersting, and Carsten Binnig. 2019. Deepdb: Learn from data, not from queries! arXiv preprint arXiv:1909.00607 (2019)."},{"key":"e_1_2_1_18_1","volume-title":"A closer look at invalid action masking in policy gradient algorithms. arXiv preprint arXiv:2006.14171","author":"Huang Shengyi","year":"2020","unstructured":"Shengyi Huang and Santiago Onta\u00f1\u00f3n. 2020. A closer look at invalid action masking in policy gradient algorithms. arXiv preprint arXiv:2006.14171 (2020)."},{"key":"e_1_2_1_19_1","unstructured":"IBM. [n.d.]. https:\/\/www.ibm.com\/topics\/tm1"},{"key":"e_1_2_1_20_1","unstructured":"IBM. [n.d.]. https:\/\/www.ibm.com\/docs\/sr\/planning-analytics\/2.0.0?topic=tier-tm1-server-installation"},{"key":"e_1_2_1_21_1","unstructured":"Martin Idel. 2016. A review of matrix scaling and Sinkhorn's normal form for matrices and positive maps. arXiv:1609.06349 [math.RA] https:\/\/arxiv.org\/abs\/1609.06349"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622737.1622748"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882940"},{"key":"e_1_2_1_24_1","volume-title":"2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 1489\u20131500","author":"Kaoudi Zoi","year":"2020","unstructured":"Zoi Kaoudi, Jorge-Arnulfo Quian\u00e9-Ruiz, Bertty Contreras-Rojas, Rodrigo Pardo-Meza, Anis Troudi, and Sanjay Chawla. 2020. ML-based cross-platform query optimization. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 1489\u20131500."},{"key":"e_1_2_1_25_1","volume-title":"2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 1489\u20131500","author":"Kaoudi Zoi","year":"2020","unstructured":"Zoi Kaoudi, Jorge-Arnulfo Quian\u00e9-Ruiz, Bertty Contreras-Rojas, Rodrigo Pardo-Meza, Anis Troudi, and Sanjay Chawla. 2020. ML-based cross-platform query optimization. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 1489\u20131500."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_27_1","volume-title":"2020 IEEE International Conference on Big Data (Big Data). IEEE, 5118\u20135127","author":"Leung Carson K","year":"2020","unstructured":"Carson K Leung, Yubo Chen, Calvin SH Hoi, Siyuan Shang, and Alfredo Cuzzocrea. 2020. Machine learning and OLAP on big COVID-19 data. In 2020 IEEE International Conference on Big Data (Big Data). IEEE, 5118\u20135127."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-018-0074-4"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687643"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687643"},{"key":"e_1_2_1_31_1","volume-title":"Conference on Innovative Data Systems,(CIDR21)","author":"Ma Qingzhi","year":"2021","unstructured":"Qingzhi Ma, Ali M Shanghooshabad, Mehrdad Almasi, Meghdad Kurmanji, and Peter Triantafillou. 2021. Learned approximate query processing: Make it light, accurate and fast. In Conference on Innovative Data Systems,(CIDR21)."},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 2019 International Conference on Management of Data. 1553\u20131570","author":"Ma Qingzhi","year":"2019","unstructured":"Qingzhi Ma and Peter Triantafillou. 2019. Dbest: Revisiting approximate query processing engines with machine learning models. In Proceedings of the 2019 International Conference on Management of Data. 1553\u20131570."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2206869.2206874"},{"key":"e_1_2_1_34_1","volume-title":"Smaller Approximate Kernel and Improved Approximation. arXiv preprint arXiv:1810.03792","author":"Manurangsi Pasin","year":"2018","unstructured":"Pasin Manurangsi. 2018. A Note on Max k-Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation. arXiv preprint arXiv:1810.03792 (2018)."},{"key":"e_1_2_1_35_1","unstructured":"Microsoft. 2016. Microsoft academic search. http:\/\/academic.research.microsoft.com"},{"key":"e_1_2_1_36_1","volume-title":"International conference on machine learning. PMLR","author":"Mnih Volodymyr","year":"2016","unstructured":"Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. 2016. Asynchronous methods for deep reinforcement learning. In International conference on machine learning. PMLR, 1928\u20131937."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3025453.3025456"},{"key":"e_1_2_1_38_1","volume-title":"Ray: A distributed framework for emerging {AI} applications. In 13th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 18). 561\u2013577.","author":"Moritz Philipp","year":"2018","unstructured":"Philipp Moritz, Robert Nishihara, Stephanie Wang, Alexey Tumanov, Richard Liaw, Eric Liang, Melih Elibol, Zongheng Yang, William Paul, Michael I Jordan, et al. 2018. Ray: A distributed framework for emerging {AI} applications. In 13th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 18). 561\u2013577."},{"key":"e_1_2_1_39_1","volume-title":"Vedavyas Panneershelvam, Mustafa Suleyman, Charles Beattie, Stig Petersen, et al.","author":"Nair Arun","year":"2015","unstructured":"Arun Nair, Praveen Srinivasan, Sam Blackwell, Cagdas Alcicek, Rory Fearon, Alessandro De Maria, Vedavyas Panneershelvam, Mustafa Suleyman, Charles Beattie, Stig Petersen, et al. 2015. Massively parallel methods for deep reinforcement learning. arXiv preprint arXiv:1507.04296 (2015)."},{"key":"e_1_2_1_40_1","volume-title":"2019 3rd International Conference on Electronics, Communication and Aerospace Technology (ICECA). IEEE, 425\u2013430","author":"Nanda Adhish","year":"2019","unstructured":"Adhish Nanda, Swati Gupta, and Meenu Vijrania. 2019. A comprehensive survey of OLAP: recent trends. In 2019 3rd International Conference on Electronics, Communication and Aerospace Technology (ICECA). IEEE, 425\u2013430."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380606"},{"key":"e_1_2_1_42_1","volume-title":"Mosaic: A Sample-Based Database System for Open World Query Processing. In CIDR.","author":"Orr Laurel J","year":"2020","unstructured":"Laurel J Orr, Samuel K Ainsworth, Kevin G Jamieson, Walter Cai, Magdalena Balazinska, and Dan Suciu. 2020. Mosaic: A Sample-Based Database System for Open World Query Processing. In CIDR."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061320"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Y. Park M. Cafarella and B. Mozafari. 2016. Visualization-aware sampling for very large databases. In ICDE.","DOI":"10.1109\/ICDE.2016.7498287"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the 2018 International Conference on Management of Data. 1461\u20131476","author":"Park Yongjoo","year":"2018","unstructured":"Yongjoo Park, Barzan Mozafari, Joseph Sorenson, and Junhao Wang. 2018. Verdictdb: Universalizing approximate query processing. In Proceedings of the 2018 International Conference on Management of Data. 1461\u20131476."},{"key":"e_1_2_1_46_1","volume-title":"Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems 32","author":"Paszke Adam","year":"2019","unstructured":"Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems 32 (2019)."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137637"},{"key":"e_1_2_1_48_1","volume-title":"Sentence-bert: Sentence embeddings using siamese bert-networks. arXiv preprint arXiv:1908.10084","author":"Reimers Nils","year":"2019","unstructured":"Nils Reimers and Iryna Gurevych. 2019. Sentence-bert: Sentence embeddings using siamese bert-networks. arXiv preprint arXiv:1908.10084 (2019)."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397242"},{"key":"e_1_2_1_50_1","volume-title":"Reinforcement learning: An introduction","author":"Sutton Richard S","unstructured":"Richard S Sutton and Andrew G Barto. 2018. Reinforcement learning: An introduction. MIT press."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00117"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.inffus.2021.11.005"},{"key":"e_1_2_1_53_1","unstructured":"Transaction Processing Performance Council. [n.d.]. TPC Benchmark H (Decision Support). http:\/\/www.tpc.org\/tpch\/. Accessed: 2025-04-04."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-016-0022-0"},{"key":"e_1_2_1_55_1","volume-title":"2011 IEEE 27th International Conference on Data Engineering. IEEE, 1163\u20131174","author":"Vieira Marcos R","year":"2011","unstructured":"Marcos R Vieira, Humberto L Razente, Maria CN Barioni, Marios Hadjieleftheriou, Divesh Srivastava, Caetano Traina, and Vassilis J Tsotras. 2011. On query result diversification. In 2011 IEEE 27th International Conference on Data Engineering. IEEE, 1163\u20131174."},{"key":"e_1_2_1_56_1","volume-title":"Chen Jason Zhang, and Weikai Li","author":"Wu Ting","year":"2015","unstructured":"Ting Wu, Lei Chen, Pan Hui, Chen Jason Zhang, and Weikai Li. 2015. Hear the Whole Story: Towards the Diversity of Opinion in Crowdsourcing Markets. PVLDB 8, 5 (2015)."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3725688.3725695","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T14:22:03Z","timestamp":1756477323000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3725688.3725695"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2]]},"references-count":56,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,2]]}},"alternative-id":["10.14778\/3725688.3725695"],"URL":"https:\/\/doi.org\/10.14778\/3725688.3725695","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,2]]},"assertion":[{"value":"2025-08-29","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}