The DOI matches its Crossref record; 126 of the 126 references it cites were found in a registry or an index.
Synopses for Massive Data: Samples, Histograms, Wavelets, Sketches
Abstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The Elements of Statistical Learning
Hastie, T., Tibshirani, R., & Friedman, J. (2009) · Springer Series in Statistics · doi:10.1007/978-0-387-84858-7 · Cited by 25,970
The Elements of Statistical Learning
Hastie, T., Friedman, J., & Tibshirani, R. (2001) · Springer Series in Statistics · doi:10.1007/978-0-387-21606-5 · Cited by 24,162
A Wavelet Tour of Signal Processing
(1999) · Elsevier eBooks · doi:10.1016/b978-0-12-466606-1.x5000-4 · Cited by 16,227
Daubechies, I. (1992) · doi:10.1137/1.9781611970104 · Cited by 15,979
Density Estimation for Statistics and Data Analysis
Silverman, B. W. (2018) · Routledge eBooks · doi:10.1201/9781315140919 · Cited by 15,796
Daubechies, I., & Heil, C. (1992) · Computers in Physics · doi:10.1063/1.4823127 · Cited by 15,631
Space/time trade-offs in hash coding with allowable errors
Bloom, B. H. (1970) · Communications of the ACM · doi:10.1145/362686.362692 · Cited by 7,492
Probability Inequalities for sums of Bounded Random Variables
Hoeffding, W. (1994) · Springer Series in Statistics · doi:10.1007/978-1-4612-0865-5_26 · Cited by 6,666
PE, & Billingsley, P. (1996) · Journal of the American Statistical Association · doi:10.2307/2291440 · Cited by 6,481
Motwani, R., & Raghavan, P. (1995) · Cambridge University Press eBooks · doi:10.1017/cbo9780511814075 · Cited by 5,123
Probability Inequalities for Sums of Bounded Random Variables
Hoeffding, W. (1963) · Journal of the American Statistical Association · doi:10.1080/01621459.1963.10500830 · Cited by 4,852
A generalization of sampling without replacement from a finite universe
Horvitz, D. G., & Thompson, D. J. (1952) · Journal of the American Statistical Association · doi:10.1080/01621459.1952.10483446 · Cited by 4,293
Multivariate Density Estimation: Theory, Practice, and Visualization
Scott, D. W. (1992) · Wiley Series in Probability and Statistics · doi:10.1002/9780470316849 · Cited by 3,696
Model Assisted Survey Sampling
Särndal, C.-E., Swensson, B., & Wretman, J. (1992) · Springer Series in Statistics · doi:10.1007/978-1-4612-4378-6 · Cited by 3,386
Extremes and Related Properties of Random Sequences and Processes
Leadbetter, M. R., Lindgren, G., & Rootzén, H. (1983) · Springer Series in Statistics · doi:10.1007/978-1-4612-5449-2 · Cited by 2,873
Multivariate Density Estimation, Theory, Practice, and Visualbation
Ramsay, P. H. (1993) · Technometrics · doi:10.1080/00401706.1993.10485361 · Cited by 2,789
Martingale Limit Theory and its Application.
Loynes, R. M., Hall, P., & Heyde, C. C. (1984) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2981599 · Cited by 2,685
Wand, M. P., & Jones, M. C. (1995) · Springer eBooks · doi:10.1007/978-1-4899-4493-1 · Cited by 2,663
Extensions of Lipschitz mappings into a Hilbert space
Johnson, W. B., & Lindenstrauss, J. (1984) · Contemporary Mathematics · doi:10.1090/conm/026/737400 · Cited by 2,523
Universal classes of hash functions
Carter, J. L., & Wegman, M. N. (1979) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(79)90044-8 · Cited by 2,519
Models and issues in data stream systems
Babcock, B., Babu, S., Datar, M., Motwani, R., & Widom, J. (2002) · Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/543613.543615 · Cited by 2,495
Network Applications of Bloom Filters: A Survey
Broder, A., & Mitzenmacher, M. (2004) · Internet Mathematics · doi:10.1080/15427951.2004.10129096 · Cited by 1,991
Shao, J., & Tu, D. (1995) · Springer Series in Statistics · doi:10.1007/978-1-4612-0795-5 · Cited by 1,985
One-Dimensional Stable Distributions
Zolotarev, V. (1986) · Translations of Mathematical Monographs · doi:10.1090/mmono/065 · Cited by 1,843
Probability and computing: randomized algorithms and probabilistic analysis
Mitzenmacher, M., & Upfal, E. (2005) · CERN Document Server (European Organization for Nuclear Research) · Cited by 1,824
Monte Carlo: Concepts, Algorithms, and Applications
Wasserstein, R. L. (1997) · Technometrics · doi:10.1080/00401706.1997.10485133 · Cited by 1,790
Random sampling with a reservoir
Vitter, J. S. (1985) · ACM Transactions on Mathematical Software · doi:10.1145/3147.3165 · Cited by 1,758
An improved data stream summary: the count-min sketch and its applications
Cormode, G., & Muthukrishnan, S. (2005) · Journal of Algorithms · doi:10.1016/j.jalgor.2003.12.001 · Cited by 1,743
Self-citationProbability and Computing: Randomized Algorithms and Probabilistic Analysis
Mitzenmacher, M., & Upfal, E. (2005) · Cambridge University Press eBooks · doi:10.1017/cbo9780511813603 · Cited by 1,733
Extremes and Related Properties of Random Sequences and Processes.
Davis, R. A., Leadbetter, M. R., Lindgren, G., & Rootzen, H. (1985) · Journal of the American Statistical Association · doi:10.2307/2288102 · Cited by 1,725
(2005) · Complexity Theory · doi:10.1007/3-540-27477-4_15 · Cited by 1,629
Gossip-based computation of aggregate information
Kempe, D., Dobra, A., & Gehrke, J. (2004) · 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. · doi:10.1109/sfcs.2003.1238221 · Cited by 1,480
Data Streams: Algorithms and Applications
Muthukrishnan, S. (2005) · now publishers, Inc. eBooks · doi:10.1561/9781933019604 · Cited by 1,433
Finding frequent items in data streams
Charikar, M., Chen, K., & Farach-Colton, M. (2004) · Theoretical Computer Science · doi:10.1016/s0304-3975(03)00400-6 · Cited by 1,278
Probabilistic counting algorithms for data base applications
Flajolet, P., & Nigel Martin, G. (1985) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(85)90041-8 · Cited by 1,269
Neyman, J. (1934) · Journal of the Royal Statistical Society · doi:10.2307/2342192 · Cited by 1,086
Neyman, J. (1992) · Springer Series in Statistics · doi:10.1007/978-1-4612-4380-9_12 · Cited by 932
Fishman, G. S. (1996) · Springer eBooks · doi:10.1007/978-1-4757-2553-7 · Cited by 925
Stochastic Complexity and Modeling
Rissanen, J. (1986) · The Annals of Statistics · doi:10.1214/aos/1176350051 · Cited by 922
Hellerstein, J. M., Haas, P. J., & Wang, H. J. (1997) · Proceedings - ACM-SIGMOD International Conference on Management of Data · doi:10.1145/253260.253291 · Cited by 902
Self-citationDeVore, R. A. (1998) · Acta Numerica · doi:10.1017/s0962492900002816 · Cited by 877
HadoopDB: an architectural hybrid of MapReduce and DBMS technologies for analytical workloads
Abouzeid, A., Bajda-Pawlikowski, K., Abadi, D., Silberschatz, A., & Rasin, A. (2009) · Proceedings of the VLDB Endowment · doi:10.14778/1687627.1687731 · Cited by 857
Maintaining Stream Statistics over Sliding Windows
Datar, M., Gionis, A., Indyk, P., & Motwani, R. (2002) · SIAM Journal on Computing · doi:10.1137/s0097539701398363 · Cited by 835
The space complexity of approximating the frequency moments
Alon, N., Matias, Y., & Szegedy, M. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237823 · Cited by 822
Min-Wise Independent Permutations
Broder, A. Z., Charikar, M., Frieze, A. M., & Mitzenmacher, M. (2000) · Journal of Computer and System Sciences · doi:10.1006/jcss.1999.1690 · Cited by 802
Random Number Generation and Monte Carlo Methods
B. Borkowf, C. (2000) · Technometrics · doi:10.1080/00401706.2000.10485723 · Cited by 799
New directions in traffic measurement and accounting
Estan, C., & Varghese, G. (2001) · doi:10.1145/505202.505212 · Cited by 734
Data Streams: Algorithms and Applications
Muthukrishnan, S. (2005) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000002 · Cited by 718
Wavelets for computer graphics: theory and applications
Stollnitz, E. J., DeRose, T., & Salesin, D. (1996) · Morgan Kaufmann Publishers Inc. eBooks · Cited by 696
Combinatorial Methods in Density Estimation
Devroye, L., & Lugosi, G. (2001) · Springer series in statistics · doi:10.1007/978-1-4613-0125-7 · Cited by 694
Gigascope: a stream database for network applications
Cranor, C., Johnson, T., Spataschek, O., & Shkapenyuk, V. (2003) · Proceedings of the 2003 ACM SIGMOD international conference on Management of data · doi:10.1145/872757.872838 · Cited by 687
Condie, T., Conway, N., Alvaro, P., Hellerstein, J. M., Elmeleegy, K., & Sears, R. (2010) · doi:10.5555/1855711.1855732 · Cited by 673
Finding Frequent Items in Data Streams
Charikar, M., Chen, K., & Farach-Colton, M. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45465-9_59 · Cited by 650
Approximate aggregation techniques for sensor databases
Considine, J., Li, F., Kollios, G., et al. (2004) · Proceedings - International Conference on Data Engineering · doi:10.1109/icde.2004.1320018 · Cited by 562
Improved histograms for selectivity estimation of range predicates
Poosala, V., Haas, P. J., Ioannidis, Y. E., & Shekita, E. J. (1996) · Proceedings of the 1996 ACM SIGMOD international conference on Management of data - SIGMOD '96 · doi:10.1145/233269.233342 · Cited by 556
Self-citationA guided tour of chernoff bounds
Hagerup, T., & Rüb, C. (1990) · Information Processing Letters · doi:10.1016/0020-0190(90)90214-i · Cited by 524
An Overview of Wavelet Based Multiresolution Analyses
Jawerth, B., & Sweldens, W. (1994) · SIAM Review · doi:10.1137/1036095 · Cited by 517
Misra, J., & Gries, D. (1982) · Science of Computer Programming · doi:10.1016/0167-6423(82)90012-0 · Cited by 507
Potter's Wheel: An Interactive Data Cleaning System
Raman, V., & Hellerstein, J. L. (2001) · Cited by 492
Counting Distinct Elements in a Data Stream
Bar-Yossef, Z., Jayram, T. S., Kumar, R., Sivakumar, D., & Trevisan, L. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45726-7_1 · Cited by 460
Space-efficient online computation of quantile summaries
Greenwald, M., & Khanna, S. (2001) · Proceedings of the 2001 ACM SIGMOD international conference on Management of data · doi:10.1145/375663.375670 · Cited by 451
On the approximation of curves by line segments using dynamic programming
Bellman, R. (1961) · Communications of the ACM · doi:10.1145/366573.366611 · Cited by 444
Green: a framework for supporting energy-conscious programming using controlled approximation
Baek, W., & Chilimbi, T. M. (2010) · Proceedings of the 31st ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/1806596.1806620 · Cited by 440
Wavelet-based histograms for selectivity estimation
Matias, Y., Vitter, J. S., & Wang, M. (1998) · Proceedings - ACM-SIGMOD International Conference on Management of Data · doi:10.1145/276304.276344 · Cited by 425
Henzinger, M., Raghavan, P., & Rajagopalan, S. (1999) · DIMACS Series in Discrete Mathematics and Theoretical Computer Science · doi:10.1090/dimacs/050/05 · Cited by 418
The History of Histograms (abridged)
Ioannidis, Y. (2003) · Elsevier eBooks · doi:10.1016/b978-012722442-8/50011-2 · Cited by 417
Selection and sorting with limited storage
Munro, J. I., & Paterson, M. S. (1980) · Theoretical Computer Science · doi:10.1016/0304-3975(80)90061-4 · Cited by 414
Stable distributions, pseudorandom generators, embeddings, and data stream computation
Indyk, P. (2006) · Journal of the ACM · doi:10.1145/1147954.1147955 · Cited by 402
Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries
Gilbert, A. C., Kotidis, Y., Muthukrishnan, S., & Strauss, M. J. (2001) · Cited by 376
Ripple joins for online aggregation
Haas, P. J., & Hellerstein, J. M. (1999) · ACM SIGMOD Record · doi:10.1145/304181.304208 · Cited by 369
Self-citationMin-wise independent permutations (extended abstract)
Broder, A. Z., Charikar, M., Frieze, A. M., & Mitzenmacher, M. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276781 · Cited by 364
Accurate estimation of the number of tuples satisfying a condition
Piatetsky-Shapiro, G., & Connell, C. (1984) · Proceedings - ACM-SIGMOD International Conference on Management of Data · doi:10.1145/602259.602294 · Cited by 345
Processing complex aggregate queries over data streams
Dobra, A., Garofalakis, M., Gehrke, J., & Rastogi, R. (2002) · Proceedings of the 2002 ACM SIGMOD international conference on Management of data · doi:10.1145/564691.564699 · Cited by 319
Self-citationFinding frequent items in data streams
Cormode, G., & Hadjieleftheriou, M. (2008) · Proceedings of the VLDB Endowment · doi:10.14778/1454159.1454225 · Cited by 304
Self-citation"A Course in Approximation Theory"
Fasshauer, G. E., Cheney, W., & Light, W. (2004) · The American Mathematical Monthly · doi:10.2307/4145288 · Cited by 286
Maintaining stream statistics over sliding windows: (extended abstract)
Datar, M., Gionis, A., Indyk, P., & Motwani, R. (2002) · doi:10.5555/545381.545466 · Cited by 253
Fast, small-space algorithms for approximate histogram maintenance
Gilbert, A. C., Guha, S., Indyk, P., Kotidis, Y., Muthukrishnan, S., & Strauss, M. J. (2002) · Proceedings of the thiry-fourth annual ACM symposium on Theory of computing · doi:10.1145/509907.509966 · Cited by 242
Stable distributions, pseudorandom generators, embeddings and data stream computation
Indyk, P. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892082 · Cited by 238
Random sampling for histogram construction
Chaudhuri, S., Motwani, R., & Narasayya, V. R. (1998) · Proceedings - ACM-SIGMOD International Conference on Management of Data · doi:10.1145/276304.276343 · Cited by 234
Estimating flow distributions from sampled flow statistics
Duffield, N., Lund, C., & Thorup, M. (2003) · Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications · doi:10.1145/863955.863992 · Cited by 226
Online association rule mining
Hidber, C. (1999) · ACM SIGMOD Record · doi:10.1145/304181.304195 · Cited by 222
Estimating simple functions on the union of data streams
Gibbons, P. B., & Tirthapura, S. (2001) · doi:10.1145/378580.378687 · Cited by 217
Querying and mining data streams: you only get one look a tutorial
Garofalakis, M., Gehrke, J., & Rastogi, R. (2002) · Proceedings of the 2002 ACM SIGMOD international conference on Management of data · doi:10.1145/564691.564794 · Cited by 213
Self-citationTracking join and self-join sizes in limited storage
Alon, N., Gibbons, P. B., Matias, Y., & Szegedy, M. (1999) · doi:10.1145/303976.303978 · Cited by 211
Dynamic multidimensional histograms
Thaper, N., Guha, S., Indyk, P., & Koudas, N. (2002) · Proceedings of the 2002 ACM SIGMOD international conference on Management of data · doi:10.1145/564691.564741 · Cited by 206
Counter braids: a novel counter architecture for per-flow measurement
Lu, Y., Montanari, A., Prabhakar, B., Dharmapurikar, S., & Kabbani, A. (2008) · Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems · doi:10.1145/1375457.1375472 · Cited by 206
Probabilistic databases: diamonds in the dirt
Dalvi, N., Ré, C., & Suciu, D. (2009) · Communications of the ACM · doi:10.1145/1538788.1538810 · Cited by 195
Comparing Data Streams Using Hamming Norms (How to Zero In)
Cormode, G., Datar, M., Indyk, P., & Muthukrishnan, S. (2002) · Elsevier eBooks · doi:10.1016/b978-155860869-6/50037-8 · Cited by 190
Self-citationA Bayesian approach to bandwidth selection for multivariate kernel density estimation
Zhang, X., King, M. L., & Hyndman, R. J. (2006) · Computational Statistics & Data Analysis · doi:10.1016/j.csda.2005.06.019 · Cited by 186
On synopses for distinct-value estimation under multiset operations
Beyer, K., Haas, P. J., Reinwald, B., Sismanis, Y., & Gemulla, R. (2007) · Proceedings of the 2007 ACM SIGMOD international conference on Management of data · doi:10.1145/1247480.1247504 · Cited by 183
Self-citationApproximating multi-dimensional aggregate range queries over real attributes
Gunopulos, D., Kollios, G., Tsotras, V. J., & Domeniconi, C. (2000) · ACM SIGMOD Record · doi:10.1145/335191.335448 · Cited by 178
What's new: finding significant differences in network data streams
Cormode, G., & Muthukrishnan, S. (2005) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2005.860096 · Cited by 175
Self-citationApproximate Query Processing: Taming the TeraBytes
Garofalakis, M., & Gibbon, P. B. (2001) · Very Large Data Bases · Cited by 174
Self-citationGilbert, A. C., Kotidis, Y., Muthukrishnan, S., & Strauss, M. J. (2002) · VLDB '02: Proceedings of the 28th International Conference on Very Large Databases · doi:10.1016/b978-155860869-6/50047-0 · Cited by 173
Sequential sampling procedures for query size estimation
Haas, P. J., & Swami, A. K. (1992) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/130283.130335 · Cited by 172
Self-citationWavelet synopses with error guarantees
Garofalakis, M., & Gibbons, P. B. (2002) · Proceedings of the 2002 ACM SIGMOD international conference on Management of data · doi:10.1145/564691.564746 · Cited by 172
Self-citationSummarizing data using bottom-k sketches
Cohen, E., & Kaplan, H. Y. (2007) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/1281100.1281133 · Cited by 164
Tight lower bounds for the distinct elements problem
Indyk, P., & Woodruff, D. P. (2004) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2003.1238202 · Cited by 153
Querying and Mining Data Streams: You Only Get One Look.
Garofalakis, M., & Gehrke, J. E. (2002) · Very Large Data Bases · Cited by 149
Self-citationOn biased reservoir sampling in the presence of stream evolution
Aggarwal, C. C. (2006) · Very Large Data Bases · doi:10.5555/1182635.1164180 · Cited by 148
Optimal space lower bounds for all frequency moments
Woodruff, D. P. (2004) · Cited by 147
Reversible Sketches: Enabling Monitoring and Analysis Over High-Speed Data Streams
Schweller, R., Li, Z., Chen, Y., Gao, Y., Gupta, A., Zhang⋆, Y., Dinda, P. A., Kao, M., & Memik, G. (2007) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2007.896150 · Cited by 142
One-pass wavelet decompositions of data streams
Gilbert, A. C., Kotidis, Y., Muthukrishnan, S., & Strauss, M. (2003) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2003.1198389 · Cited by 132
ISOMER: Consistent Histogram Construction Using Query Feedback
Srivastava, U., Haas, P. J., Markl, V., Kutsch, M., & Tran, T. M. (2006) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2006.84 · Cited by 99
Self-citationSketching and Streaming Entropy via Approximation Theory
Harvey, N. J. A., Nelson, J., & Onak, K. (2008) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2008.76 · Cited by 96
What's new: Finding significant differences in network data streams
Cormode, G., & Muthukrishnan, S. (2004) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.2004.1354567 · Cited by 89
Self-citationScalable approximate query processing with the DBO engine
Jermaine, C., Arumugam, S., Pol, A., & Dobra, A. (2007) · Proceedings - ACM-SIGMOD International Conference on Management of Data · doi:10.1145/1247480.1247560 · Cited by 82
Self-citationAlgorithmic Challenges in Web Search Engines
Henzinger, M. R. (2004) · Internet Mathematics · doi:10.1080/15427951.2004.10129079 · Cited by 81
Optimal sampling from distributed streams
Cormode, G., Muthukrishnan, S., Yi, K., & Zhang, Q. (2010) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/1807085.1807099 · Cited by 76
Self-citationAccurate estimation of the number of tuples satisfying a condition
Piatetsky-Shapiro, G., & Connell, C. (1984) · ACM SIGMOD Record · doi:10.1145/971697.602294 · Cited by 72
Sketches for size of join estimation
Rusu, F., & Dobra, A. (2008) · ACM Transactions on Database Systems · doi:10.1145/1386118.1386121 · Cited by 69
Some History and Reminiscences on Survey Sampling
Hansen, M. H. (1987) · Statistical Science · doi:10.1214/ss/1177013352 · Cited by 59
Dynamic Histograms: Capturing Evolving Data Sets
Donjerkovic, D., Ioannidis, Y., & Ramakrishnan, R. (2005) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2000.839394 · Cited by 56
Data Stream Management: Processing High-Speed Data Streams (Data-Centric Systems and Applications)
Garofalakis, M., Gehrke, J. E., & Rastogi, R. R. (2007) · Springer eBooks · Cited by 53
Self-citationXCluster Synopses for Structured XML Content
Polyzotis, N., & Garofalakis, M. (2006) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2006.175 · Cited by 50
Self-citationA Fast Algorithm for Approximate Quantiles in High Speed Data Streams
Zhang, Q., & Wang, W. (2007) · International Conference on Scientific and Statistical Database Management · doi:10.1109/ssdbm.2007.27 · Cited by 47
Space Efficient Streaming Algorithms for the Maximum Error Histogram
Buragohain, C., Shrivastava, N., & Suri, S. (2007) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2007.368961 · Cited by 47
Online maintenance of very large random samples
Jermaine, C., Pol, A., & Arumugam, S. (2004) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/1007568.1007603 · Cited by 46
Self-citationGlobal optimization of histograms
Jagadish, H. V., Jin, H. X., Ooi, B. C., et al. (2001) · Proceedings - ACM-SIGMOD International Conference on Management of Data · doi:10.1145/375663.375687 · Cited by 46
Robust approximate aggregation in sensor data management systems
Considine, J., Hadjieleftheriou, M., Li, F., Byers, J. W., & Kollios, G. (2009) · ACM Transactions on Database Systems · doi:10.1145/1508857.1508863 · Cited by 38
Fast mining of massive tabular data via approximate distance computations
Cormode, G., Indyk, P., Koudas, N., & Muthukrishnan, S. (2003) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2002.994778 · Cited by 36
Self-citationAdaptive Spatial Partitioning for Multidimensional Data Streams
Hershberger, J. E., Shrivastava, N., Suri, S., & Tóth, C. D. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-30551-4_46 · Cited by 25
Sampling-based estimators for subset-based queries
Joshi, S., & Jermaine, C. (2008) · The VLDB Journal · doi:10.1007/s00778-008-0095-0 · Cited by 21
Self-citationA Bayesian method for guessing the extreme values in a data set
Wu, M., & Jermaine, C. (2007) · Very Large Data Bases · Cited by 19
Self-citationDobra, A. (2005) · ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/1065167.1065196 · Cited by 13
Haas, P. J., Ilyas, I. F., Lohman, G. M., & Markl, V. (2009) · Statistical Analysis and Data Mining The ASA Data Science Journal · doi:10.1002/sam.10016 · Cited by 10
Self-citation
Cited by
BlinkDB: queries with bounded errors and bounded response times on very large data
Agarwal, S., Mozafari, B., Panda, A., Milner, H., Madden, S., & Stoica, I. (2013) · Proceedings of the 8th ACM European Conference on Computer Systems · doi:10.1145/2465351.2465355 · Cited by 694
VideoEdge: Processing Camera Streams using Hierarchical Clusters
Hung, C.-C., Ananthanarayanan, G., Bodik, P., Golubchik, L., Yu, M., Bahl, P., & Philipose, M. (2018) · 2018 IEEE/ACM Symposium on Edge Computing (SEC) · doi:10.1109/sec.2018.00016 · Cited by 287
Profiling relational data: a survey
Abedjan, Z., Golab, L., & Naumann, F. (2015) · The VLDB Journal · doi:10.1007/s00778-015-0389-y · Cited by 283
A survey of data partitioning and sampling methods to support big data analysis
Mahmud, M. S., Huang, J. Z., Salloum, S., Emara, T. Z., & Sadatdiynov, K. (2020) · Big Data Mining and Analytics · doi:10.26599/bdma.2019.9020015 · Cited by 282
Yang, Z., Moczulski, M., Denil, M., De Freitas, N., Song, L., & Wang, Z. (2015) · 2015 IEEE International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2015.173 · Cited by 215
Metadata
- Authors
- Cormode, G., Garofalakis, M., Haas, P. J., & Jermaine, C.
- Venue
- Foundations and Trends in Databases
- Publisher
- Emerald
- Published
- 2011-12-31
- Volume
- 4
- Issue
- 1-3
- Pages
- 1-294
- ISSN
- 1931-7883 (ISSN-L)
- 1931-7891
- OpenAlex
- W2022858489
- Cited by
- 468
- References
- 126
- FWCI
- 15.61
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
