{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,24]],"date-time":"2025-09-24T09:22:15Z","timestamp":1758705735104},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2011,10]]},"abstract":"<jats:p>MapReduce is becoming the<jats:italic>de facto<\/jats:italic>framework for storing and processing massive data, due to its excellent scalability, reliability, and elasticity. In many MapReduce applications, obtaining a compact accurate summary of data is essential. Among various data summarization tools, histograms have proven to be particularly important and useful for summarizing data, and the wavelet histogram is one of the most widely used histograms. In this paper, we investigate the problem of building wavelet histograms efficiently on large datasets in MapReduce. We measure the efficiency of the algorithms by both end-to-end running time and communication cost. We demonstrate straightforward adaptations of existing exact and approximate methods for building wavelet histograms to MapReduce clusters are highly inefficient. To that end, we design new algorithms for computing exact and approximate wavelet histograms and discuss their implementation in MapReduce. We illustrate our techniques in Hadoop, and compare to baseline solutions with extensive experiments performed in a heterogeneous Hadoop cluster of 16 nodes, using large real and synthetic datasets, up to hundreds of gigabytes. The results suggest significant (often orders of magnitude) performance improvement achieved by our new algorithms.<\/jats:p>","DOI":"10.14778\/2078324.2078327","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"109-120","source":"Crossref","is-referenced-by-count":25,"title":["Building wavelet histograms on large data in MapReduce"],"prefix":"10.14778","volume":"5","author":[{"given":"Jeffrey","family":"Jestes","sequence":"first","affiliation":[{"name":"University of Utah Salt Lake City, Utah"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ke","family":"Yi","sequence":"additional","affiliation":[{"name":"HKUST, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Feifei","family":"Li","sequence":"additional","affiliation":[{"name":"University of Utah Salt Lake City, Utah"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,10]]},"reference":[{"issue":"1","key":"e_1_2_1_1_1","first-page":"922","article-title":"HadoopDB: An architectural hybrid of MapReduce and DBMS technologies for analytical workloads","volume":"2","author":"Abouzeid A.","year":"2009","unstructured":"A. Abouzeid , K. Bajda-Pawlikowski , D. J. Abadi , A. Rasin , and A. Silberschatz . HadoopDB: An architectural hybrid of MapReduce and DBMS technologies for analytical workloads . PVLDB , 2 ( 1 ): 922 -- 933 , 2009 . A. Abouzeid, K. Bajda-Pawlikowski, D. J. Abadi, A. Rasin, and A. Silberschatz. HadoopDB: An architectural hybrid of MapReduce and DBMS technologies for analytical workloads. PVLDB, 2(1):922--933, 2009.","journal-title":"PVLDB"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1145\/1739041.1739056","volume-title":"EDBT","author":"Afrati F. N.","year":"2010","unstructured":"F. N. Afrati and J. D. Ullman . Optimizing joins in a map-reduce environment . In EDBT , pages 99 -- 110 , 2010 . 10.1145\/1739041.1739056 F. N. Afrati and J. D. Ullman. Optimizing joins in a map-reduce environment. In EDBT, pages 99--110, 2010. 10.1145\/1739041.1739056"},{"key":"e_1_2_1_3_1","first-page":"163","volume-title":"SIGKDD","author":"Aggarwal C. C.","year":"2002","unstructured":"C. C. Aggarwal . On effective classification of strings with wavelets . In SIGKDD , pages 163 -- 172 , 2002 . 10.1145\/775047.775071 C. C. Aggarwal. On effective classification of strings with wavelets. In SIGKDD, pages 163--172, 2002. 10.1145\/775047.775071"},{"key":"e_1_2_1_4_1","first-page":"20","volume-title":"STOC","author":"Alon N.","year":"1996","unstructured":"N. Alon , Y. Matias , and M. Szegedy . The space complexity of approximating the frequency moments . In STOC , pages 20 -- 29 , 1996 . 10.1145\/237814.237823 N. Alon, Y. Matias, and M. Szegedy. The space complexity of approximating the frequency moments. In STOC, pages 20--29, 1996. 10.1145\/237814.237823"},{"key":"e_1_2_1_5_1","unstructured":"Amazon EC2. http:\/\/aws.amazon.com\/ec2\/. Amazon EC2. http:\/\/aws.amazon.com\/ec2\/."},{"key":"e_1_2_1_6_1","volume-title":"Workload characterization of the 1998 world cup web site. Technical report","author":"Arlitt M.","year":"1999","unstructured":"M. Arlitt and T. Jin . Workload characterization of the 1998 world cup web site. Technical report , IEEE Network , 1999 . M. Arlitt and T. Jin. Workload characterization of the 1998 world cup web site. Technical report, IEEE Network, 1999."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1145\/1011767.1011798","volume-title":"PODC","author":"Cao P.","year":"2004","unstructured":"P. Cao and Z. Wang . Efficient top-k query calculations in distributed networks . In PODC , pages 206 -- 215 , 2004 . 10.1145\/1011767.1011798 P. Cao and Z. Wang. Efficient top-k query calculations in distributed networks. In PODC, pages 206--215, 2004. 10.1145\/1011767.1011798"},{"issue":"2","key":"e_1_2_1_8_1","first-page":"1265","article-title":"SCOPE: easy and efficient parallel processing of massive data sets","volume":"1","author":"Chaiken R.","year":"2008","unstructured":"R. Chaiken , B. Jenkins , P.-A. Larson , B. Ramsey , D. Shakib , S. Weaver , and J. Zhou . SCOPE: easy and efficient parallel processing of massive data sets . PVLDB , 1 ( 2 ): 1265 -- 1276 , 2008 . R. Chaiken, B. Jenkins, P.-A. Larson, B. Ramsey, D. Shakib, S. Weaver, and J. Zhou. SCOPE: easy and efficient parallel processing of massive data sets. PVLDB, 1(2):1265--1276, 2008.","journal-title":"PVLDB"},{"issue":"2","key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/s007780100049","article-title":"Approximate query processing using wavelets","volume":"10","author":"Chakrabarti K.","year":"2001","unstructured":"K. Chakrabarti , M. Garofalakis , R. Rastogi , and K. Shim . Approximate query processing using wavelets . VLDBJ , 10 ( 2-3 ): 199 -- 223 , 2001 . K. Chakrabarti, M. Garofalakis, R. Rastogi, and K. Shim. Approximate query processing using wavelets. VLDBJ, 10(2-3):199--223, 2001.","journal-title":"VLDBJ"},{"issue":"2","key":"e_1_2_1_10_1","first-page":"1481","article-title":"MAD skills: New analysis practices for big data","volume":"2","author":"Cohen J.","year":"2009","unstructured":"J. Cohen , B. Dolan , M. Dunlap , J. M. Hellerstein , and C. Welton . MAD skills: New analysis practices for big data . PVLDB , 2 ( 2 ): 1481 -- 1492 , 2009 . J. Cohen, B. Dolan, M. Dunlap, J. M. Hellerstein, and C. Welton. MAD skills: New analysis practices for big data. PVLDB, 2(2):1481--1492, 2009.","journal-title":"PVLDB"},{"key":"e_1_2_1_11_1","first-page":"21","volume-title":"NSDI","author":"Condie T.","year":"2010","unstructured":"T. Condie , N. Conway , P. Alvaro , J. M. Hellerstein , K. Elmeleegy , and R. Sears . MapReduce online . In NSDI , pages 21 -- 21 , 2010 . T. Condie, N. Conway, P. Alvaro, J. M. Hellerstein, K. Elmeleegy, and R. Sears. MapReduce online. In NSDI, pages 21--21, 2010."},{"key":"e_1_2_1_12_1","first-page":"1115","volume-title":"SIGMOD","author":"Condie T.","year":"2010","unstructured":"T. Condie , N. Conway , P. Alvaro , J. M. Hellerstein , J. Gerth , J. Talbot , K. Elmeleegy , and R. Sears . Online aggregation and continuous query support in MapReduce . In SIGMOD , pages 1115 -- 1118 , 2010 . 10.1145\/1807167.1807295 T. Condie, N. Conway, P. Alvaro, J. M. Hellerstein, J. Gerth, J. Talbot, K. Elmeleegy, and R. Sears. Online aggregation and continuous query support in MapReduce. In SIGMOD, pages 1115--1118, 2010. 10.1145\/1807167.1807295"},{"key":"e_1_2_1_13_1","first-page":"26","volume-title":"EDBT","author":"Cormode G.","year":"2006","unstructured":"G. Cormode , M. Garofalakis , and D. Sacharidis . Fast approximate wavelet tracking on streams . In EDBT , pages 26 -- 30 , 2006 . 10.1007\/11687238_4 G. Cormode, M. Garofalakis, and D. Sacharidis. Fast approximate wavelet tracking on streams. In EDBT, pages 26--30, 2006. 10.1007\/11687238_4"},{"key":"e_1_2_1_14_1","first-page":"1530","volume-title":"VLDB","author":"Cormode G.","year":"2008","unstructured":"G. Cormode and M. Hadjieleftheriou . Finding frequent items in data streams . In VLDB , pages 1530 -- 1541 , 2008 . G. Cormode and M. Hadjieleftheriou. Finding frequent items in data streams. In VLDB, pages 1530--1541, 2008."},{"key":"e_1_2_1_15_1","first-page":"137","volume-title":"OSDI","author":"Dean J.","year":"2004","unstructured":"J. Dean and S. Ghemawat . MapReduce: simplified data processing on large clusters . In OSDI , pages 137 -- 150 , 2004 . J. Dean and S. Ghemawat. MapReduce: simplified data processing on large clusters. In OSDI, pages 137--150, 2004."},{"issue":"1","key":"e_1_2_1_16_1","first-page":"518","article-title":"Hadoop++: Making a yellow elephant run like a cheetah","volume":"3","author":"Dittrich J.","year":"2010","unstructured":"J. Dittrich , J.-A. Quian\u00e9-Ruiz , A. Jindal , Y. Kargin , V. Setty , and J. Schad . Hadoop++: Making a yellow elephant run like a cheetah . PVLDB , 3 ( 1 ): 518 -- 529 , 2010 . J. Dittrich, J.-A. Quian\u00e9-Ruiz, A. Jindal, Y. Kargin, V. Setty, and J. Schad. Hadoop++: Making a yellow elephant run like a cheetah. PVLDB, 3(1):518--529, 2010.","journal-title":"PVLDB"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00026-6"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","first-page":"476","DOI":"10.1145\/564691.564746","volume-title":"SIGMOD","author":"Garofalakis M.","year":"2002","unstructured":"M. Garofalakis and P. B. Gibbons . Wavelet synopses with error guarantees . In SIGMOD , pages 476 -- 487 , 2002 . 10.1145\/564691.564746 M. Garofalakis and P. B. Gibbons. Wavelet synopses with error guarantees. In SIGMOD, pages 476--487, 2002. 10.1145\/564691.564746"},{"issue":"2","key":"e_1_2_1_19_1","first-page":"1414","article-title":"Building a high-level dataflow system on top of Map-Reduce: the Pig experience","volume":"2","author":"Gates A. F.","year":"2009","unstructured":"A. F. Gates , O. Natkovich , S. Chopra , P. Kamath , S. M. Narayanamurthy , C. Olston , B. Reed , S. Srinivasan , and U. Srivastava . Building a high-level dataflow system on top of Map-Reduce: the Pig experience . PVLDB , 2 ( 2 ): 1414 -- 1425 , 2009 . A. F. Gates, O. Natkovich, S. Chopra, P. Kamath, S. M. Narayanamurthy, C. Olston, B. Reed, S. Srinivasan, and U. Srivastava. Building a high-level dataflow system on top of Map-Reduce: the Pig experience. PVLDB, 2(2):1414--1425, 2009.","journal-title":"PVLDB"},{"key":"e_1_2_1_20_1","first-page":"79","volume-title":"VLDB","author":"Gilbert A. C.","year":"2001","unstructured":"A. C. Gilbert , Y. Kotidis , S. Muthukrishnan , and M. Strauss . Surfing wavelets on streams: One-pass summaries for approximate aggregate queries . In VLDB , pages 79 -- 88 , 2001 . A. C. Gilbert, Y. Kotidis, S. Muthukrishnan, and M. Strauss. Surfing wavelets on streams: One-pass summaries for approximate aggregate queries. In VLDB, pages 79--88, 2001."},{"key":"e_1_2_1_21_1","first-page":"88","volume-title":"SIGKDD","author":"Guha S.","year":"2005","unstructured":"S. Guha and B. Harb . Wavelet synopsis for data streams: minimizing non-euclidean error . In SIGKDD , pages 88 -- 97 , 2005 . 10.1145\/1081870.1081884 S. Guha and B. Harb. Wavelet synopsis for data streams: minimizing non-euclidean error. In SIGKDD, pages 88--97, 2005. 10.1145\/1081870.1081884"},{"key":"e_1_2_1_22_1","unstructured":"Hadoop Project. http:\/\/hadoop.apache.org\/. Hadoop Project. http:\/\/hadoop.apache.org\/."},{"key":"e_1_2_1_23_1","first-page":"1997","volume-title":"IEEE INFOCOM","author":"Huang Z.","year":"2011","unstructured":"Z. Huang , K. Yi , Y. Liu , and G. Chen . Optimal sampling algorithms for frequency estimation in distributed data . In IEEE INFOCOM , pages 1997 -- 2005 , 2011 . Z. Huang, K. Yi, Y. Liu, and G. Chen. Optimal sampling algorithms for frequency estimation in distributed data. In IEEE INFOCOM, pages 1997--2005, 2011."},{"key":"e_1_2_1_24_1","first-page":"275","volume-title":"VLDB","author":"Jagadish H. V.","year":"1998","unstructured":"H. V. Jagadish , N. Koudas , S. Muthukrishnan , V. Poosala , K. C. Sevcik , and T. Suel . Optimal histograms with quality guarantees . In VLDB , pages 275 -- 286 , 1998 . H. V. Jagadish, N. Koudas, S. Muthukrishnan, V. Poosala, K. C. Sevcik, and T. Suel. Optimal histograms with quality guarantees. In VLDB, pages 275--286, 1998."},{"issue":"1","key":"e_1_2_1_25_1","first-page":"472","article-title":"The performance of MapReduce: An in-depth study","volume":"3","author":"Jiang D.","year":"2010","unstructured":"D. Jiang , B. C. Ooi , L. Shi , and S. Wu . The performance of MapReduce: An in-depth study . PVLDB , 3 ( 1 ): 472 -- 483 , 2010 . D. Jiang, B. C. Ooi, L. Shi, and S. Wu. The performance of MapReduce: An in-depth study. PVLDB, 3(1):472--483, 2010.","journal-title":"PVLDB"},{"key":"e_1_2_1_26_1","first-page":"448","volume-title":"SIGMOD","author":"Matias Y.","year":"1998","unstructured":"Y. Matias , J. S. Vitter , and M. Wang . Wavelet-based histograms for selectivity estimation . In SIGMOD , pages 448 -- 459 , 1998 . 10.1145\/276305.276344 Y. Matias, J. S. Vitter, and M. Wang. Wavelet-based histograms for selectivity estimation. In SIGMOD, pages 448--459, 1998. 10.1145\/276305.276344"},{"key":"e_1_2_1_27_1","first-page":"101","volume-title":"VLDB","author":"Matias Y.","year":"2000","unstructured":"Y. Matias , J. S. Vitter , and M. Wang . Dynamic maintenance of wavelet-based histograms . In VLDB , pages 101 -- 110 , 2000 . Y. Matias, J. S. Vitter, and M. Wang. Dynamic maintenance of wavelet-based histograms. In VLDB, pages 101--110, 2000."},{"key":"e_1_2_1_28_1","first-page":"637","volume-title":"VLDB","author":"Michel S.","year":"2005","unstructured":"S. Michel , P. Triantafillou , and G. Weikum . KLEE: a framework for distributed top-k query algorithms . In VLDB , pages 637 -- 648 , 2005 . S. Michel, P. Triantafillou, and G. Weikum. KLEE: a framework for distributed top-k query algorithms. In VLDB, pages 637--648, 2005."},{"key":"e_1_2_1_29_1","first-page":"1099","volume-title":"SIGMOD","author":"Olston C.","year":"2008","unstructured":"C. Olston , B. Reed , U. Srivastava , R. Kumar , and A. Tomkins . Pig latin: a not-so-foreign language for data processing . In SIGMOD , pages 1099 -- 1110 , 2008 . 10.1145\/1376616.1376726 C. Olston, B. Reed, U. Srivastava, R. Kumar, and A. Tomkins. Pig latin: a not-so-foreign language for data processing. In SIGMOD, pages 1099--1110, 2008. 10.1145\/1376616.1376726"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00446-008-0055-3","article-title":"Approximate distributed top-k queries","volume":"21","author":"Patt-Shamir B.","year":"2008","unstructured":"B. Patt-Shamir and A. Shafrir . Approximate distributed top-k queries . Distributed Computing , 21 : 1 -- 22 , 2008 . B. Patt-Shamir and A. Shafrir. Approximate distributed top-k queries. Distributed Computing, 21:1--22, 2008.","journal-title":"Distributed Computing"},{"key":"e_1_2_1_31_1","first-page":"165","volume-title":"SIGMOD","author":"Pavlo A.","year":"2009","unstructured":"A. Pavlo , E. Paulson , A. Rasin , D. J. Abadi , D. J. DeWitt , S. Madden , and M. Stonebraker . A comparison of approaches to large-scale data analysis . In SIGMOD , pages 165 -- 178 , 2009 . 10.1145\/1559845.1559865 A. Pavlo, E. Paulson, A. Rasin, D. J. Abadi, D. J. DeWitt, S. Madden, and M. Stonebraker. A comparison of approaches to large-scale data analysis. In SIGMOD, pages 165--178, 2009. 10.1145\/1559845.1559865"},{"key":"e_1_2_1_32_1","first-page":"294","volume-title":"SIGMOD","author":"Poosala V.","year":"1996","unstructured":"V. Poosala , P. J. Haas , Y. E. Ioannidis , and E. J. Shekita . Improved histograms for selectivity estimation of range predicates . In SIGMOD , pages 294 -- 305 , 1996 . 10.1145\/233269.233342 V. Poosala, P. J. Haas, Y. E. Ioannidis, and E. J. Shekita. Improved histograms for selectivity estimation of range predicates. In SIGMOD, pages 294--305, 1996. 10.1145\/233269.233342"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050009"},{"key":"e_1_2_1_34_1","volume-title":"Parallel top-k query processing using MapReduce. Technical report","author":"Son M.","year":"2010","unstructured":"M. Son and H. Im . Parallel top-k query processing using MapReduce. Technical report , Pohang University of Science and Technology , 2010 . M. Son and H. Im. Parallel top-k query processing using MapReduce. Technical report, Pohang University of Science and Technology, 2010."},{"key":"e_1_2_1_35_1","volume-title":"Springer-Verlag","author":"Srinivasan R.","year":"2002","unstructured":"R. Srinivasan . Importance sampling - Applications in communications and detection . Springer-Verlag , 2002 . R. Srinivasan. Importance sampling - Applications in communications and detection. Springer-Verlag, 2002."},{"issue":"2","key":"e_1_2_1_36_1","first-page":"1626","article-title":"Hive: a warehousing solution over a map-reduce framework","volume":"2","author":"Thusoo A.","year":"2009","unstructured":"A. Thusoo , J. S. Sarma , N. Jain , Z. Shao , P. Chakka , S. Anthony , H. Liu , P. Wyckoff , and R. Murthy . Hive: a warehousing solution over a map-reduce framework . PVLDB , 2 ( 2 ): 1626 -- 1629 , 2009 . A. Thusoo, J. S. Sarma, N. Jain, Z. Shao, P. Chakka, S. Anthony, H. Liu, P. Wyckoff, and R. Murthy. Hive: a warehousing solution over a map-reduce framework. PVLDB, 2(2):1626--1629, 2009.","journal-title":"PVLDB"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/1116025","article-title":"On the uniform convergence of relative frequencies of events to their probabilities","volume":"16","author":"Vapnik V. N.","year":"1971","unstructured":"V. N. Vapnik and A. Y. Chervonenkis . On the uniform convergence of relative frequencies of events to their probabilities . Theory of Probability and its Applications , 16 : 264 -- 280 , 1971 . V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16:264--280, 1971.","journal-title":"Theory of Probability and its Applications"},{"key":"e_1_2_1_38_1","first-page":"495","volume-title":"SIGMOD","author":"Vernica R.","year":"2010","unstructured":"R. Vernica , M. J. Carey , and C. Li . Efficient parallel set-similarity joins using MapReduce . In SIGMOD , pages 495 -- 506 , 2010 . 10.1145\/1807167.1807222 R. Vernica, M. J. Carey, and C. Li. Efficient parallel set-similarity joins using MapReduce. In SIGMOD, pages 495--506, 2010. 10.1145\/1807167.1807222"},{"key":"e_1_2_1_39_1","first-page":"298","volume-title":"PODS","author":"Zhao Q.","year":"2006","unstructured":"Q. Zhao , M. Ogihara , H. Wang , and J. Xu . Finding global icebergs over distributed data sets . In PODS , pages 298 -- 307 , 2006 . 10.1145\/1142351.1142394 Q. Zhao, M. Ogihara, H. Wang, and J. Xu. Finding global icebergs over distributed data sets. In PODS, pages 298--307, 2006. 10.1145\/1142351.1142394"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2078324.2078327","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T14:42:17Z","timestamp":1689345737000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2078324.2078327"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,10]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,10]]}},"alternative-id":["10.14778\/2078324.2078327"],"URL":"https:\/\/doi.org\/10.14778\/2078324.2078327","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2011,10]]}}}