{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T19:48:14Z","timestamp":1774986494816,"version":"3.50.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["62402112;62072113"],"award-info":[{"award-number":["62402112;62072113"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,17]]},"abstract":"<jats:p>\n                    For interactive data exploration, approximate query processing (AQP) is a useful approach that provides a timely response by trading query accuracy. To reduce query latency, existing AQP methods use samples or models rather than the underlying data to answer queries. However, it is difficult to achieve satisfactory results in terms of query accuracy and query latency simultaneously with these methods. For the sample-based methods, this is because the more accurate the query results are, the more samples are needed and the more time cost is required for processing. The model-based methods have lower query latency, but they cannot return the approximate results with high accuracy because the existing models cannot capture the complex data distribution accurately. In this paper, we propose a fast and accurate AQP method\n                    <jats:italic toggle=\"yes\">FAAQP<\/jats:italic>\n                    . In FAAQP, we propose a novel unsupervised model\n                    <jats:italic toggle=\"yes\">bitmap-augmented sum-product network<\/jats:italic>\n                    (BSPN) that combines the advantages of the sum-product network with bitmaps to capture the characteristics of data distribution more accurately. Then, we propose a budget-aware BSPN construction method that builds BSPN models with the maximum query accuracy for the given storage budget. Furthermore, to reduce the query latency of FAAQP, we propose a bitmap merging strategy that makes a trade-off between query accuracy and query latency. Experimental results on real-world and synthetic datasets show that FAAQP outperforms the state-of-the-art AQP methods and achieves 1.3\u00d7-9.0\u00d7 improvements in query accuracy with a low query latency.\n                  <\/jats:p>","DOI":"10.1145\/3725292","type":"journal-article","created":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:23:29Z","timestamp":1750281809000},"page":"1-26","source":"Crossref","is-referenced-by-count":0,"title":["FAAQP: Fast and Accurate Approximate Query Processing based on Bitmap-augmented Sum-Product Network"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4987-932X","authenticated-orcid":false,"given":"Hanbing","family":"Zhang","sequence":"first","affiliation":[{"name":"School of Computer Science, Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1169-8032","authenticated-orcid":false,"given":"Yinan","family":"Jing","sequence":"additional","affiliation":[{"name":"School of Computer Science, Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2926-4814","authenticated-orcid":false,"given":"Zhenying","family":"He","sequence":"additional","affiliation":[{"name":"School of Computer Science, Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7518-5466","authenticated-orcid":false,"given":"Kai","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Computer Science, Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9059-3713","authenticated-orcid":false,"given":"X. Sean","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Computer Science, Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,18]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"2020. Bureau of transportation statistics. Flights dataset."},{"key":"e_1_2_2_2_1","unstructured":"2023. Airbnb dataset. http:\/\/insideairbnb.com\/get-the-data\/."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3524284"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335450"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465355"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.2325"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242524.1242526"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915249"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3625054.3625059"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304208"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253291"},{"key":"e_1_2_2_12_1","volume-title":"Github repository: deepdb-public. https:\/\/github.com\/DataManagementLab\/deepdb-public","author":"Hilprecht Benjamin","year":"2023","unstructured":"Benjamin Hilprecht. 2023. Github repository: deepdb-public. https:\/\/github.com\/DataManagementLab\/deepdb-public (2023)."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384349"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3648160.3648181"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882940"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.2402"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915235"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457277"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2014.2346452"},{"key":"e_1_2_2_20_1","volume-title":"The Randomized Dependence Coefficient. In Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems","author":"L\u00f3pez-Paz David","year":"2013","unstructured":"David L\u00f3pez-Paz, Philipp Hennig, and Bernhard Sch\u00f6lkopf. 2013. The Randomized Dependence Coefficient. In Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. 1--9."},{"key":"e_1_2_2_21_1","volume-title":"Github repository: DBEstClient. https:\/\/github.com\/qingzma\/DBEstClient","author":"Qingzhi Ma.","year":"2023","unstructured":"Qingzhi Ma. 2023. Github repository: DBEstClient. https:\/\/github.com\/qingzma\/DBEstClient (2023)."},{"key":"e_1_2_2_22_1","volume-title":"Accurate and Fast. In 11th Conference on Innovative Data Systems Research, CIDR","author":"Ma Qingzhi","year":"2021","unstructured":"Qingzhi Ma, Ali Mohammadi Shanghooshabad, Mehrdad Almasi, Meghdad Kurmanji, and Peter Triantafillou. 2021. Learned Approximate Query Processing: Make it Light, Accurate and Fast. In 11th Conference on Innovative Data Systems Research, CIDR 2021."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3324958"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1609\/AAAI.V32I1.11731"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056098"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00053"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00050"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196905"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064013"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517900"},{"key":"e_1_2_2_31_1","volume-title":"Domingos","author":"Poon Hoifung","year":"2011","unstructured":"Hoifung Poon and Pedro M. Domingos. 2011. Sum-product networks: A new deep architecture. In Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence. AUAI Press, 337--346."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3543507.3583411"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3320212"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589319"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457302"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v36i8.20800"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00117"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368302"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3485450.3485458"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461552"},{"key":"e_1_2_2_41_1","volume-title":"Github repository: FSPN. https:\/\/github.com\/wuziniu\/FSPN","author":"Ziniu Wu.","year":"2023","unstructured":"Ziniu Wu. 2023. Github repository: FSPN. https:\/\/github.com\/wuziniu\/FSPN (2023)."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368294"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461539"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725292","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:51:05Z","timestamp":1774983065000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725292"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,17]]}},"alternative-id":["10.1145\/3725292"],"URL":"https:\/\/doi.org\/10.1145\/3725292","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]}}}