Source-linked AI summary
Early Accurate Results for Advanced Analytics on MapReduce
Nikolay Laptev, Kai Zeng, Carlo Zaniolo
TL;DR
Large-data analytics often need timely approximate answers, but MapReduce systems lack general support for accurate early results. EARL extends Hadoop with incremental sampling and resampling-based accuracy estimation; the paper describes using approximate results to avoid restarting failed nodes when the desired accuracy is reached.
Problem
MapReduce-oriented systems lack general methods for accurate incremental results, despite the need for timely approximate answers in large-data analytics.
Source: §1 · p. 1Method
Results
EARL can provide approximate results and guarantees despite node failures, avoiding failed-node restarts when the desired accuracy is reached.
Source: §8 · p. 11Takeaways & Limitations
Error estimates can help determine whether node recovery is necessary after failures.
Source: §1 · p. 1The optimization techniques are best suited to small sample sizes, and further work remains on delta maintenance and sampling.
Source: §4.2 · p. 7
Abstract
from arXiv · showhide
Approximate results based on samples often provide the only way in which advanced analytical applications on very massive data sets can satisfy their time and resource constraints. Unfortunately, methods and tools for the computation of accurate early results are currently not supported in MapReduce-oriented systems although these are intended for `big data'. Therefore, we proposed and implemented a non-parametric extension of Hadoop which allows the incremental computation of early results for arbitrary work-flows, along with reliable on-line estimates of the degree of accuracy achieved so far in the computation. These estimates are based on a technique called bootstrapping that has been widely employed in statistics and can be applied to arbitrary functions and data distributions. In this paper, we describe our Early Accurate Result Library (EARL) for Hadoop that was designed to minimize the changes required to the MapReduce framework. Various tests of EARL of Hadoop are presented to characterize the frequent situations where EARL can provide major speed-ups over the current version of Hadoop.
1. INTRODUCTION
Large-data analytics often need timely approximate answers, but MapReduce systems lack general support for accurate incremental results. EARL combines statistical resampling with Hadoop extensions to produce early results and estimate their accuracy.
1. INTRODUCTION
- EARL seeks accurate workflow results on massive datasets while minimizing computation time and resource use.Its early accuracy estimates can help determine whether node recovery is necessary after failures.Source: §1 · p. 1
- EARL targets complex analytics, extending early-result approaches beyond simple aggregates while addressing the lack of general approximation methods in MapReduce and parallel databases.The introduction frames quickly obtained approximate answers as valuable when exact results take too long.Source: §1 · p. 1
- EARL iteratively expands a uniform sample until bootstrap-based error estimates meet a user-defined accuracy threshold.The paper selects bootstrapping for its stated generality and accuracy; other resampling methods are left for future work.Source: §1 · pp. 1–2
- Unlike HOP, EARL supplies accuracy-estimation and sample-expansion control within its MapReduce approach; Hadoop’s distributed data and random key sampling support uniform samples.The authors chose Hadoop as the underlying engine and identify extending other resampling methods as outside this paper’s scope.Source: §1 · p. 2
- EARL can provide approximate results and guarantees despite node failures, avoiding task restarts when the desired accuracy is reached.The paper connects this capability to error estimation that can indicate whether node recovery is needed.Source: §1 · pp. 1–2
1.1 Contributions and Organization
- The contributions include a general early-approximation method with error bounds, a delta-maintained resampling optimization, and a distributed-file sampling strategy.EARL implements and experimentally validates the method on Hadoop.Source: §1.1 · p. 2
2. ARCHITECTURE
EARL samples the input, runs the user’s task on resamples, and estimates accuracy from the resulting distribution. Hadoop extensions support dynamically expanding the input and incremental reduction as the sample grows.
2. ARCHITECTURE
- EARL draws an initial uniform sample, runs the user’s task on resamples, and estimates accuracy from their result distribution, expanding the sample until the target is reached.Each added sample is aggregated with the existing sample before the process repeats.Source: §2 · p. 2
- The authors chose a relatively simple Hadoop extension for dynamic input and resampling after finding that HaLoop and Hadoop Online did not fit their requirements.They cite HaLoop overhead for non-iterative jobs and the need for further Hadoop Online modifications to adjust sample size.Source: §2 · p. 3
- EARL modifies Hadoop to let reducers process input before mappers finish, keep mappers active, and communicate termination conditions.Mappers monitor approximation error and expand the sample; active mappers are reused rather than restarted for each expansion.Source: §2 · p. 3
- Four finer-grained reduce methods support incremental jobs: initialize state, update it with new input, finalize the result and error, and correct the result.Users can supply correction logic when computation on a data subset requires adjustment, using the fraction of data processed.Source: §2 · p. 3
- EARL aims to add early-result approximation with minimal changes to users’ MapReduce jobs.The architecture has sampling, user-task, and accuracy-estimation stages.Source: §2 · pp. 2–3
3. ESTIMATING ACCURACY
EARL estimates error for general functions through resampling, then selects sample and bootstrap sizes and sampling strategies to meet a desired accuracy with less work. Its approximate results can also be accompanied by error estimates despite node failures.
3. ESTIMATING ACCURACY
- EARL concentrates on bootstrapping because jackknife fails for many functions, such as the median, and may require more resamples.Resampling estimates accuracy for general functions without requiring a theoretical formula.Source: §3 · p. 4
3.1 Accuracy Estimation Stage
- AES bootstraps a statistic computed from sample s to estimate its standard error cv; τ measures the stability of successive error estimates.If B × n ≥ N, EARL reports that early estimation is not faster and computes the function over the full dataset.Source: §3.1 · p. 4
3.2 Sample Size and Number of Bootstraps
- SSABE estimates B from cv stability, then fits cv across five progressively larger subsamples to select n before running the job with both estimates.The first phase estimates B and n; the second evaluates the function B times on a sample of size n.Source: §3.2 · pp. 4–5
- Because the initial sample is small, EARL can estimate B and n locally before MapReduce startup, using one JVM instead of separate mapper and reducer JVM tasks.The authors report that p = 0.01 gives robust results for the initial sample fraction.Source: §3.2 · pp. 4–5
3.3 Sampling
- Random block sampling may preserve clustered dependencies, while reservoir sampling reads the entire dataset; EARL therefore offers pre-map and post-map sampling.The section identifies these as problems with two straightforward sampling approaches.Source: §3.3 · p. 5
- Pre-map sampling reduces load time but can misrepresent the total key-value count because it samples lines; post-map sampling reads the data and yields a uniform sample with accurate counts.Post-map sampling is useful when a correction function needs an accurate estimate of the total key-value pairs.Source: §3.3 · pp. 5–6
3.4 Fault Tolerance
- With a user-specified approximation bound, EARL can provide a result and an error estimate with reasonable confidence despite node failures, avoiding task restarts.The paper frames this as a way to make a system more robust to node failures.Source: §3.4 · p. 6
4. OPTIMIZATIONS
The optimizations reduce repeated work by reusing results across iterations and overlapping bootstrap resamples. Intra-iteration optimization saves over 20% of work on average, while the techniques are best suited to small samples.
4. OPTIMIZATIONS
- Re-executing the user job on larger samples is EARL’s most computationally intensive work, so the optimizations reuse results from previous iterations.This reuse applies both during the main job and during initial sample-size estimation.Source: §4 · p. 6
4.1 Inter-Iteration Optimization
- Inter-iteration optimization reuses prior bootstrap resamples, updating them with items from the newly added delta sample instead of drawing each resample anew.This can save part of both the resampling cost and the cost of repeating the user job.Source: §4.1 · pp. 6–7
- Storing the sample and resamples on HDFS can make frequent disk access a bottleneck; EARL instead uses sketches in a two-layer memory-disk structure.For large n′ with fixed n/n′, the binomial model is approximated by a Gaussian; updates access sketches first and use HDFS when a sketch is exhausted.Source: §4.1 · p. 7
4.2 Intra-Iteration Optimization
- Because bootstrap resamples can share a substantial fraction of their data, intra-iteration optimization reuses the shared portion through delta maintenance.The paper gives an example in which roughly one in three resamples share 30% of their data.Source: §4.2 · p. 7
- Over 20% of work is saved on average by intra-iteration optimization compared with standard bootstrapping.The method chooses the overlap fraction y to minimize bootstrapping work.Source: §4.2 · p. 7
- The optimization techniques are best suited to small sample sizes, and delta maintenance and sampling still require further research.The paper frames small samples as reasonable in distributed systems where response time and data movement must be minimized.Source: §4.2 · p. 7
5. CURRENT IMPLEMENTATION
EARL’s Hadoop implementation integrates sampling, user-job execution, and accuracy estimation with modifications to MapReduce components. The implementation addresses potential overhead from repeated jobs, sample generation, and resampling.
5. CURRENT IMPLEMENTATION
- EARL implements pre-map sampling by modifying RecordReader and post-map sampling by extending the map class; resampling and updates extend the reduce class.Results from resamples feed accuracy estimation, and the estimated error is used to check the termination condition.Source: §5 · p. 8
- A naive design with separate sampler and accuracy-estimation jobs could run slower than standard Hadoop, especially for small datasets and light aggregates.The implementation aims to keep EARL lightweight so its worst-case execution time is comparable to standard Hadoop.Source: §5 · p. 8
- Pipelining and inter-task communication reuse Hadoop tasks as the sample is refined, while mappers can request additional input splits when a larger sample is needed.The passage also identifies sample generation and repeated resampling as sources of overhead.Source: §5 · p. 8
- Resampling runs in the reduce phase, and delta maintenance decreases its overhead.The implementation was developed and tested with Hadoop 0.20.2-dev on a five-machine cluster.Source: §5 · pp. 7–8
6. EXPERIMENTS
EARL’s experiments test early-result efficiency across simple and advanced analytics, sampling strategies, and incremental updates. Results show speedups alongside accuracy and workload conditions that inform when each approach is useful.
6. EXPERIMENTS
- Experiments use single-phase MapReduce tasks, a normalized error of 0.05, and synthetic data for asymptotic behavior and accuracy validation.Broader experiments on more mining algorithms were identified as future work.Source: §6 · p. 9
6.1 A Strong Case for EARL
- 4× speedup over standard Hadoop on datasets larger than 100GB for computing the mean; without early results below 1GB, EARL switches back without big overhead.The experiment also reports that pre-map sampling loads data more efficiently than standard Hadoop data loading.Source: §6.1 · p. 9
6.2 Approximate Median Computation
- 3-fold speedup over standard Hadoop for median computation with naïve Monte Carlo bootstrap, and another 4× speedup from the optimized algorithm over the original resampling algorithm.The comparison tests stock Hadoop, original resampling, and optimized resampling.Source: §6.2 · p. 9, Figure 6 · p. 9
6.3 EARL and Advanced Mining Algorithms
- EARL’s K-Means speedup comes from running on a smaller dataset and faster convergence there; on synthetic data, its centroids are within 5% of optimal.The comparison is against stock Hadoop.Source: §6.3 · p. 9, Figure 7 · p. 9
6.4 Sample Size and Number of Bootstraps
- For a 5% error threshold on the sample mean, the empirical method requires a 1% uniform sample and 30 bootstraps; theoretical predictions can over- or underestimate requirements.Theoretical sample-size predictions overestimate at low error tolerance and underestimate at relatively high tolerance; bootstrap predictions frequently underestimate the required count, though some tests found overestimation.Source: §6.4 · p. 10, Figure 8 · p. 10
6.5 Pre-map and Post-map Sampling
- Pre-map sampling is faster overall and, for large samples, as accurate as post-map sampling in estimating key/value counts; post-map sampling may be more accurate for small samples.Pre-map reduces load times but can reduce key/value-count estimation accuracy; post-map increases load times.Source: §6.5 · p. 10, Figure 9 · p. 10
6.6 Update Overhead
- For a 4GB dataset, delta-maintenance updates achieve close to 300% speedup over processing the full dataset without the optimization.The optimized strategy processes half the data and merges results with previously saved state.Source: §6.6 · p. 10, Figure 10 · p. 10
7. RELATED WORK
Related work spans Hadoop sampling, database sampling, specialized mining approximations, and online query systems. EARL is distinguished in these passages by its broader analytical scope and accuracy estimation, while its dynamic-input needs differ from iterative-processing extensions.
Hadoop sampling
- The Hadoop sampling framework in incrementally supplies random input splits, but its uniform-sample assumption is not well validated and it lacks an error-estimation framework.The cited work is described as a simple, useful overview of Hadoop sampling.Source: §7 · pp. 10–11
File and block sampling
- The 2-file and ARHASH approach in reduces expected disk seeks, but requires extension for a distributed filesystem; block sampling in can lose uniformity when data layout reflects dependencies.The block-sampling error depends on disk layout; varies the number of blocks to address this issue.Source: §7 · p. 11
Mining approximations
- FAST in uses two-phase sampling and reports speedups up to a factor of 10, but is specialized to a narrower mining task than EARL.The passage says EARL can obtain comparable results.Source: §7 · p. 11
Online query systems
- Online aggregation work [8, 15] and other MapReduce systems support early or continuous queries, but cited systems are limited to simple aggregates or do not estimate result accuracy.Bootstrapping optimization in was studied only for simple aggregates.Source: §7 · p. 11
Other platforms
- EARL could potentially be applied to Hyracks, whereas HaLoop targets iterative jobs and is not suited to dynamically expanding input.HaLoop improves iterative execution through loop-aware scheduling and caching.Source: §7 · p. 11
8. CONCLUSION
The conclusion presents EARL as a non-parametric Hadoop extension for early results with reliable accuracy estimates. Experiments suggest speedups across a broad range of applications, and the authors identify other resampling methods as future work.
Conclusion
- EARL combines statistical resampling with Hadoop to deliver early results and reliable accuracy estimates, with optimizations and distributed-filesystem sampling techniques.The authors say the approach can improve fault tolerance by avoiding failed-node restarts when the desired accuracy has already been reached.Source: §8 · p. 11
- Experimental results suggest speedups across a broad range of applications and potential interactive support for users working with large datasets.The conclusion identifies investigation of other resampling methods, such as jackknife, as future work.Source: §8 · p. 11
A. CATEGORICAL AND INTER-DEPENDENT DATA
The appendix extends EARL’s scope to categorical data and notes support for dependent data through modified bootstrap sampling. The work itself focuses on i.i.d. data.
Scope
- The appendix assumes numerical data and numerically ordered function results without loss of generality, while noting a small modification for categorical data.The categorical-data treatment is described in the following passage.Source: A. CATEGORICAL AND INTER-DEPENDENT DATA · p. 12
Categorical data
- For categorical data, EARL estimates a population proportion from the sample’s success fraction and uses a z-test for confidence intervals and significance with large samples.The passage treats the binomial distribution as approximately normal for large sample sizes.Source: A. CATEGORICAL AND INTER-DEPENDENT DATA · p. 12
Inter-dependent data
- The stated primary assumption is i.i.d. samples, but block sampling can preserve dependencies by selecting consecutive observations together.The passage identifies time-series data as a setting where such dependencies commonly occur and says dependent data can also be supported.Source: A. CATEGORICAL AND INTER-DEPENDENT DATA · p. 12