Computer Science – Databases
Scientific paper
2011-10-30
Proceedings of the VLDB Endowment (PVLDB), Vol. 5, No. 2, pp. 109-120 (2011)
Computer Science
Databases
VLDB2012
Scientific paper
MapReduce is becoming the de facto 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.
Jestes Jeffrey
Li Feifei
Yi Ke
No associations
LandOfFree
Building Wavelet Histograms on Large Data in MapReduce does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Building Wavelet Histograms on Large Data in MapReduce, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Building Wavelet Histograms on Large Data in MapReduce will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-146780