Building Wavelet Histograms on Large Data in MapReduce
[Overview] [Papers and Talks] [Source Code]
[Dataset] [Contacts]
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.
1. Building Wavelet Histograms on Large Data in MapReduce,
Full version:
Talk:
Important Notice
If you use this library for your work, please kindly cite our paper. Thanks!
If you find any bugs or any suggestions/comments,
we are very happy to hear from you!
Library Description
The library is developed in Java for use with Hadoop 0.20.2. The code is self-explanatory. A makefile is included to compile the library into a jar file. The classpath in the makefile should be updated to refer to the Hadoop 0.20.2 jar file and the Apache Commons Logging jar file. A customized scheduler which permits data-local only mappers and a user specified single reducer is also included.
Download
Wavelet Histogram MapReduce Library [tar.gz]
Quick Install
Hadoop 0.20.2 may be obtained from here and Apache
Commons Logging may be obtained from here. After obtaining both, update
the makefiles as mentioned above in order to compile. The library may be invoked by specifying the command:
hadoop jar wavelet.jar org.HadoopWavelet
A detailed description of command line arguments is displayed.
The real dataset used in this paper is publicly available here.
Jeffrey Jestes
Feifei Li