DBScholar

Back to papers

Building Wavelet Histograms on Large Data in MapReduce

Summary: Proposes exact and approximate wavelet histogram algorithms for MapReduce, cutting communication and runtime vs naive approaches. Implemented in Hadoop and evaluated on a 16-node cluster with real and synthetic data, showing large improvements. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h32436c103450cb9a
Venue
VLDB
Year
2012
Pagerank
6.0293278e-05
Overall Rank
5,664 | 62.04%
DOI
10.14778/2078324.2078327

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{jestes_vldb12,
        title = {{Building Wavelet Histograms on Large Data in MapReduce}},
        author = {Jestes, Jeffrey and Yi, Ke and Li, Feifei},
        journal = {PVLDB},
        series = {{VLDB} '12},
        volume = {5},
        number = {2},
        pages = {109--120},
        doi = {10.14778/2078324.2078327},
        url = {https://doi.org/10.14778/2078324.2078327},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank Citing Paper Year Venue Pagerank
1,156 QuickSel: Quick Selectivity Learning with Mixture Models 2020 SIGMOD 0.00011759683
2,561 Minimal MapReduce Algorithms 2013 SIGMOD 8.2743492e-05
3,228 Multi-Query Optimization in MapReduce Framework 2014 VLDB 7.4957341e-05
7,720 Enabling Efficient and General Subpopulation Analytics in Multidimensional Data Streams 2022 VLDB 5.4542911e-05
9,176 One Seed, Two Birds: A Unified Learned Structure for Exact and Approximate Counting 2024 SIGMOD 5.200391e-05
10,346 Distributed Wavelet Thresholding for Maximum Error Metrics 2016 SIGMOD 5.0197268e-05
12,304 Efficient Haar+ Synopsis Construction for the Maximum Absolute Error Measure 2018 VLDB 4.9605343e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 22 of 22 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
5 Optimal Aggregation Algorithms for Middleware [Extended Abstract] 2001 PODS 0.0010688884
6 Pig Latin: A Not-So-Foreign Language for Data Processing 2008 SIGMOD 0.0010494385
30 SCOPE: Easy and Efficient Parallel Processing of Massive Data Sets 2008 VLDB 0.00050364918
31 Hive - A Warehousing Solution Over a Map-Reduce Framework 2009 VLDB 0.00049707539
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00047654188
43 A Comparison of Approaches to Large-Scale Data Analysis 2009 SIGMOD 0.00045453255
120 HadoopDB: An Architectural Hybrid of MapReduce and DBMS Technologies for Analytical Workloads 2009 VLDB 0.00031017868
154 MAD Skills: New Analysis Practices for Big Data 2009 VLDB 0.00028524078
171 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00027063233
277 Optimal Histograms with Quality Guarantees 1998 VLDB 0.0002235043
311 Approximate Query Processing Using Wavelets 2000 VLDB 0.00021315058
316 Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries 2001 VLDB 0.00021238056
359 Efficient Parallel Set-Similarity Joins Using MapReduce 2010 SIGMOD 0.00019963275
655 Building a High-Level Dataflow System on top of Map-Reduce: The Pig Experience 2009 VLDB 0.00015076669
677 Hadoop++: Making a Yellow Elephant Run Like a Cheetah (Without It Even Noticing) 2010 VLDB 0.00014835154
911 Finding Frequent Items in Data Streams 2008 VLDB 0.00013093314
1,006 Dynamic Maintenance of Wavelet-Based Histograms 2000 VLDB 0.00012551491
1,174 Wavelet Synopses with Error Guarantees 2002 SIGMOD 0.0001165008
1,470 The Performance of MapReduce: An In-depth Study 2010 VLDB 0.00010532106
2,372 Online Aggregation and Continuous Query support in MapReduce 2010 SIGMOD 8.5454388e-05
2,880 KLEE: A Framework for Distributed Top-k Query Algorithms 2005 VLDB 7.8948229e-05
6,201 Finding Global Icebergs over Distributed Data Sets 2006 PODS 5.8350139e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,299 A Platform for Scalable One-Pass Analytics using MapReduce 2011 SIGMOD
2 3,312 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS
3 171 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD
4 1,470 The Performance of MapReduce: An In-depth Study 2010 VLDB
5 316 Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries 2001 VLDB
6 5,800 Extended Wavelets for Multiple Measures 2003 SIGMOD
7 4,290 One-Pass Wavelet Synopses for Maximum-Error Metrics 2005 VLDB
8 1,006 Dynamic Maintenance of Wavelet-Based Histograms 2000 VLDB
9 222 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD
10 10,346 Distributed Wavelet Thresholding for Maximum Error Metrics 2016 SIGMOD