{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,21]],"date-time":"2026-09-21T13:03:02Z","timestamp":1789995782329,"version":"4.0.1"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,11,2]],"date-time":"2019-11-02T00:00:00Z","timestamp":1572652800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,11,2]],"date-time":"2019-11-02T00:00:00Z","timestamp":1572652800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["1535565"],"award-info":[{"award-number":["1535565"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"crossref","award":["1614738"],"award-info":[{"award-number":["1614738"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2020,1]]},"DOI":"10.1007\/s00778-019-00582-9","type":"journal-article","created":{"date-parts":[[2019,11,2]],"date-time":"2019-11-02T09:03:21Z","timestamp":1572685401000},"page":"539-567","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["EntropyDB: a probabilistic approach to approximate query processing"],"prefix":"10.1007","volume":"29","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2183-3541","authenticated-orcid":false,"given":"Laurel","family":"Orr","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Magdalena","family":"Balazinska","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,11,2]]},"reference":[{"key":"582_CR1","doi-asserted-by":"crossref","unstructured":"Acharya, S., Gibbons, P.B., Poosala, V.: Congressional samples for approximate answering of group-by queries. In: ACM Sigmod Record, vol.\u00a029, pp. 487\u2013498. ACM (2000)","DOI":"10.1145\/335191.335450"},{"key":"582_CR2","doi-asserted-by":"crossref","unstructured":"Acharya, S., Gibbons, P.B., Poosala, V., Ramaswamy, S.: The aqua approximate query answering system. In: ACM Sigmod Record, vol.\u00a028, pp. 574\u2013576. ACM (1999)","DOI":"10.1145\/304181.304581"},{"key":"582_CR3","doi-asserted-by":"crossref","unstructured":"Agarwal, S., et al.: Blinkdb: queries with bounded errors and bounded response times on very large data. In: Proceedings of EuroSys\u201913, pp. 29\u201342 (2013)","DOI":"10.1145\/2465351.2465355"},{"key":"582_CR4","unstructured":"Applegate, D.A., Calinescu, G., Johnson, D.S., Karloff, H., Ligett, K., Wang, J.: Compressing rectilinear pictures and minimizing access control lists. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms"},{"key":"582_CR5","doi-asserted-by":"crossref","unstructured":"Babcock, B., Chaudhuri, S., Das, G.: Dynamic sample selection for approximate query processing. In: Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, pp. 539\u2013550 (2003)","DOI":"10.1145\/872757.872822"},{"key":"582_CR6","doi-asserted-by":"crossref","unstructured":"Bar-Yossef, Z., Jayram, T., Kumar, R., Sivakumar, D., Trevisan, L.: Counting distinct elements in a data stream. In: International Workshop on Randomization and Approximation Techniques in Computer Science, pp. 1\u201310. Springer (2002)","DOI":"10.1007\/3-540-45726-7_1"},{"key":"582_CR7","doi-asserted-by":"crossref","unstructured":"Behrisch, M., Bach, B., Henry Riche, N., Schreck, T., Fekete, J.-D.: Matrix reordering methods for table and network visualization. In: Computer Graphics Forum, vol. 35, pp. 693\u2013716. Wiley Online Library (2016)","DOI":"10.1111\/cgf.12935"},{"key":"582_CR8","unstructured":"Bekker, J., Davis, J., Choi, A., Darwiche, A., Van den Broeck, G.: Tractable learning for complex probability queries. In: Advances in Neural Information Processing Systems, pp. 2242\u20132250 (2015)"},{"issue":"1","key":"582_CR9","first-page":"39","volume":"22","author":"AL Berger","year":"1996","unstructured":"Berger, A.L., Pietra, V.J.D., Pietra, S.A.D.: A maximum entropy approach to natural language processing. Comput. Linguist. 22(1), 39\u201371 (1996)","journal-title":"Comput. Linguist."},{"issue":"3\u20134","key":"582_CR10","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1561\/2200000050","volume":"8","author":"S Bubeck","year":"2015","unstructured":"Bubeck, S.: Convex optimization: algorithms and complexity. Found. Trends Mach. Learn. 8(3\u20134), 231\u2013357 (2015)","journal-title":"Found. Trends Mach. Learn."},{"issue":"2\u20133","key":"582_CR11","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s007780100049","volume":"10","author":"K Chakrabarti","year":"2001","unstructured":"Chakrabarti, K., Garofalakis, M., Rastogi, R., Shim, K.: Approximate query processing using wavelets. VLDB J. Int. J. Very Large Data Bases 10(2\u20133), 199\u2013223 (2001)","journal-title":"VLDB J. Int. J. Very Large Data Bases"},{"key":"582_CR12","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1145\/376284.375694","volume":"30","author":"S Chaudhuri","year":"2001","unstructured":"Chaudhuri, S., Das, G., Narasayya, V.: A robust, optimization-based approach for approximate answering of aggregate queries. ACM SIGMOD Rec. 30, 295\u2013306 (2001)","journal-title":"ACM SIGMOD Rec."},{"key":"582_CR13","doi-asserted-by":"crossref","unstructured":"Chaudhuri, S., Ding, B., Kandula, S.: Approximate query processing: No silver bullet. In: Proceedings of the 2017 ACM International Conference on Management of Data, pp. 511\u2013519. ACM (2017)","DOI":"10.1145\/3035918.3056097"},{"issue":"3","key":"582_CR14","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1109\/TIT.1968.1054142","volume":"14","author":"C Chow","year":"1968","unstructured":"Chow, C., Liu, C.: Approximating discrete probability distributions with dependence trees. IEEE Trans. Inf. Theory 14(3), 462\u2013467 (1968)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1\u20133","key":"582_CR15","first-page":"1","volume":"4","author":"G Cormode","year":"2011","unstructured":"Cormode, G., Garofalakis, M., Haas, P.J., Jermaine, C., et al.: Synopses for massive data: samples, histograms, wavelets, sketches. Found. Trends\u00ae Databases 4(1\u20133), 1\u2013294 (2011)","journal-title":"Found. Trends\u00ae Databases"},{"key":"582_CR16","doi-asserted-by":"crossref","unstructured":"Crotty, A., Galakatos, A., Zgraggen, A., Binnig, C., Kraska, T.: The case for interactive data exploration accelerators (ideas). In: Proceedings of the Workshop on Human-In-the-Loop Data Analytics, p.\u00a011. ACM (2016)","DOI":"10.1145\/2939502.2939513"},{"issue":"7","key":"582_CR17","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1145\/1538788.1538810","volume":"52","author":"N Dalvi","year":"2009","unstructured":"Dalvi, N., R\u00e9, C., Suciu, D.: Probabilistic databases: diamonds in the dirt. Commun. ACM 52(7), 86\u201394 (2009)","journal-title":"Commun. ACM"},{"key":"582_CR18","doi-asserted-by":"crossref","unstructured":"Deshpande, A., Garofalakis, M.N., Rastogi, R.: Independence is good: dependency-based histogram synopses for high-dimensional data. In: SIGMOD Conference (2001)","DOI":"10.1145\/375663.375685"},{"key":"582_CR19","doi-asserted-by":"crossref","unstructured":"Ding, B., Huang, S., Chaudhuri, S., Chakrabarti, K., Wang, C.: Sample+seek: approximating aggregates with distribution precision guarantee. In: Proceedings of SIGMOD, pp. 679\u2013694 (2016)","DOI":"10.1145\/2882903.2915249"},{"key":"582_CR20","unstructured":"Dwork, C., Feldman, V., Hardt, M., Pitassi, T., Reingold, O., Roth, A.: Generalization in adaptive data analysis and holdout reuse. In: Advances in Neural Information Processing Systems, pp. 2350\u20132358 (2015)"},{"issue":"10","key":"582_CR21","doi-asserted-by":"publisher","first-page":"1142","DOI":"10.14778\/3115404.3115418","volume":"10","author":"A Galakatos","year":"2017","unstructured":"Galakatos, A., Crotty, A., Zgraggen, E., Binnig, C., Kraska, T.: Revisiting reuse for approximate query processing. Proc. VLDB Endow. 10(10), 1142\u20131153 (2017)","journal-title":"Proc. VLDB Endow."},{"key":"582_CR22","doi-asserted-by":"crossref","unstructured":"Hardt, M., Rothblum, G.N.: A multiplicative weights mechanism for privacy-preserving data analysis. In: 2010 51st Annual IEEE Symposium on, Foundations of Computer Science (FOCS), pp. 61\u201370. IEEE (2010)","DOI":"10.1109\/FOCS.2010.85"},{"key":"582_CR23","doi-asserted-by":"crossref","unstructured":"Hellerstein, J.M., Haas, P.J., Wang, H.J.: Online aggregation. In: ACM SIGMOD Record, vol.\u00a026, pp. 171\u2013182. ACM (1997)","DOI":"10.1145\/253262.253291"},{"key":"582_CR24","unstructured":"Hosangadi, A., Fallah, F., Kastner, R.: Factoring and eliminating common subexpressions in polynomial expressions. In: IEEE\/ACM International Conference on Computer Aided Design, 2004. ICCAD-2004 (2004)"},{"issue":"4","key":"582_CR25","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1145\/1412331.1412335","volume":"33","author":"C Jermaine","year":"2008","unstructured":"Jermaine, C., Arumugam, S., Pol, A., Dobra, A.: Scalable approximate query processing with the DBO engine. ACM Trans. Database Syst. (TODS) 33(4), 23 (2008)","journal-title":"ACM Trans. Database Syst. (TODS)"},{"key":"582_CR26","unstructured":"http:\/\/www.transtats.bts.gov\/"},{"key":"582_CR27","doi-asserted-by":"crossref","unstructured":"Jetley, P. et al.: Massively parallel cosmological simulations with ChaNGa. In: Proceedings of IPDPS (2008)","DOI":"10.1109\/IPDPS.2008.4536319"},{"key":"582_CR28","unstructured":"Jordan, M.: An introduction to probabilistic graphical models (2003). \nhttp:\/\/www.cs.cmu.edu\/~lebanon\/pub\/book\/\n\n. Accessed 10 Nov 2018"},{"key":"582_CR29","doi-asserted-by":"crossref","unstructured":"Kandula, S., Shanbhag, A., Vitorovic, A., Olma, M., Grandl, R., Chaudhuri, S., Ding, B.: Quickr: lazily approximating complex adhoc queries in bigdata clusters. In: Proceedings of the 2016 International Conference on Management of Data, pp. 631\u2013646. ACM (2016)","DOI":"10.1145\/2882903.2882940"},{"key":"582_CR30","unstructured":"Kipf, A., Kipf, T., Radke, B., Leis, V., Boncz, P., Kemper, A.: Learned cardinalities: estimating correlated joins with deep learning (2018). arXiv preprint \narXiv:1809.00677"},{"key":"582_CR31","doi-asserted-by":"crossref","unstructured":"Li, C., et al.: Optimizing linear counting queries under differential privacy. In: Proceedings of PODS, pp. 123\u2013134 (2010)","DOI":"10.1145\/1807085.1807104"},{"issue":"4","key":"582_CR32","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/s41019-018-0074-4","volume":"3","author":"K Li","year":"2018","unstructured":"Li, K., Li, G.: Approximate query processing: what is new and where to go? Data Sci. Eng. 3(4), 379\u2013397 (2018)","journal-title":"Data Sci. Eng."},{"issue":"12","key":"582_CR33","doi-asserted-by":"publisher","first-page":"2262","DOI":"10.1109\/TKDE.2018.2877362","volume":"31","author":"Kaiyu Li","year":"2019","unstructured":"Li, K., Zhang, Y., Li, G., Tao, W., Yan, Y.: Bounded approximate query processing. IEEE Trans. Knowl. Data Eng. (2018). \nhttps:\/\/doi.org\/10.1109\/TKDE.2018.2877362","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"582_CR34","doi-asserted-by":"crossref","unstructured":"M\u00e4kinen, E., Siirtola, H.: Reordering the reorderable matrix as an algorithmic problem. In: International Conference on Theory and Application of Diagrams, pp. 453\u2013468. Springer (2000)","DOI":"10.1007\/3-540-44590-0_37"},{"key":"582_CR35","unstructured":"Markl, V., et al.: Consistently estimating the selectivity of conjuncts of predicates. In: Proceedings of VLDB, pp. 373\u2013384. VLDB Endowment (2005)"},{"issue":"3","key":"582_CR36","first-page":"3","volume":"38","author":"B Mozafari","year":"2015","unstructured":"Mozafari, B., Niu, N.: A handbook for building an approximate query engine. IEEE Data Eng. Bull. 38(3), 3\u201329 (2015)","journal-title":"IEEE Data Eng. Bull."},{"key":"582_CR37","unstructured":"Murphy, K.: Undirected graphical models (2006). \nhttps:\/\/www.cs.ubc.ca\/~murphyk\/Teaching\/CS340-Fall06\/reading\/ugm.pdf\n\n. Accessed 19 Nov 2018"},{"issue":"10","key":"582_CR38","doi-asserted-by":"publisher","first-page":"1154","DOI":"10.14778\/3115404.3115419","volume":"10","author":"L Orr","year":"2017","unstructured":"Orr, L., Balazinska, M., Suciu, D.: Probabilistic database summarization for interactive data exploration. Proc. VLDB Endow. 10(10), 1154\u20131165 (2017)","journal-title":"Proc. VLDB Endow."},{"key":"582_CR39","unstructured":"Ortiz, J., Balazinska, M., Gehrke, J., Keerthi, S.S.: Learning state representations for query optimization with deep reinforcement learning (2018). arXiv preprint \narXiv:1803.08604"},{"key":"582_CR40","doi-asserted-by":"crossref","unstructured":"Park, Y., Mozafari, B., Sorenson, J., Wang, J.: Verdictdb: universalizing approximate query processing. In: Proceedings of the 2018 International Conference on Management of Data, pp. 1461\u20131476. ACM (2018)","DOI":"10.1145\/3183713.3196905"},{"key":"582_CR41","doi-asserted-by":"crossref","unstructured":"Peng, J., Zhang, D., Wang, J., Pei, J.: Aqp++: connecting approximate query processing with aggregate precomputation for interactive analytics. In: Proceedings of the 2018 International Conference on Management of Data, pp. 1477\u20131492. ACM (2018)","DOI":"10.1145\/3183713.3183747"},{"issue":"1","key":"582_CR42","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1145\/2109196.2109202","volume":"37","author":"C R\u00e9","year":"2012","unstructured":"R\u00e9, C., Suciu, D.: Understanding cardinality estimation using entropy maximization. ACM TODS 37(1), 6 (2012)","journal-title":"ACM TODS"},{"issue":"2","key":"582_CR43","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2200\/S00362ED1V01Y201105DTM016","volume":"3","author":"D Suciu","year":"2011","unstructured":"Suciu, D., Olteanu, D., R\u00e9, C., Koch, C.: Probabilistic databases. Synth. Lect. Data Manag. 3(2), 1\u2013180 (2011)","journal-title":"Synth. Lect. Data Manag."},{"key":"582_CR44","unstructured":"Teh, Y.W., Welling, M.: On improving the efficiency of the iterative proportional fitting procedure. In: AIStats (2003)"},{"key":"582_CR45","unstructured":"Thirumuruganathan, S., Hasan, S., Koudas, N., Das, G.: Approximate query processing using deep generative models (2019). arXiv preprint \narXiv:1903.10000"},{"issue":"1","key":"582_CR46","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00778-012-0293-7","volume":"22","author":"K Tzoumas","year":"2013","unstructured":"Tzoumas, K., Deshpande, A., Jensen, C.S.: Efficiently adapting graphical models for selectivity estimation. VLDB J. 22(1), 3\u201327 (2013)","journal-title":"VLDB J."},{"issue":"1\u20132","key":"582_CR47","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/2200000001","volume":"1","author":"MJ Wainwright","year":"2008","unstructured":"Wainwright, M.J., Jordan, M.I.: Graphical models, exponential families, and variational inference. Found. Trends Mach. Learn. 1(1\u20132), 1\u2013305 (2008)","journal-title":"Found. Trends Mach. Learn."},{"key":"582_CR48","unstructured":"Wu, M., Jermaine, C.: A Bayesian method for guessing the extreme values in a data set? In: Proceedings of the 33rd International Conference on Very Large Data Bases, pp. 471\u2013482. VLDB Endowment (2007)"},{"issue":"1","key":"582_CR49","first-page":"3813","volume":"16","author":"E Yang","year":"2015","unstructured":"Yang, E., Ravikumar, P., Allen, G.I., Liu, Z.: Graphical models via univariate exponential family distributions. J. Mach. Learn. Res. 16(1), 3813\u20133847 (2015)","journal-title":"J. Mach. Learn. Res."}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-019-00582-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00778-019-00582-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-019-00582-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,1]],"date-time":"2020-11-01T00:59:56Z","timestamp":1604192396000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00778-019-00582-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,2]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["582"],"URL":"https:\/\/doi.org\/10.1007\/s00778-019-00582-9","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,2]]},"assertion":[{"value":"1 December 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 October 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 November 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}