{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:50:59Z","timestamp":1773481859644,"version":"3.50.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2020,3,6]],"date-time":"2020-03-06T00:00:00Z","timestamp":1583452800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,3,6]],"date-time":"2020-03-06T00:00:00Z","timestamp":1583452800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Knowl Inf Syst"],"published-print":{"date-parts":[[2020,8]]},"DOI":"10.1007\/s10115-020-01450-7","type":"journal-article","created":{"date-parts":[[2020,3,6]],"date-time":"2020-03-06T10:03:08Z","timestamp":1583488988000},"page":"3155-3180","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["SUM-optimal histograms for approximate query processing"],"prefix":"10.1007","volume":"62","author":[{"given":"Meifan","family":"Zhang","sequence":"first","affiliation":[]},{"given":"Hongzhi","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Jianzhong","family":"Li","sequence":"additional","affiliation":[]},{"given":"Hong","family":"Gao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,3,6]]},"reference":[{"key":"1450_CR1","doi-asserted-by":"crossref","unstructured":"Acharya J, Diakonikolas I, Hegde C, Li JZ, Schmidt L (2015) Fast and near-optimal algorithms for approximating distributions by histograms. In: Proceedings of the 34th ACM symposium on principles of database systems, PODS 2015, Melbourne, Victoria, Australia, May 31\u2013June 4, 2015, pp 249\u2013263","DOI":"10.1145\/2745754.2745772"},{"key":"1450_CR2","doi-asserted-by":"crossref","unstructured":"Acharya S, Gibbons PB, Poosala V (2000) Congressional samples for approximate answering of group-by queries. In: Proceedings of the 2000 ACM SIGMOD international conference on management of data, May 16\u201318, 2000, Dallas, TX, USA, pp 487\u2013498","DOI":"10.1145\/342009.335450"},{"key":"1450_CR3","doi-asserted-by":"crossref","unstructured":"Acharya S, Gibbons PB, Poosala V, Ramaswamy S (1999) The aqua approximate query answering system. In: SIGMOD 1999, proceedings ACM SIGMOD international conference on management of data, June 1\u20133, 1999, Philadelphia, PA, USA, pp 574\u2013576","DOI":"10.1145\/304182.304581"},{"key":"1450_CR4","doi-asserted-by":"crossref","unstructured":"Agarwal S, Mozafari B, Panda A, Milner H, Madden S, Stoica I (2013) Blinkdb: queries with bounded errors and bounded response times on very large data. In: Eighth Eurosys conference 2013, EuroSys\u201913, Prague, Czech Republic, April 14\u201317, 2013, pp 29\u201342","DOI":"10.1145\/2465351.2465355"},{"key":"1450_CR5","unstructured":"Agrawal R, Swami AN (1995) A one-pass space-efficient algorithm for finding quantiles. In: COMAD"},{"issue":"7","key":"1450_CR6","doi-asserted-by":"publisher","first-page":"1082","DOI":"10.1016\/j.is.2011.03.007","volume":"36","author":"F Buccafurri","year":"2011","unstructured":"Buccafurri F, Furfaro F, Mazzeo GM, Sacc\u00e0 D (2011) A quad-tree based multiresolution approach for two-dimensional summary data. Inf Syst 36(7):1082\u20131103","journal-title":"Inf Syst"},{"issue":"5","key":"1450_CR7","doi-asserted-by":"publisher","first-page":"1041","DOI":"10.1007\/s00778-007-0050-5","volume":"17","author":"F Buccafurri","year":"2008","unstructured":"Buccafurri F, Lax G, Sacc\u00e0 D, Pontieri L, Rosaci D (2008) Enhancing histograms by tree-like bucket indices. VLDB J 17(5):1041\u20131061","journal-title":"VLDB J"},{"issue":"2","key":"1450_CR8","first-page":"1265","volume":"1","author":"R Chaiken","year":"2008","unstructured":"Chaiken R, Jenkins B, Larson P\u00c5, Ramsey B, Shakib D, Weaver S, Zhou J (2008) SCOPE: easy and efficient parallel processing of massive data sets. PVLDB 1(2):1265\u20131276","journal-title":"PVLDB"},{"key":"1450_CR9","doi-asserted-by":"crossref","unstructured":"Chaudhuri S, Das G, Datar M, Motwani R, Narasayya VR (2001) Overcoming limitations of sampling for aggregation queries. In: Proceedings of the 17th international conference on data engineering, April 2\u20136, 2001, Heidelberg, Germany, pp 534\u2013542","DOI":"10.1109\/ICDE.2001.914867"},{"key":"1450_CR10","doi-asserted-by":"crossref","unstructured":"Chaudhuri S, Das G, Narasayya VR (2001) A robust, optimization-based approach for approximate answering of aggregate queries. In: Proceedings of the 2001 ACM SIGMOD international conference on management of data, Santa Barbara, CA, USA, May 21\u201324, 2001, pp 295\u2013306","DOI":"10.1145\/375663.375694"},{"key":"1450_CR11","doi-asserted-by":"crossref","unstructured":"Chaudhuri S, Ding B, Kandula S (2017) Approximate query processing: no silver bullet. In: Proceedings of the 2017 ACM international conference on management of data, SIGMOD conference 2017, Chicago, IL, USA, May 14\u201319, 2017, pp 511\u2013519","DOI":"10.1145\/3035918.3056097"},{"key":"1450_CR12","doi-asserted-by":"crossref","unstructured":"Chaudhuri S, Motwani R, Narasayya VR (1998) Random sampling for histogram construction: How much is enough? In: SIGMOD 1998, proceedings ACM SIGMOD international conference on management of data, June 2\u20134, 1998, Seattle, Washington, USA, pp 436\u2013447","DOI":"10.1145\/276305.276343"},{"issue":"1\u20133","key":"1450_CR13","first-page":"1","volume":"4","author":"G Cormode","year":"2012","unstructured":"Cormode G, Garofalakis MN, Haas PJ, Jermaine C (2012) Synopses for massive data: samples, histograms, wavelets, sketches. Found Trends Databases 4(1\u20133):1\u2013294","journal-title":"Found Trends Databases"},{"issue":"2","key":"1450_CR14","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1109\/TDSC.2017.2693969","volume":"16","author":"X Ding","year":"2019","unstructured":"Ding X, Liu P, Jin H (2019) Privacy-preserving multi-keyword top-$$k$$ k similarity search over encrypted data. IEEE Trans Dependable Sec Comput 16(2):344\u2013357","journal-title":"IEEE Trans Dependable Sec Comput"},{"key":"1450_CR15","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.ins.2019.03.035","volume":"493","author":"X Ding","year":"2019","unstructured":"Ding X, Yang W, Choo K-KR, Wang X, Jin H (2019) Privacy preserving similarity joins using mapreduce. Inf Sci 493:20\u201333","journal-title":"Inf Sci"},{"issue":"10","key":"1450_CR16","first-page":"1142","volume":"10","author":"A Galakatos","year":"2017","unstructured":"Galakatos A, Crotty A, Zgraggen E, Binnig C, Kraska T (2017) Revisiting reuse for approximate query processing. PVLDB 10(10):1142\u20131153","journal-title":"PVLDB"},{"issue":"3","key":"1450_CR17","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1145\/581751.581753","volume":"27","author":"PB Gibbons","year":"2002","unstructured":"Gibbons PB, Matias Y, Poosala V (2002) Fast incremental maintenance of approximate histograms. ACM Trans Database Syst 27(3):261\u2013298","journal-title":"ACM Trans Database Syst"},{"key":"1450_CR18","doi-asserted-by":"crossref","unstructured":"Gilbert AC, Guha S, Indyk P, Kotidis Y, Muthukrishnan S, Strauss M (2002) Fast, small-space algorithms for approximate histogram maintenance. In: STOC. ACM, New York, pp 389\u2013398","DOI":"10.1145\/509907.509966"},{"key":"1450_CR19","doi-asserted-by":"crossref","unstructured":"Greenwald M, Khanna S (2001) Space-efficient online computation of quantile summaries. In: Proceedings of the 2001 ACM SIGMOD international conference on management of data, Santa Barbara, CA, USA, May 21\u201324, 2001, pp 58\u201366","DOI":"10.1145\/375663.375670"},{"issue":"1","key":"1450_CR20","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1145\/1132863.1132873","volume":"31","author":"S Guha","year":"2006","unstructured":"Guha S, Koudas N, Shim K (2006) Approximation and streaming algorithms for histogram construction problems. ACM Trans Database Syst 31(1):396\u2013438","journal-title":"ACM Trans Database Syst"},{"key":"1450_CR21","doi-asserted-by":"crossref","unstructured":"Indyk P, Levi R, Rubinfeld R (2012) Approximating and testing $$k$$-histogram distributions in sub-linear time. In: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART symposium on principles of database systems, PODS 2012, Scottsdale, AZ, USA, May 20\u201324, 2012, pp 15\u201322","DOI":"10.1145\/2213556.2213561"},{"key":"1450_CR22","unstructured":"Ioannidis YE, Poosala V (1995) Balancing histogram optimality and practicality for query result size estimation. In: Proceedings of the 1995 ACM SIGMOD international conference on management of data, San Jose, California, May 22\u201325, 1995, pp 233\u2013244"},{"key":"1450_CR23","unstructured":"Jagadish HV, Koudas N, Muthukrishnan S, Poosala V, Sevcik KC, Suel T (1998) Optimal histograms with quality guarantees. In: VLDB\u201998, proceedings of 24th international conference on very large data bases, August 24\u201327, 1998, New York City, NY, USA, pp 275\u2013286"},{"key":"1450_CR24","unstructured":"Joseph AG, Bhatnagar S (2015) A stochastic approximation algorithm for quantile estimation. In: Neural information processing\u201422nd international conference, ICONIP 2015, Istanbul, Turkey, November 9\u201312, 2015, Proceedings, Part II, pp 311\u2013319"},{"issue":"4","key":"1450_CR25","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 (2018) Approximate query processing: What is new and where to go? A survey on approximate query processing. Data Sci Eng 3(4):379\u2013397","journal-title":"Data Sci Eng"},{"key":"1450_CR26","doi-asserted-by":"crossref","unstructured":"Ma Q, Triantafillou P (2019) Dbest: revisiting approximate query processing engines with machine learning models. In: Proceedings of the 2019 international conference on management of data, SIGMOD conference 2019, Amsterdam, The Netherlands, June 30\u2013July 5, 2019, pp 1553\u20131570","DOI":"10.1145\/3299869.3324958"},{"issue":"6","key":"1450_CR27","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/1953122.1953148","volume":"54","author":"S Melnik","year":"2011","unstructured":"Melnik S, Gubarev A, Long JJ, Romer G, Shivakumar S, Tolton M, Vassilakis T (2011) Dremel: interactive analysis of web-scale datasets. Commun ACM 54(6):114\u2013123","journal-title":"Commun ACM"},{"key":"1450_CR28","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0304-3975(80)90061-4","volume":"12","author":"JI Munro","year":"1980","unstructured":"Munro JI, Paterson M (1980) Selection and sorting with limited storage. Theor Comput Sci 12:315\u2013323","journal-title":"Theor Comput Sci"},{"key":"1450_CR29","doi-asserted-by":"crossref","unstructured":"Muthukrishnan S, Poosala V, Suel T (1999) On rectangular partitionings in two dimensions: algorithms, complexity, and applications. In: Database Theory\u2014ICDT\u201999, 7th international conference, Jerusalem, Israel, January 10\u201312, 1999, Proceedings, pp 236\u2013256","DOI":"10.1007\/3-540-49257-7_16"},{"key":"1450_CR30","doi-asserted-by":"crossref","unstructured":"Olma M, Papapetrou O, Appuswamy R, Ailamaki A (2019) Taster: self-tuning, elastic and online approximate query processing. In: 35th IEEE international conference on data engineering, ICDE 2019, Macao, China, April 8\u201311, 2019, pp 482\u2013493","DOI":"10.1109\/ICDE.2019.00050"},{"key":"1450_CR31","doi-asserted-by":"crossref","unstructured":"Olston C, Reed B, Srivastava U, Kumar R, Tomkins A (2008) Pig latin: a not-so-foreign language for data processing. In: Proceedings of the ACM SIGMOD international conference on management of data, SIGMOD 2008, Vancouver, BC, Canada, June 10\u201312, 2008, pp 1099\u20131110","DOI":"10.1145\/1376616.1376726"},{"issue":"11","key":"1450_CR32","first-page":"443","volume":"197","author":"K Pearson","year":"1901","unstructured":"Pearson K (1901) Mathematical contributions to the theory of evolution. X. Supplement to a memoir on skew variation. Philos Trans R Soc Lond 197(11):443\u2013459","journal-title":"Philos Trans R Soc Lond"},{"key":"1450_CR33","doi-asserted-by":"crossref","unstructured":"Peng J, Zhang D, Wang J, Pei J (2018) AQP++: connecting approximate query processing with aggregate precomputation for interactive analytics. In: Proceedings of the 2018 international conference on management of data, SIGMOD conference 2018, Houston, TX, USA, June 10\u201315, 2018, pp 1477\u20131492","DOI":"10.1145\/3183713.3183747"},{"key":"1450_CR34","doi-asserted-by":"crossref","unstructured":"Piatetsky-Shapiro G, Connell C (1984) Accurate estimation of the number of tuples satisfying a condition. In: SIGMOD\u201984, proceedings of annual meeting, Boston, MA, June 18\u201321, 1984, pp 256\u2013276","DOI":"10.1145\/602259.602294"},{"key":"1450_CR35","unstructured":"Poosala V, Ioannidis YE (1996) Estimation of query-result distribution and its application in parallel-join load balancing. In: VLDB\u201996, proceedings of 22nd international conference on very large data bases, September 3\u20136, 1996, Mumbai (Bombay), India, pp 448\u2013459"},{"key":"1450_CR36","doi-asserted-by":"crossref","unstructured":"Poosala V, Ioannidis YE, Haas PJ, Shekita EJ (1996) Improved histograms for selectivity estimation of range predicates. In: Proceedings of the 1996 ACM SIGMOD international conference on management of data, Montreal, Quebec, Canada, June 4\u20136, 1996, pp 294\u2013305","DOI":"10.1145\/233269.233342"},{"issue":"3","key":"1450_CR37","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1214\/aoms\/1177729586","volume":"22","author":"H Robbins","year":"1951","unstructured":"Robbins H, Monro S (1951) A stochastic approximation method. Ann Math Stat 22(3):400\u2013407","journal-title":"Ann Math Stat"},{"issue":"11","key":"1450_CR38","first-page":"1514","volume":"10","author":"M Shekelyan","year":"2017","unstructured":"Shekelyan M, Dign\u00f6s A, Gamper J (2017) Digithist: a histogram-based data summary with tight error bounds. PVLDB 10(11):1514\u20131525","journal-title":"PVLDB"},{"key":"1450_CR39","unstructured":"Sidirourgos L, Kersten ML, Boncz PA (2011) Sciborq: scientific data management with bounds on runtime and quality. In: CIDR 2011, 5th biennial conference on innovative data systems research, Asilomar, CA, USA, January 9\u201312, 2011, online proceedings, pp 296\u2013301"},{"issue":"1","key":"1450_CR40","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/s41019-018-0060-x","volume":"3","author":"G Song","year":"2018","unstructured":"Song G, Wenwen Q, Liu X, Wang X (2018) Approximate calculation of window aggregate functions via global random sample. Data Sci Eng 3(1):40\u201351","journal-title":"Data Sci Eng"},{"key":"1450_CR41","doi-asserted-by":"crossref","unstructured":"To H, Chiang K, Shahabi C (2013) Entropy-based histograms for selectivity estimation. In: 22nd ACM international conference on information and knowledge management, CIKM\u201913, San Francisco, CA, USA, October 27\u2013November 1, 2013, pp 1939\u20131948","DOI":"10.1145\/2505515.2505756"},{"key":"1450_CR42","unstructured":"Yildiz B, B\u00fcy\u00fcktanir T, Emek\u00e7i F (2016) Equi-depth histogram construction for big data with quality guarantees. CoRR arXiv:1606.05633"}],"container-title":["Knowledge and Information Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-020-01450-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10115-020-01450-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-020-01450-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,6]],"date-time":"2021-03-06T00:35:29Z","timestamp":1614990929000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10115-020-01450-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,6]]},"references-count":42,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2020,8]]}},"alternative-id":["1450"],"URL":"https:\/\/doi.org\/10.1007\/s10115-020-01450-7","relation":{},"ISSN":["0219-1377","0219-3116"],"issn-type":[{"value":"0219-1377","type":"print"},{"value":"0219-3116","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,6]]},"assertion":[{"value":"27 October 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 February 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 February 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 March 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}