{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,25]],"date-time":"2026-06-25T18:55:30Z","timestamp":1782413730637,"version":"3.54.5"},"reference-count":299,"publisher":"Emerald","issue":"1-3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011,12,31]]},"abstract":"<jats:p>Methods for Approximate Query Processing (AQP) are essential for dealing with massive data. They are often the only means of providing interactive response times when exploring massive datasets, and are also needed to handle high speed data streams. These methods proceed by computing a lossy, compact synopsis of the data, and then executing the query of interest against the synopsis rather than the entire dataset. We describe basic principles and recent developments in AQP. We focus on four key synopses: random samples, histograms, wavelets, and sketches. We consider issues such as accuracy, space and time efficiency, optimality, practicality, range of applicability, error bounds on query answers, and incremental maintenance. We also discuss the tradeoffs between the different synopsis types.<\/jats:p>","DOI":"10.1561\/1900000004","type":"journal-article","created":{"date-parts":[[2012,3,9]],"date-time":"2012-03-09T07:36:17Z","timestamp":1331278577000},"page":"1-294","source":"Crossref","is-referenced-by-count":262,"title":["Synopses for Massive Data: Samples, Histograms, Wavelets, Sketches"],"prefix":"10.1108","volume":"4","author":[{"given":"Graham","family":"Cormode","sequence":"first","affiliation":[{"name":"AT&T Labs \u2014 Research , 180 Park Avenue, Florham Park, NJ 07932,","place":["USA"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Minos","family":"Garofalakis","sequence":"additional","affiliation":[{"name":"Technical University of Crete, University Campus \u2014 Kounoupidiana , Chania, 73100,","place":["Greece"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter J.","family":"Haas","sequence":"additional","affiliation":[{"name":"IBM Almaden Research Center , 650 Harry Road, San Jose, CA 95120-6099,","place":["USA"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chris","family":"Jermaine","sequence":"additional","affiliation":[{"name":"Rice University , 6100 Main Street, Houston, TX 77005,","place":["USA"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"140","published-online":{"date-parts":[[2011,12,31]]},"reference":[{"issue":"1","key":"2025121112222085500_ref001","first-page":"922","article-title":"HadoopDB: An architectural hybrid of MapReduce and DBMS technologies for analytical workloads","volume":"2","author":"Abouzeid","year":"2009","journal-title":"PVLDB"},{"key":"2025121112222085500_ref002","article-title":"Aqua: A fast decision support system using approximate query answers","volume-title":"International Conference on Very Large Data Bases","author":"Acharya","year":"1999"},{"key":"2025121112222085500_ref003","doi-asserted-by":"crossref","DOI":"10.1145\/304182.304581","article-title":"The Aqua approximate query answering system","volume-title":"ACM SIGMOD International Conference on Management of Data","author":"Acharya","year":"1999"},{"key":"2025121112222085500_ref004","first-page":"275","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Acharya","year":"1999"},{"key":"2025121112222085500_ref005","first-page":"607","article-title":"On biased reservoir sampling in the presence of stream evolution","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Aggarwal","year":"2006"},{"key":"2025121112222085500_ref006","doi-asserted-by":"crossref","DOI":"10.1145\/303976.303978","article-title":"Tracking join and self-join sizes in limited storage","volume-title":"ACM Principles of Database Systems","author":"Alon","year":"1999"},{"key":"2025121112222085500_ref007","doi-asserted-by":"crossref","DOI":"10.1145\/237814.237823","article-title":"The space complexity of approximating the frequency moments","volume-title":"ACM Symposium on Theory of Computing","author":"Alon","year":"1996"},{"key":"2025121112222085500_ref008","article-title":"Streaming algorithms from precision sampling","volume-title":"CoRR","author":"Andoni","year":"2010"},{"key":"2025121112222085500_ref009","first-page":"375","article-title":"Random sampling from pseudo-ranked B+ trees","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Antoshenkov","year":"1992"},{"key":"2025121112222085500_ref010","first-page":"258","article-title":"Algorithms for index-assisted selectivity estimation","volume-title":"Proceedings of the International Conference on Data Engineering","author":"Aoki","year":"1999"},{"key":"2025121112222085500_ref011","first-page":"567","article-title":"CONTROL: Continuous output and navigation technology with refinement on-line","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Avnur","year":"1998"},{"key":"2025121112222085500_ref012","doi-asserted-by":"crossref","DOI":"10.1145\/543613.543615","article-title":"Models and issues in data stream systems","volume-title":"ACM Principles of Database Systems","author":"Babcock","year":"2002"},{"key":"2025121112222085500_ref013","first-page":"539","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Babcock","year":"2003"},{"key":"2025121112222085500_ref014","first-page":"633","article-title":"Sampling from a moving window over streaming data","volume-title":"SODA","author":"Babcock","year":"2002"},{"key":"2025121112222085500_ref015","first-page":"198","article-title":"Green: A framework for supporting energyconscious programming using controlled approximation","volume-title":"Proceedings of PLDI","author":"Baek","year":"2010"},{"key":"2025121112222085500_ref016","first-page":"105","article-title":"Multi-dimensional histograms with tight bounds for the error","volume-title":"Proceedings of IDEAS","author":"Baltrunas","year":"2006"},{"key":"2025121112222085500_ref017","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-45726-7_1","article-title":"Counting distinct elements in a data stream","volume-title":"Proceedings of RANDOM 2002","author":"Bar-Yossef","year":"2002"},{"issue":"6","key":"2025121112222085500_ref018","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1145\/366573.366611","article-title":"On the approximation of curves by line segments using dynamic programming","volume":"4","author":"Bellman","year":"1961","journal-title":"Communications of ACM"},{"key":"2025121112222085500_ref019","doi-asserted-by":"crossref","DOI":"10.1145\/1247480.1247504","article-title":"On synopses for distinct-value estimation under multiset operations","volume-title":"ACM SIGMOD International Conference on Management of Data","author":"Beyer","year":"2007"},{"key":"2025121112222085500_ref020","article-title":"How to scalably skip past streams","volume-title":"Scalable Stream Processing Systems (SSPS) Workshop with ICDE 2007","author":"Bhattacharrya","year":"2007"},{"key":"2025121112222085500_ref021","doi-asserted-by":"crossref","DOI":"10.1145\/1109557.1109634","article-title":"Simpler algorithm for estimating frequency moments of data streams","volume-title":"ACM-SIAM Symposium on Discrete Algorithms","author":"Bhuvanagiri","year":"2006"},{"key":"2025121112222085500_ref022","volume-title":"Probability and Measure","author":"Billingsley","year":"1999","edition":"third ed"},{"key":"2025121112222085500_ref023","first-page":"239","article-title":"A comparison of selectivity estimators for range queries on metric attributes","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Blohsfeld","year":"1999"},{"issue":"7","key":"2025121112222085500_ref024","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1145\/362686.362692","article-title":"Space\/time trade-offs in hash coding with allowable errors","volume":"13","author":"Bloom","year":"1970","journal-title":"Communications of the ACM"},{"key":"2025121112222085500_ref025","article-title":"Min-wise independent permutations","volume-title":"ACM Symposium on Theory of Computing","author":"Broder","year":"1998"},{"issue":"4","key":"2025121112222085500_ref026","doi-asserted-by":"crossref","DOI":"10.1080\/15427951.2004.10129096","article-title":"Network applications of bloom filters: A survey","volume":"1","author":"Broder","year":"2003","journal-title":"Internet Mathematics"},{"key":"2025121112222085500_ref027","volume-title":"Proceedings of the International Conference on Data Engineering","author":"Brown","year":"2006"},{"key":"2025121112222085500_ref028","first-page":"6","article-title":"The estimates of Laplace. an example: Research concerning the population of a large empire, 1785-1812","volume":"129","author":"Bru","year":"1988","journal-title":"Journal de la Soci\u00e9t\u00e9 de statistique de Paris"},{"key":"2025121112222085500_ref029","first-page":"263","article-title":"Exploiting statistics on query expressions for optimization","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Bruno","year":"2002"},{"key":"2025121112222085500_ref030","first-page":"211","article-title":"STHoles: A multidimensional workload-aware histogram","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Bruno","year":"2001"},{"key":"2025121112222085500_ref031","doi-asserted-by":"crossref","DOI":"10.1109\/INFCOM.2007.220","article-title":"A fast and compact method for unveiling significant patterns in high speed networks","volume-title":"IEEE INFOCOMM","author":"Bu","year":"2007"},{"key":"2025121112222085500_ref032","doi-asserted-by":"crossref","first-page":"861","DOI":"10.1007\/3-540-46146-9_85","article-title":"Binary-tree histograms with tree indices","volume-title":"Proceedings of Database and Expert Systems Applications","author":"Buccafurri","year":"2002"},{"key":"2025121112222085500_ref033","first-page":"390","article-title":"Estimating range queries using aggregate data with integrity constraints: A probabilistic approach","volume-title":"Proceedings of the International Conference on Database Theory","author":"Buccafurri","year":"2001"},{"key":"2025121112222085500_ref034","first-page":"127","article-title":"A quad-tree based multiresolution approach for two-dimensional summary data","volume-title":"Proceedings of the International Conference on Scientific and Statistical Database Management","author":"Buccafurri","year":"2003"},{"issue":"2","key":"2025121112222085500_ref035","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/j.datak.2004.04.004","article-title":"Fast range query estimation by n-level tree histograms","volume":"51","author":"Buccafurri","year":"2004","journal-title":"Data Knowledge in Engineering"},{"key":"2025121112222085500_ref036","first-page":"75","article-title":"Reducing data stream sliding windows by cyclic tree-like histograms","volume-title":"PKDD","author":"Buccafurri","year":"2004"},{"issue":"5","key":"2025121112222085500_ref037","doi-asserted-by":"crossref","first-page":"1041","DOI":"10.1007\/s00778-007-0050-5","article-title":"Enhancing histograms by tree-like bucket indices","volume":"17","author":"Buccafurri","year":"2008","journal-title":"VLDB Journal"},{"key":"2025121112222085500_ref038","first-page":"1026","article-title":"Space efficient streaming algorithms for the maximum error histogram","volume-title":"Proceedings of the International Conference on Data Engineering","author":"Buragohain","year":"2007"},{"issue":"2","key":"2025121112222085500_ref039","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","article-title":"Universal classes of hash functions","volume":"18","author":"Carter","year":"1979","journal-title":"Journal of Computer and System Sciences"},{"key":"2025121112222085500_ref040","article-title":"A near-optimal algorithm for computing the entropy of a stream","volume-title":"ACM-SIAM Symposium on Discrete Algorithms","author":"Chakrabarti","year":"2007"},{"key":"2025121112222085500_ref041","first-page":"111","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Chakrabarti","year":"2000"},{"issue":"2-3","key":"2025121112222085500_ref042","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/s007780100049","article-title":"Approximate query processing using wavelets","volume":"10","author":"Chakrabarti","year":"2001","journal-title":"The VLDB Journal"},{"key":"2025121112222085500_ref043","volume-title":"A Complete Guide to DB2 Universal Database","author":"Chamberlin","year":"1998"},{"key":"2025121112222085500_ref044","first-page":"268","article-title":"Towards estimation error guarantees for distinct values","volume-title":"Proceedings of ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems","author":"Charikar","year":"2000"},{"key":"2025121112222085500_ref045","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-45465-9_59","article-title":"Finding frequent items in data streams","volume-title":"International Colloquium on Automata, Languages and Programming","author":"Charikar","year":"2002"},{"issue":"1","key":"2025121112222085500_ref046","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0304-3975(03)00400-6","article-title":"Finding frequent items in data streams","volume":"312","author":"Charikar","year":"2004","journal-title":"Theoretical Computer Science"},{"key":"2025121112222085500_ref047","first-page":"295","article-title":"A robust, optimization-based approach for approximate answering of aggregate queries","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Chaudhuri","year":"2001"},{"issue":"2","key":"2025121112222085500_ref048","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1145\/1242524.1242526","article-title":"Optimized stratified sampling for approximate query processing","volume":"32","author":"Chaudhuri","year":"2007","journal-title":"ACM Transactions on Database Systems"},{"key":"2025121112222085500_ref049","first-page":"287","article-title":"Effective use of block-level sampling in statistics estimation","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Chaudhuri","year":"2004"},{"issue":"2","key":"2025121112222085500_ref050","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1145\/304181.304206","article-title":"On random sampling over joins","volume":"28","author":"Chaudhuri","year":"1999","journal-title":"SIGMOD Record"},{"key":"2025121112222085500_ref051","first-page":"436","article-title":"Random sampling for histogram construction: How much is enough?","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Chaudhuri","year":"1998"},{"key":"2025121112222085500_ref052","unstructured":"K. K.\n              Chen\n            \n          , \u201cInfluence query optimization with optimization profiles and statistical views in DB2 9: Optimal query performance in DB2 9 for Linux, UNIX, and Windows,\u201d Available at www.ibm.com\/developerworks\/db2\/library\/techarticle\/dm-0612chen, 2006."},{"key":"2025121112222085500_ref053","volume-title":"A Course in Approximation Theory","author":"Cheney","year":"2000"},{"key":"2025121112222085500_ref054","first-page":"197","article-title":"Structure-aware sampling on data streams","volume-title":"SIGMETRICS","author":"Cohen","year":"2011"},{"key":"2025121112222085500_ref055","first-page":"7","article-title":"Processing top-k queries from samples","volume-title":"Proceedings of CoNext","author":"Cohen","year":"2006"},{"key":"2025121112222085500_ref056","doi-asserted-by":"crossref","DOI":"10.1145\/1281100.1281133","article-title":"Summarizing data using bottom-k sketches","volume-title":"ACM Conference on Principles of Distributed Computing (PODC)","author":"Cohen","year":"2007"},{"key":"2025121112222085500_ref057","doi-asserted-by":"crossref","DOI":"10.1145\/872757.872787","article-title":"Spectral bloom filters","volume-title":"ACM SIGMOD International Conference on Management of Data","author":"Cohen","year":"2003"},{"key":"2025121112222085500_ref058","article-title":"MapReduce online","volume-title":"NSDI","author":"Condie","year":"2010"},{"issue":"1","key":"2025121112222085500_ref059","doi-asserted-by":"crossref","DOI":"10.1145\/1508857.1508863","article-title":"Robust approximate aggregation in sensor data management systems","volume":"34","author":"Considine","year":"2009","journal-title":"ACM Transactions on Database Systems"},{"key":"2025121112222085500_ref060","doi-asserted-by":"crossref","DOI":"10.1109\/ICDE.2004.1320018","article-title":"Approximate aggregation techniques for sensor databases","volume-title":"IEEE International Conference on Data Engineering","author":"Considine","year":"2004"},{"key":"2025121112222085500_ref061","doi-asserted-by":"crossref","DOI":"10.1016\/B978-155860869-6\/50037-8","article-title":"Comparing data streams using Hamming norms","volume-title":"International Conference on Very Large Data Bases","author":"Cormode","year":"2002"},{"issue":"1","key":"2025121112222085500_ref062","first-page":"526","article-title":"Probabilistic histograms for probabilistic data","volume":"2","author":"Cormode","year":"2009","journal-title":"PVLDB"},{"key":"2025121112222085500_ref063","article-title":"Sketching streams through the net: Distributed approximate query tracking","volume-title":"International Conference on Very Large Data Bases","author":"Cormode","year":"2005"},{"key":"2025121112222085500_ref064","volume-title":"Proceedings of the International Conference on Extending Database Technology","author":"Cormode","year":"2006"},{"key":"2025121112222085500_ref065","doi-asserted-by":"crossref","DOI":"10.14778\/1454159.1454225","article-title":"Finding frequent items in data streams","volume-title":"International Conference on Very Large Data Bases","author":"Cormode","year":"2008"},{"key":"2025121112222085500_ref066","doi-asserted-by":"crossref","DOI":"10.1109\/ICDE.2002.994778","article-title":"Fast mining of tabular data via approximate distance computations","volume-title":"IEEE International Conference on Data Engineering","author":"Cormode","year":"2002"},{"key":"2025121112222085500_ref067","first-page":"35","article-title":"Holistic UDAFs at streaming speeds","volume-title":"ACM SIGMOD International Conference on Management of Data","author":"Cormode","year":"2004"},{"key":"2025121112222085500_ref068","first-page":"263","article-title":"Space-and time-efficient deterministic algorithms for biased quantiles over data streams","volume-title":"Proceedings of ACM Principles of Database Systems","author":"Cormode","year":"2006"},{"key":"2025121112222085500_ref069","doi-asserted-by":"crossref","DOI":"10.1109\/INFCOM.2004.1354567","article-title":"What\u2019s new: Finding significant differences in network data streams","volume-title":"Proceedings of IEEE Infocom","author":"Cormode","year":"2004"},{"issue":"1","key":"2025121112222085500_ref070","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1016\/j.jalgor.2003.12.001","article-title":"An improved data stream summary: The count-min sketch and its applications","volume":"55","author":"Cormode","year":"2005","journal-title":"Journal of Algorithms"},{"key":"2025121112222085500_ref071","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611972757.5","article-title":"Summarizing and mining skewed data streams","volume-title":"SIAM Conference on Data Mining","author":"Cormode","year":"2005"},{"key":"2025121112222085500_ref072","article-title":"Summarizing and mining inverse distributions on data streams via dynamic inverse sampling","volume-title":"International Conference on Very Large Data Bases","author":"Cormode","year":"2005"},{"key":"2025121112222085500_ref073","first-page":"77","article-title":"Optimal sampling from distributed streams","volume-title":"Proceedings of ACM Principles of Database Systems","author":"Cormode","year":"2010"},{"key":"2025121112222085500_ref074","doi-asserted-by":"crossref","DOI":"10.1145\/872757.872838","article-title":"Gigascope: A stream database for network applications","volume-title":"ACM SIGMOD International Conference on Management of Data","author":"Cranor","year":"2003"},{"issue":"7","key":"2025121112222085500_ref075","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1145\/1538788.1538810","article-title":"Probabilistic databases: Diamonds in the dirt","volume":"52","author":"Dalvi","year":"2009","journal-title":"Communications of the ACM"},{"key":"2025121112222085500_ref076","doi-asserted-by":"crossref","DOI":"10.1145\/1007568.1007646","article-title":"Approximation techniques for spatial data","volume-title":"ACM SIGMOD International Conference on Management of Data","author":"Das","year":"2004"},{"key":"2025121112222085500_ref077","doi-asserted-by":"crossref","DOI":"10.1137\/S0097539701398363","article-title":"Maintaining stream statistics over sliding windows","volume-title":"ACM-SIAM Symposium on Discrete Algorithms","author":"Datar","year":"2002"},{"key":"2025121112222085500_ref078","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970104","volume-title":"Ten Lectures on Wavelets.","author":"Daubechies","year":"1992"},{"key":"2025121112222085500_ref079","volume-title":"Proceedings of the International Conference on Scientific and Statistical Database Management","author":"Deligiannakis","year":"2005"},{"issue":"2","key":"2025121112222085500_ref080","doi-asserted-by":"crossref","DOI":"10.1145\/1242524.1242527","article-title":"Extended wavelets for multiple measures","volume":"32","author":"Deligiannakis","year":"2007","journal-title":"ACM Transactions on Database Systems"},{"key":"2025121112222085500_ref081","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Deligiannakis","year":"2003"},{"key":"2025121112222085500_ref082","unstructured":"F.\n              Deng\n             and D.Rafiei, \u201cNew estimation algorithms for streaming data: Count-min can do more,\u201d http:\/\/www.cs.ualberta.ca\/~fandeng\/paper\/cmm.pdf, 2007."},{"key":"2025121112222085500_ref083","first-page":"199","article-title":"Independence is good: Dependency-based histogram synopses for high-dimensional data","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Deshpande","year":"2001"},{"key":"2025121112222085500_ref084","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1017\/S0962492900002816","article-title":"Nonlinear approximation","volume":"7","author":"DeVore","year":"1998","journal-title":"Acta Numerica"},{"key":"2025121112222085500_ref085","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0125-7","volume-title":"Combinatorial Methods in Density Estimation","author":"Devroye","year":"2001"},{"key":"2025121112222085500_ref086","first-page":"228","article-title":"Histograms revisited: When are histograms the best approximation method for aggregates over joins?","volume-title":"Proceedings of ACM Principles of Database Systems","author":"Dobra","year":"2005"},{"key":"2025121112222085500_ref087","doi-asserted-by":"crossref","DOI":"10.1145\/564691.564699","article-title":"Processing complex aggregate queries over data streams","volume-title":"ACM SIGMOD International Conference on Management of Data","author":"Dobra","year":"2002"},{"issue":"3","key":"2025121112222085500_ref088","article-title":"Statistical analysis of sketch estimators","volume":"33","author":"Dobra","year":"2008","journal-title":"ACM Transactions on Database Systems"},{"key":"2025121112222085500_ref089","first-page":"86","article-title":"Dynamic histograms: Capturing evolving data sets","volume-title":"Proceedings of the International Conference on Data Engineering","author":"Donjerkovic","year":"2000"},{"key":"2025121112222085500_ref090","first-page":"411","article-title":"Probabilistic optimization of top N queries","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Donjerkovic","year":"1999"},{"key":"2025121112222085500_ref091","doi-asserted-by":"crossref","DOI":"10.1145\/863955.863992","article-title":"Estimating flow distributions from sampled flow statistics","volume-title":"ACM SIGCOMM","author":"Duffield","year":"2003"},{"key":"2025121112222085500_ref092","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-39658-1_55","article-title":"Loglog counting of large cardinalities","volume-title":"European Symposium on Algorithms (ESA)","author":"Durand","year":"2003"},{"key":"2025121112222085500_ref093","doi-asserted-by":"crossref","DOI":"10.1145\/633025.633056","article-title":"New directions in traffic measurement and accounting","volume-title":"ACM SIGCOMM","author":"Estan","year":"2002"},{"key":"2025121112222085500_ref094","first-page":"387","article-title":"Development of sampling plans by using sequential (item by item) selection techniques and digital computers","volume-title":"Journal of the American Statistical Association","author":"Fan","year":"1962"},{"key":"2025121112222085500_ref095","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2553-7","volume-title":"Monte Carlo: Concepts, Algorithms and Applications.","author":"Fishman","year":"1996"},{"issue":"4","key":"2025121112222085500_ref096","doi-asserted-by":"crossref","DOI":"10.1007\/BF02241657","article-title":"On adaptive sampling","volume":"43","author":"Flajolet","year":"1990","journal-title":"Computing"},{"key":"2025121112222085500_ref097","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1016\/0022-0000(85)90041-8","article-title":"Probabilistic counting algorithms for database applications","volume":"31","author":"Flajolet","year":"1985","journal-title":"Journal of Computer and System Sciences"},{"key":"2025121112222085500_ref098","doi-asserted-by":"crossref","DOI":"10.1145\/1064092.1064116","article-title":"Sampling in dynamic data streams and applications","volume-title":"Symposium on Computational Geometry","author":"Frahling","year":"2005"},{"issue":"3","key":"2025121112222085500_ref099","doi-asserted-by":"crossref","first-page":"680","DOI":"10.1016\/j.ins.2006.07.013","article-title":"Compressed histograms with arbitrary bucket layouts for selectivity estimation","volume":"177","author":"Fuchs","year":"2007","journal-title":"Information on Science"},{"issue":"3","key":"2025121112222085500_ref100","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/j.tcs.2007.02.031","article-title":"Counting distinct items over update streams","volume":"378","author":"Ganguly","year":"2007","journal-title":"Theoretical Computer Science"},{"key":"2025121112222085500_ref101","doi-asserted-by":"crossref","DOI":"10.1145\/872757.872790","article-title":"Processing set expressions over continuous update streams","volume-title":"ACM SIGMOD International Conference on Management of Data","author":"Ganguly","year":"2003"},{"key":"2025121112222085500_ref102","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-24741-8_33","article-title":"Processing data-stream join aggregates using skimmed sketches","volume-title":"International Conference on Extending Database Technology","author":"Ganguly","year":"2004"},{"issue":"2","key":"2025121112222085500_ref103","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1145\/235968.233340","article-title":"Bifocal sampling for skew-resistant join size estimation","volume":"25","author":"Ganguly","year":"1996","journal-title":"SIGMOD Record"},{"key":"2025121112222085500_ref104","article-title":"CR-precis: A deterministic summary structure for update data streams","volume-title":"ESCAPE","author":"Ganguly","year":"2007"},{"key":"2025121112222085500_ref105","doi-asserted-by":"crossref","DOI":"10.1145\/564691.564794","article-title":"Querying and mining data streams: You only get one look","volume-title":"ACM SIGMOD International Conference on Management of Data","author":"Garofalakis","year":"2002"},{"key":"2025121112222085500_ref106","volume-title":"Data Stream Management: Processing High-Speed Data Streams","author":"Garofalakis","year":"2011"},{"key":"2025121112222085500_ref107","volume-title":"International Conference on Very Large Data Bases","author":"Garofalakis","year":"2001"},{"key":"2025121112222085500_ref108","first-page":"476","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Garofalakis","year":"2002"},{"key":"2025121112222085500_ref109","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/974750.974753","article-title":"Probabilistic wavelet synopses","volume":"29","author":"Garofalakis","year":"2004","journal-title":"ACM Transactions on Database Systems"},{"key":"2025121112222085500_ref110","volume-title":"Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems","author":"Garofalakis","year":"2004"},{"key":"2025121112222085500_ref111","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/1114244.1114246","article-title":"Wavelet synopses for general error metrics","volume":"30","author":"Garofalakis","year":"2005","journal-title":"ACM Transactions on Database Systems"},{"key":"2025121112222085500_ref112","unstructured":"R.\n              Gemulla\n            \n          , \u201cSampling algorithms for evolving datasets,\u201d PhD Thesis, Technische Universit\u00e4t Dresden, Available at http:\/\/nbn-resolving.de\/urn:nbn:de:bsz:14-ds-1224861856184-11644, 2009."},{"key":"2025121112222085500_ref113","first-page":"423","article-title":"Deferred maintenance of disk-based random samples","volume-title":"Proceedings of International Conference on Extending Database Technology","author":"Gemulla","year":"2006"},{"key":"2025121112222085500_ref114","first-page":"379","article-title":"Sampling time-based sliding windows in bounded space","volume-title":"SIGMOD Conference","author":"Gemulla","year":"2008"},{"key":"2025121112222085500_ref115","first-page":"595","article-title":"A dip in the reservoir: Maintaining sample synopses of evolving datasets","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Gemulla","year":"2006"},{"key":"2025121112222085500_ref116","first-page":"93","article-title":"Maintaining Bernoulli samples over evolving multisets","volume-title":"Proceedings of ACM Principles of Database Systems","author":"Gemulla","year":"2007"},{"issue":"2","key":"2025121112222085500_ref117","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/s00778-007-0065-y","article-title":"Maintaining bounded-size sample synopses of evolving datasets","volume":"17","author":"Gemulla","year":"2008","journal-title":"VLDB Journal"},{"key":"2025121112222085500_ref118","volume-title":"Random Number Generation and Monte Carlo Methods","author":"Gentle","year":"2003","edition":"second ed"},{"key":"2025121112222085500_ref119","first-page":"461","article-title":"Selectivity estimation using probabilistic models","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Getoor","year":"2001"},{"key":"2025121112222085500_ref120","first-page":"676","article-title":"An information theoretic histogram for single dimensional selectivity estimation","author":"Giannella","year":"2005","journal-title":"Proceedings of ACM Conference on Applications on Computing"},{"key":"2025121112222085500_ref121","article-title":"Distinct sampling for highly-accurate answers to distinct values queries and event reports","volume-title":"International Conference on Very Large Data Bases","author":"Gibbons","year":"2001"},{"key":"2025121112222085500_ref122","doi-asserted-by":"crossref","DOI":"10.1145\/378580.378687","article-title":"Estimating simple functions on the union of data streams","volume-title":"ACM Symposium on Parallel Algorithms and Architectures (SPAA)","author":"Gibbons","year":"2001"},{"key":"2025121112222085500_ref123","doi-asserted-by":"crossref","DOI":"10.1145\/564870.564880","article-title":"Distributed streams algorithms for sliding windows","volume-title":"ACM Symposium on Parallel Algorithms and Architectures (SPAA)","author":"Gibbons","year":"2002"},{"key":"2025121112222085500_ref124","first-page":"331","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Gibbons","year":"1998"},{"key":"2025121112222085500_ref125","author":"Gibbons","year":"1997"},{"issue":"3","key":"2025121112222085500_ref126","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1145\/581751.581753","article-title":"Fast incremental maintenance of approximate histograms","volume":"27","author":"Gibbons","year":"2002","journal-title":"ACM Transactions on Database Systems"},{"key":"2025121112222085500_ref127","doi-asserted-by":"crossref","DOI":"10.1145\/509907.509966","article-title":"Fast, small-space algorithms for approximate histogram maintenance","volume-title":"ACM Symposium on Theory of Computing","author":"Gilbert","year":"2002"},{"key":"2025121112222085500_ref128","article-title":"Surfing wavelets on streams: One-pass summaries for approximate aggregate queries","volume-title":"International Conference on Very Large Data Bases","author":"Gilbert","year":"2001"},{"key":"2025121112222085500_ref129","article-title":"How to summarize the universe: Dynamic maintenance of quantiles","volume-title":"International Conference on Very Large Data Bases","author":"Gilbert","year":"2002"},{"issue":"3","key":"2025121112222085500_ref130","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1109\/TKDE.2003.1198389","article-title":"One-pass wavelet decomposition of data streams","volume":"15","author":"Gilbert","year":"2003","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"2025121112222085500_ref131","doi-asserted-by":"crossref","DOI":"10.1145\/375663.375670","article-title":"Space-efficient online computation of quantile summaries","volume-title":"ACM SIGMOD International Conference on Management of Data","author":"Greenwald","year":"2001"},{"key":"2025121112222085500_ref132","unstructured":"S.\n              Guha\n            \n          , \u201cA note on wavelet optimization,\u201d (Manuscript available from: http:\/\/www.cis.upenn.edu\/~sudipto\/note.html.), September2004."},{"issue":"6","key":"2025121112222085500_ref133","doi-asserted-by":"crossref","first-page":"1509","DOI":"10.1007\/s00778-007-0083-9","article-title":"On the space-time of optimal, approximate and streaming algorithms for synopsis construction problems","volume":"17","author":"Guha","year":"2008","journal-title":"VLDB Journal"},{"key":"2025121112222085500_ref134","volume-title":"Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Guha","year":"2005"},{"key":"2025121112222085500_ref135","volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Guha","year":"2006"},{"key":"2025121112222085500_ref136","volume-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming","author":"Guha","year":"2002"},{"key":"2025121112222085500_ref137","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Guha","year":"2004"},{"issue":"1","key":"2025121112222085500_ref138","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1145\/1132863.1132873","article-title":"Approximation and streaming algorithms for histogram construction problems","volume":"31","author":"Guha","year":"2006","journal-title":"ACM Transactions on Database Systems"},{"key":"2025121112222085500_ref139","first-page":"180","article-title":"Fast algorithms for hierarchical range histogram construction","volume-title":"Proceedings of ACM Principles of Database Systems","author":"Guha","year":"2002"},{"issue":"7","key":"2025121112222085500_ref140","doi-asserted-by":"crossref","first-page":"993","DOI":"10.1109\/TKDE.2007.1039","article-title":"A note on linear time algorithms for maximum error histograms","volume":"19","author":"Guha","year":"2007","journal-title":"IEEE Transactions on Knowledge Data Engineering"},{"key":"2025121112222085500_ref141","first-page":"300","article-title":"REHIST: Relative error histogram construction algorithms","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Guha","year":"2004"},{"key":"2025121112222085500_ref142","first-page":"463","article-title":"Approximating multi-dimensional aggregate range queries over real attributes","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Gunopulos","year":"2000"},{"key":"2025121112222085500_ref143","first-page":"92","article-title":"Equidepth partitioning of a data set based on finding its medians","volume-title":"Proceedings of Applications of Computing","author":"Gurajada","year":"1991"},{"key":"2025121112222085500_ref144","first-page":"51","article-title":"Large-sample and deterministic confidence intervals for online aggregation","volume-title":"Proceedings of International Conference on Scientific and Statistical Database Management","author":"Haas","year":"1997"},{"issue":"2","key":"2025121112222085500_ref145","first-page":"32","article-title":"The need for speed: Speeding up DB2 UDB using sampling","volume":"10","author":"Haas","year":"2003","journal-title":"IDUG Solutions Journal"},{"key":"2025121112222085500_ref146","author":"Haas","year":"1998"},{"key":"2025121112222085500_ref147","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1145\/304181.304208","article-title":"Ripple joins for online aggregation","author":"Haas","year":"1999","journal-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data"},{"issue":"4","key":"2025121112222085500_ref148","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1002\/sam.10016","article-title":"Discovering and exploiting statistical properties for query optimization in relational databases","volume":"1","author":"Haas","year":"2009","journal-title":"Statistical Analysis and Data Mining"},{"key":"2025121112222085500_ref149","first-page":"275","article-title":"A bi-level bernoulli scheme for database sampling","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Haas","year":"2004"},{"key":"2025121112222085500_ref150","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1111\/j.1541-0420.2005.00390.x","article-title":"An estimator of the number of species from quadrat sampling","volume":"62","author":"Haas","year":"2006","journal-title":"Biometrics"},{"key":"2025121112222085500_ref151","first-page":"311","article-title":"Sampling-based estimation of the number of distinct values of an attribute","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Haas","year":"1995"},{"key":"2025121112222085500_ref152","first-page":"190","article-title":"Fixed-precision estimation of join selectivity","volume-title":"Proceedings of ACM Principles of Database Systems","author":"Haas","year":"1993"},{"issue":"3","key":"2025121112222085500_ref153","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1006\/jcss.1996.0041","article-title":"Selectivity and cost estimation for joins based on random sampling","volume":"52","author":"Haas","year":"1996","journal-title":"Journal of Computer and Systems Science"},{"key":"2025121112222085500_ref154","first-page":"14","article-title":"On the relative cost of sampling for join selectivity estimation","volume-title":"Proceedings of ACM Principles of Database Systems","author":"Haas","year":"1994"},{"issue":"444","key":"2025121112222085500_ref155","doi-asserted-by":"crossref","first-page":"1475","DOI":"10.1080\/01621459.1998.10473807","article-title":"Estimating the number of classes in a finite population","volume":"93","author":"Haas","year":"1998","journal-title":"Journal of American Statistical Association"},{"key":"2025121112222085500_ref156","first-page":"341","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Haas","year":"1992"},{"issue":"6","key":"2025121112222085500_ref157","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0020-0190(90)90214-I","article-title":"A guided tour of chernoff bounds","volume":"33","author":"Hagerup","year":"1990","journal-title":"Information on Processing Letters"},{"key":"2025121112222085500_ref158","volume-title":"Martingale Limit Theory and Its Application","author":"Hall","year":"1980"},{"key":"2025121112222085500_ref159","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1214\/ss\/1177013352","article-title":"Some history and reminiscences on survey sampling","volume":"2","author":"Hansen","year":"1987","journal-title":"Statistical Science"},{"key":"2025121112222085500_ref160","author":"Harb","year":"2007"},{"key":"2025121112222085500_ref161","doi-asserted-by":"crossref","DOI":"10.1109\/FOCS.2008.76","article-title":"Sketching and streaming entropy via approximation theory","volume-title":"Proceedings of the IEEE Conference on Foundations of Computer Science","author":"Harvey","year":"2008"},{"key":"2025121112222085500_ref162","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-21606-5","volume-title":"The Elements of Statistical Learning: Data Mining, Inferences, and Prediction","author":"Hastie","year":"2001"},{"issue":"3","key":"2025121112222085500_ref163","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1016\/j.jss.2007.03.088","article-title":"Proactive and reactive multi-dimensional histogram maintenance for selectivity estimation","volume":"81","author":"He","year":"2008","journal-title":"Journal of Systems and Software"},{"key":"2025121112222085500_ref164","first-page":"171","article-title":"Online aggregation","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Hellerstein","year":"1997"},{"issue":"1","key":"2025121112222085500_ref165","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1080\/15427951.2004.10129079","article-title":"Algorithmic challenges in search engines","volume":"1","author":"Henzinger","year":"2003","journal-title":"Internet Mathematics"},{"key":"2025121112222085500_ref166","author":"Henzinger","year":"1998"},{"key":"2025121112222085500_ref167","first-page":"522","article-title":"Adaptive spatial partitioning for multidimensional data streams","author":"Hershberger","year":"2004","journal-title":"Proceedings of ISAAC"},{"key":"2025121112222085500_ref168","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1145\/304181.304195","article-title":"Online association rule mining","author":"Hidber","year":"1999","journal-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data"},{"issue":"301","key":"2025121112222085500_ref169","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","article-title":"Probability inequalities for sums of bounded random variables","volume":"58","author":"Hoeffding","year":"1963","journal-title":"Journal of the American Statistical Association"},{"key":"2025121112222085500_ref170","doi-asserted-by":"crossref","first-page":"663","DOI":"10.1080\/01621459.1952.10483446","article-title":"A generalization of sampling without replacement from a finite universe","volume":"47","author":"Horvitz","year":"1952","journal-title":"Journal of the American Statistical Association"},{"key":"2025121112222085500_ref171","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1145\/308386.308455","article-title":"Statistical estimators for relational algebra expressions","volume-title":"Proceedings of ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems","author":"Hou","year":"1988"},{"key":"2025121112222085500_ref172","first-page":"68","article-title":"Processing aggregate relational queries with hard time constraints","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Hou","year":"1989"},{"key":"2025121112222085500_ref173","author":"IDC","year":"2008"},{"key":"2025121112222085500_ref174","doi-asserted-by":"crossref","DOI":"10.1109\/SFCS.2000.892082","article-title":"Stable distributions, pseudorandom generators, embeddings and data stream computation","volume-title":"IEEE Conference on Foundations of Computer Science","author":"Indyk","year":"2000"},{"key":"2025121112222085500_ref175","doi-asserted-by":"crossref","DOI":"10.1109\/SFCS.2003.1238202","article-title":"Tight lower bounds for the distinct elements problem","volume-title":"IEEE Conference on Foundations of Computer Science","author":"Indyk","year":"2003"},{"key":"2025121112222085500_ref176","doi-asserted-by":"crossref","DOI":"10.1145\/1060590.1060621","article-title":"Optimal approximations of the frequency moments of data streams","volume-title":"ACM Symposium on Theory of Computing","author":"Indyk","year":"2005"},{"key":"2025121112222085500_ref177","first-page":"256","article-title":"Universality of serial histograms","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Ioannidis","year":"1993"},{"key":"2025121112222085500_ref178","first-page":"16","article-title":"Approximations in database systems","volume-title":"Proceedings of the International Conference on Database Theory","author":"loannidis","year":"2003"},{"key":"2025121112222085500_ref179","first-page":"19","article-title":"The history of histograms (abridged)","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Ioannidis","year":"2003"},{"key":"2025121112222085500_ref180","first-page":"268","article-title":"On the propagation of errors in the size of join results","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Ioannidis","year":"1991"},{"issue":"4","key":"2025121112222085500_ref181","doi-asserted-by":"crossref","DOI":"10.1145\/169725.169708","article-title":"Optimal histograms for limiting worst-case error propagation in the size of join results","volume":"18","author":"Ioannidis","year":"1993","journal-title":"ACM Transactions on Database Systems"},{"key":"2025121112222085500_ref182","first-page":"233","article-title":"Balancing histogram optimality and practicality for query result size estimation","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Ioannidis","year":"1995"},{"key":"2025121112222085500_ref183","first-page":"174","article-title":"Histogram-based approximation of set-valued query-answers","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Ioannidis","year":"1999"},{"key":"2025121112222085500_ref184","first-page":"223","article-title":"Global optimization of histograms","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Jagadish","year":"2001"},{"key":"2025121112222085500_ref185","first-page":"275","article-title":"Optimal histograms with quality guarantees","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Jagadish","year":"1998"},{"issue":"3","key":"2025121112222085500_ref186","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1137\/1036095","article-title":"An overview of wavelet based multiresolution analyses","volume":"36","author":"Jawerth","year":"1994","journal-title":"SIAM Review"},{"key":"2025121112222085500_ref187","unstructured":"T. S.\n              Jayram\n            , R.Kumar, and D.Sivakumar, \u201cThe one-way communication complexity of gap hamming distance,\u201d http:\/\/www.madalgo.au.dk\/img\/SumSchoo2007_Lecture_20slides\/Bibliography\/p14_Jayram_07_Manusc_ghd.pdf, 2007."},{"key":"2025121112222085500_ref188","doi-asserted-by":"crossref","DOI":"10.1145\/1247480.1247560","article-title":"Scalable approximate query processing with the DBO engine","volume-title":"ACM SIGMOD International Conference on Management of Data","author":"Jermaine","year":"2007"},{"issue":"4","key":"2025121112222085500_ref189","doi-asserted-by":"crossref","first-page":"1382","DOI":"10.1145\/1189769.1189775","article-title":"The sortmerge-shrink join","volume":"31","author":"Jermaine","year":"2006","journal-title":"ACM Transactions on Database Systems"},{"key":"2025121112222085500_ref190","first-page":"745","article-title":"Online estimation for subsetbased sql queries","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Jermaine","year":"2005"},{"key":"2025121112222085500_ref191","first-page":"299","article-title":"Online maintenance of very large random samples","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Jermaine","year":"2004"},{"key":"2025121112222085500_ref192","doi-asserted-by":"crossref","DOI":"10.1145\/956863.956918","article-title":"Dynamically maintaining frequent items over a data stream","volume-title":"Proceedings of the ACM Conference on Information and Knowledge Management","author":"Jin","year":"2003"},{"key":"2025121112222085500_ref193","volume-title":"Proceedings of the International Conference on Data Engineering","author":"Jin","year":"2006"},{"key":"2025121112222085500_ref194","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1090\/conm\/026\/737400","article-title":"Extensions of Lipshitz mapping into Hilbert space","volume":"26","author":"Johnson","year":"1984","journal-title":"Contemporary Mathematics"},{"key":"2025121112222085500_ref195","article-title":"Sampling-based estimators for subset-based queries","volume-title":"VLDB Journal","author":"Joshi","year":"2008"},{"key":"2025121112222085500_ref196","doi-asserted-by":"crossref","DOI":"10.1145\/1989284.1989289","article-title":"Tight bounds for lp samplers, finding duplicates in streams, and related problems","volume-title":"ACM Principles of Database Systems","author":"Jowhari","year":"2011"},{"key":"2025121112222085500_ref197","first-page":"663","article-title":"Histograms reloaded: The merits of bucket diversity","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Kanne","year":"2010"},{"issue":"1","key":"2025121112222085500_ref198","first-page":"670","article-title":"Optimality and scalability in lattice histogram construction","volume":"2","author":"Karras","year":"2009","journal-title":"PVLDB"},{"key":"2025121112222085500_ref199","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/1386118.1386124","article-title":"Hierarchical synopses with optimal error guarantees","volume":"33","author":"Karras","year":"2008","journal-title":"ACM Transactions on Database Systems"},{"key":"2025121112222085500_ref200","first-page":"247","volume-title":"Proceedings of the International Conference on Data Engineering","author":"Karras","year":"2008"},{"key":"2025121112222085500_ref201","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Karras","year":"2005"},{"key":"2025121112222085500_ref202","volume-title":"Proceedings of the International Conference on Data Engineering","author":"Karras","year":"2007"},{"key":"2025121112222085500_ref203","volume-title":"Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Karras","year":"2007"},{"issue":"4","key":"2025121112222085500_ref204","doi-asserted-by":"crossref","first-page":"1102","DOI":"10.1145\/1114244.1114251","article-title":"Synopses for query optimization: A space-complexity perspective","volume":"30","author":"Kaushik","year":"2005","journal-title":"ACM Transactions on Database Systems"},{"issue":"1","key":"2025121112222085500_ref205","first-page":"850","article-title":"Consistent histograms in the presence of distinct value counts","volume":"2","author":"Kaushik","year":"2009","journal-title":"PVLDB"},{"key":"2025121112222085500_ref206","first-page":"482","article-title":"Gossip-based computation of aggregate information","volume-title":"Proceedings of the IEEE Conference on Foundations of Computer Science","author":"Kempe","year":"2003"},{"key":"2025121112222085500_ref207","doi-asserted-by":"crossref","first-page":"616","DOI":"10.1007\/3-540-63165-8_216","article-title":"Efficient array partitioning","volume-title":"Proceedings of the International Colloquium on Automata, Languages and Programming","author":"Khanna","year":"1997"},{"key":"2025121112222085500_ref208","first-page":"423","article-title":"Combining histograms and parametric curve fitting for feedback-driven query result-size estimation","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"K\u00f6nig","year":"1999"},{"key":"2025121112222085500_ref209","first-page":"244","article-title":"Range selectivity estimation for continuous attributes","volume-title":"Proceedings of the International Conference on Scientific and Statistical Database Management","author":"Korn","year":"1999"},{"key":"2025121112222085500_ref210","volume-title":"Communication Complexity","author":"Kushilevitz","year":"1997"},{"key":"2025121112222085500_ref211","doi-asserted-by":"crossref","DOI":"10.1145\/1185347.1185364","article-title":"High-throughput sketch update on a low-power stream processor","volume-title":"Proceedings of the ACM\/IEEE Symposium on Architecture for Networking and Communications Systems","author":"Lai","year":"2006"},{"key":"2025121112222085500_ref212","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-5449-2","volume-title":"Extremes and Related Properties of Random Sequences and Processes: Springer Series in Statistics","author":"Leadbetter","year":"1983"},{"key":"2025121112222085500_ref213","doi-asserted-by":"crossref","DOI":"10.1145\/1330107.1330138","article-title":"Improving sketch reconstruction accuracy using linear least squares method","volume-title":"Internet Measurement Conference (IMC)","author":"Lee","year":"2005"},{"key":"2025121112222085500_ref214","first-page":"369","article-title":"SASH: A self-adaptive histogram set for dynamically changing workloads","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Lim","year":"2003"},{"key":"2025121112222085500_ref215","first-page":"1187","article-title":"CXHist: An on-line classification-based histogram for XML string selectivity estimation","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Lim","year":"2005"},{"key":"2025121112222085500_ref216","first-page":"165","article-title":"Error minimization for approximate computation of range aggregate","volume-title":"Proceedings of the International Conference on Database Systems for Advanced Applications","author":"Lin","year":"2003"},{"key":"2025121112222085500_ref217","doi-asserted-by":"crossref","DOI":"10.1145\/1375457.1375472","article-title":"Counter braids: A novel counter architecture for per-flow measurement","volume-title":"SIGMETRICS","author":"Lu","year":"2008"},{"key":"2025121112222085500_ref218","first-page":"252","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Luo","year":"2002"},{"key":"2025121112222085500_ref219","first-page":"93","article-title":"Selectivity estimation by batch-query based histogram and parametric method","volume-title":"Proceedings of Australasian Database Conference on ADC2007","author":"Luo","year":"2007"},{"key":"2025121112222085500_ref220","unstructured":"MADlib library for scalable analytics\n          , http:\/\/madlib.net."},{"key":"2025121112222085500_ref221","volume-title":"A Wavelet Tour of Signal Processing","author":"Mallat","year":"1999","edition":"Second ed"},{"key":"2025121112222085500_ref222","volume-title":"Proceedings of the International Conference on Database Theory","author":"Matias","year":"2005"},{"issue":"3","key":"2025121112222085500_ref223","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/j.tcs.2006.11.018","article-title":"Optimal workload-based weighted wavelet synopses","volume":"371","author":"Matias","year":"2007","journal-title":"Theoretical Computer Science"},{"key":"2025121112222085500_ref224","first-page":"448","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Matias","year":"1998"},{"key":"2025121112222085500_ref225","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Matias","year":"2000"},{"key":"2025121112222085500_ref226","doi-asserted-by":"crossref","DOI":"10.1145\/1353343.1353418","article-title":"Why go logarithmic if we can go linear? Towards effective distinct counting of search traffic","volume-title":"International Conference on Extending Database Technology","author":"Metwally","year":"2008"},{"key":"2025121112222085500_ref227","unstructured":"Microsoft. Microsoft StreamInsight\n          . http:\/\/msdn.microsoft.com\/en-us\/library\/ee362541.aspx, 2008."},{"key":"2025121112222085500_ref228","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0167-6423(82)90012-0","article-title":"Finding repeated elements","volume":"2","author":"Misra","year":"1982","journal-title":"Science of Computer Programming"},{"key":"2025121112222085500_ref229","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis. CUP","author":"Mitzenmacher","year":"2005"},{"issue":"1","key":"2025121112222085500_ref230","first-page":"982","article-title":"Preventing bad plans by bounding the impact of cardinality estimation errors","volume":"2","author":"Moerkotte","year":"2009","journal-title":"PVLDB"},{"key":"2025121112222085500_ref231","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611973075.92","article-title":"1-pass relative-error lp-sampling with applications","volume-title":"ACM-SIAM Symposium on Discrete Algorithms","author":"Monemizadeh","year":"2010"},{"key":"2025121112222085500_ref232","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"Motwani","year":"1995"},{"key":"2025121112222085500_ref233","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/0304-3975(80)90061-4","article-title":"Selection and sorting with limited storage","volume":"12","author":"Munro","year":"1980","journal-title":"Theoretical Computer Science"},{"key":"2025121112222085500_ref234","first-page":"28","article-title":"Equi-depth histograms for estimating selectivity factors for multi-dimensional queries","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Muralikrishna","year":"1988"},{"key":"2025121112222085500_ref235","volume-title":"Proceedings of the International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)","author":"Muthukrishnan","year":"2005"},{"issue":"2","key":"2025121112222085500_ref236","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1561\/0400000002","article-title":"Data streams: Algorithms and applications","volume":"1","author":"Muthukrishnan","year":"2005","journal-title":"Foundations and Trends\u00ae in Theoretical Computer Science"},{"key":"2025121112222085500_ref237","first-page":"236","article-title":"On rectangular partitionings in two dimensions: Algorithms, complexity, and applications","volume-title":"Proceedings of the International Conference on Database Theory","author":"Muthukrishnan","year":"1999"},{"key":"2025121112222085500_ref238","first-page":"352","article-title":"Maintenance of multidimensional histograms","author":"Muthukrishnan","year":"2003"},{"key":"2025121112222085500_ref239","first-page":"734","article-title":"Workload-optimal histograms on streams","volume-title":"Proceedings of ESA","author":"Muthukrishnan","year":"2005"},{"key":"2025121112222085500_ref240","doi-asserted-by":"crossref","first-page":"558","DOI":"10.2307\/2342192","article-title":"On the two different aspects of the representative method: The method of stratified sampling and the method of purposive selection","volume":"97","author":"Neyman","year":"1934","journal-title":"Journal of the Royal Statistical Society"},{"key":"2025121112222085500_ref241","volume-title":"Bayesian Inference","author":"O\u2019Hagan","year":"2004","edition":"second ed"},{"key":"2025121112222085500_ref242","author":"Olken","year":"1993"},{"key":"2025121112222085500_ref243","first-page":"160","article-title":"Simple random sampling from relational databases","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Olken","year":"1986"},{"key":"2025121112222085500_ref244","first-page":"269","article-title":"Random sampling from B+ trees","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Olken","year":"1989"},{"key":"2025121112222085500_ref245","first-page":"632","article-title":"Maintenance of materialized views of sampling queries","volume-title":"Proceedings of the International Conference on Data Engineering","author":"Olken","year":"1992"},{"issue":"2","key":"2025121112222085500_ref246","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1145\/93605.98746","article-title":"Random sampling from hash files","volume":"19","author":"Olken","year":"1990","journal-title":"SIGMOD Record"},{"key":"2025121112222085500_ref247","volume-title":"Proceedings of the International Conference on Extending Database Technology","author":"Pang","year":"2009"},{"key":"2025121112222085500_ref248","article-title":"Online aggregation for large MapReduce jobs","volume":"5","author":"Pansare","year":"2011","journal-title":"PVLDB"},{"issue":"2","key":"2025121112222085500_ref249","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1137\/050643672","article-title":"Range-efficient counting of distinct elements in a massive data stream","volume":"37","author":"Pavan","year":"2007","journal-title":"SIAM Journal on Computing"},{"key":"2025121112222085500_ref250","first-page":"13","article-title":"Structure choices for two-dimensional histogram construction","volume-title":"Proceedings of CASCON","author":"Pham","year":"2004"},{"key":"2025121112222085500_ref251","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1145\/971697.602294","article-title":"Accurate estimation of the number of tuples satisfying a condition","author":"Piatetsky-Shapiro","year":"1984","journal-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data"},{"key":"2025121112222085500_ref252","first-page":"63","article-title":"XCluster synopses for structured XML content","volume-title":"Proceedings of the International Conference on Data Engineering","author":"Polyzotis","year":"2006"},{"key":"2025121112222085500_ref253","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/1166074.1166082","article-title":"XSKETCH synopses for XML data graphs","volume":"31","author":"Polyzotis","year":"2006","journal-title":"ACM Transactions on Database Systems"},{"key":"2025121112222085500_ref254","first-page":"24","article-title":"Fast approximate answers to aggregate queries on a data cube","volume-title":"Proceedings of the International Conference on Scientific and Statistical Database Management","author":"Poosala","year":"1999"},{"issue":"4","key":"2025121112222085500_ref255","first-page":"5","article-title":"Approximate query answering using histograms","volume":"22","author":"Poosala","year":"1999","journal-title":"IEEE Data Engineering Bulletins"},{"key":"2025121112222085500_ref256","first-page":"486","article-title":"Selectivity estimation without the attribute value independence assumption","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Poosala","year":"1997"},{"key":"2025121112222085500_ref257","first-page":"294","article-title":"Improved histograms for selectivity estimation of range predicates","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Poosala","year":"1996"},{"key":"2025121112222085500_ref258","first-page":"469","article-title":"RHist: Adaptive summarization over continuous data streams","volume-title":"Proceedings of the ACM Conference on Information and Knowledge Management","author":"Qiao","year":"2002"},{"key":"2025121112222085500_ref259","first-page":"381","article-title":"Potter\u2019s Wheel: An interactive data cleaning system","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Raman","year":"2001"},{"issue":"3","key":"2025121112222085500_ref260","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/s007780000032","article-title":"Online dynamic reordering","volume":"9","author":"Raman","year":"2000","journal-title":"VLDB Journal"},{"key":"2025121112222085500_ref261","first-page":"60","article-title":"Constant-time query processing","volume-title":"Proceedings of the International Conference on Data Engineering","author":"Raman","year":"2008"},{"key":"2025121112222085500_ref262","first-page":"107","article-title":"Computing bounds on aggregate operations over uncertain sets using histograms","volume-title":"Proceedings of Post-ILPS 9&gt;4 Workshop on Uncertainty in Databases and Deductive Systems,","author":"Read","year":"1994"},{"key":"2025121112222085500_ref263","first-page":"870","article-title":"Compact histograms for hierarchical identifiers","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Reiss","year":"2006"},{"issue":"3","key":"2025121112222085500_ref264","doi-asserted-by":"crossref","first-page":"1080","DOI":"10.1214\/aos\/1176350051","article-title":"Stochastic complexity and modeling","volume":"14","author":"Rissanen","year":"1986","journal-title":"Annals of Statistics"},{"key":"2025121112222085500_ref265","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/1386118.1386121","article-title":"Sketches for size of join estimation","volume":"33","author":"Rusu","year":"2008","journal-title":"ACM Transactions on Database Systems"},{"issue":"1","key":"2025121112222085500_ref266","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/s00778-008-0096-z","article-title":"Hierarchically-compressed wavelet synopses","volume":"18","author":"Sacharidis","year":"2009","journal-title":"The VLDB Journal"},{"issue":"5","key":"2025121112222085500_ref267","doi-asserted-by":"crossref","first-page":"989","DOI":"10.1007\/s00778-009-0147-0","article-title":"Representing uncertain data: Models, properties, and algorithms","volume":"18","author":"Sarma","year":"2009","journal-title":"VLDB Journal"},{"key":"2025121112222085500_ref268","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-4378-6","volume-title":"Model-Assisted Survey Sampling","author":"Sarndal","year":"1992","edition":"second ed"},{"key":"2025121112222085500_ref269","first-page":"5","article-title":"Reversible sketches: Enabling monitoring and analysis over high-speed data streams","volume":"15","author":"Schweller","year":"2007","journal-title":"IEEE Transactions on Networks"},{"key":"2025121112222085500_ref270","doi-asserted-by":"crossref","DOI":"10.1002\/9780470316849","volume-title":"Multivariate Density Estimation: Theory Practice, and Visualization","author":"Scott","year":"1992"},{"key":"2025121112222085500_ref271","author":"Seshadri","year":"1992"},{"key":"2025121112222085500_ref272","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0795-5","volume-title":"The Jackknife and Bootstrap","author":"Shao","year":"1995"},{"key":"2025121112222085500_ref273","volume-title":"Density Estimation for Statistics and Data Analysis","author":"Silverman","year":"1986"},{"key":"2025121112222085500_ref274","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1508857.1508860","article-title":"TuG synopses for approximate query answering","volume":"34","author":"Spiegel","year":"2009","journal-title":"ACM Transactions on Database Systems"},{"key":"2025121112222085500_ref275","doi-asserted-by":"crossref","DOI":"10.1109\/ICDE.2006.84","article-title":"ISOMER: Consistent histogram construction using query feedback","volume-title":"Proceedings of the International Conference on Data Engineering","author":"Srivastava","year":"2006"},{"key":"2025121112222085500_ref276","volume-title":"Wavelets for Computer Graphics \u2014 Theory and Applications","author":"Stollnitz","year":"1996"},{"key":"2025121112222085500_ref277","article-title":"Requirements for science data bases and scidb","volume-title":"Proceedings of CIDR","author":"Stonebraker","year":"2009"},{"key":"2025121112222085500_ref278","doi-asserted-by":"crossref","DOI":"10.1145\/564691.564741","article-title":"Dynamic multidimensional histograms","volume-title":"ACM SIGMOD International Conference on Management of Data","author":"Thaper","year":"2002"},{"key":"2025121112222085500_ref279","doi-asserted-by":"crossref","DOI":"10.1109\/ICDE.2009.35","article-title":"On efficient query processing of stream counts on the cell processor","volume-title":"IEEE International Conference on Data Engineering","author":"Thomas","year":"2009"},{"key":"2025121112222085500_ref280","article-title":"Even strongly universal hashing is pretty fast","volume-title":"ACM-SIAM Symposium on Discrete Algorithms","author":"Thorup","year":"2000"},{"key":"2025121112222085500_ref281","article-title":"Tabulation based 4-universal hashing with applications to second moment estimation","volume-title":"ACM-SIAM Symposium on Discrete Algorithms","author":"Thorup","year":"2004"},{"key":"2025121112222085500_ref282","article-title":"New streaming algorithms for fast detection of superspreaders","volume-title":"Network and Distributed System Security Symposium NDSS","author":"Venkataraman","year":"2005"},{"issue":"1","key":"2025121112222085500_ref283","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1145\/3147.3165","article-title":"Random sampling with a reservoir","volume":"11","author":"Vitter","year":"1985","journal-title":"ACM Transactions on Mathematical Software"},{"key":"2025121112222085500_ref284","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Vitter","year":"1999"},{"key":"2025121112222085500_ref285","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4899-4493-1","volume-title":"Kernel Smoothing","author":"Wand","year":"1995"},{"key":"2025121112222085500_ref286","first-page":"16","article-title":"Utilizing histogram information","volume-title":"Proceedings of CASCON","author":"Wang","year":"2001"},{"key":"2025121112222085500_ref287","first-page":"328","article-title":"A multi-dimensional histogram for selectivity estimation and fast approximate query answering","volume-title":"Proceedings of CASCON","author":"Wang","year":"2003"},{"issue":"3","key":"2025121112222085500_ref288","doi-asserted-by":"crossref","DOI":"10.1007\/s00778-006-0015-0","article-title":"Histograms based on the minimum description length principle","volume":"17","author":"Wang","year":"2008","journal-title":"VLDB Journal"},{"issue":"2","key":"2025121112222085500_ref289","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1145\/78922.78925","article-title":"A linear-time probabilistic counting algorithm for database applications","volume":"15","author":"Whang","year":"1990","journal-title":"ACM Transactions on Database Systems"},{"key":"2025121112222085500_ref290","first-page":"709","article-title":"How simulation languages should report results: A modest proposal","volume-title":"Proceedings of Winter Simulation Conference","author":"Wieland","year":"2009"},{"key":"2025121112222085500_ref291","article-title":"The big time: 1998 winter VLDB survey","volume-title":"Database Programming and Design","author":"Winter","year":"1998"},{"key":"2025121112222085500_ref292","article-title":"Optimal space lower bounds for all frequency moments","volume-title":"ACM-SIAM Symposium on Discrete Algorithms","author":"Woodruff","year":"2004"},{"key":"2025121112222085500_ref293","first-page":"471","article-title":"A bayesian method for guessing the extreme values in a data set","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Wu","year":"2007"},{"key":"2025121112222085500_ref294","doi-asserted-by":"crossref","DOI":"10.1109\/ICDE.2008.4497450","article-title":"Randomized synopses for query assurance on data streams","volume-title":"IEEE International Conference on Data Engineering","author":"Yi","year":"2008"},{"key":"2025121112222085500_ref295","first-page":"354","article-title":"On linear-spline based histograms","volume-title":"Proceedings of the International Conference on Web-Age Information Management","author":"Zhang","year":"2002"},{"key":"2025121112222085500_ref296","first-page":"29","article-title":"A fast algorithm for approximate quantiles in high speed data streams","volume-title":"Proceedings of the International Conference on Scientific and Statistical Database Management","author":"Zhang","year":"2007"},{"key":"2025121112222085500_ref297","article-title":"Bandwidth selection for multivariate kernel density estimation using MCMC","volume-title":"Econometric Society 2004 Australasian Meetings","author":"Zhang","year":"2004"},{"key":"2025121112222085500_ref298","first-page":"220","article-title":"Building regression cost models for multidatabase systems","volume-title":"Proceedings of the International Conference on Parallel and Distributed Information Systems","author":"Zhu","year":"1996"},{"key":"2025121112222085500_ref299","volume-title":"One Dimensional Stable Distributions","author":"Zolotarev","year":"1983"}],"container-title":["Foundations and Trends in Databases"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.emerald.com\/ftdbs\/article-pdf\/4\/1-3\/1\/11024120\/1900000004en.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/www.emerald.com\/ftdbs\/article-pdf\/4\/1-3\/1\/11024120\/1900000004en.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T14:11:39Z","timestamp":1777471899000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.emerald.com\/ftdbs\/article\/4\/1-3\/1\/1326465\/Synopses-for-Massive-Data-Samples-Histograms"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12,31]]},"references-count":299,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[2011,12,31]]}},"URL":"https:\/\/doi.org\/10.1561\/1900000004","relation":{},"ISSN":["1931-7883","1931-7891"],"issn-type":[{"value":"1931-7883","type":"print"},{"value":"1931-7891","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,12,31]]}}}