Introduction
In the era of "Big Data," the primary bottleneck for inductive learning—such as building decision trees—is no longer just raw computation, but I/O. When datasets are too large to fit in memory, algorithms must read from secondary storage. Traditional state-of-the-art algorithms (like SPRINT or BOAT) required multiple sequential scans of the data to build a model. Even meta-learning techniques usually required at least two scans. This paper introduces a general framework that can produce high-quality models with less than one full scan, significantly reducing the time and cost associated with data access.
Methodology
The authors propose a framework that combines an averaging ensemble approach with Hoeffding’s inequality to determine when enough data has been processed. The framework consists of two main algorithmic approaches:
- The One-Scan Ensemble (Strawman): This algorithm partitions the dataset into $K$ disjoint subsets. A base model (e.g., a decision tree or Naive Bayes classifier) is trained on each subset. These models are then combined into an averaging ensemble. Instead of simple voting, the ensemble averages the expected benefits or probabilities from each base model to make a final prediction. This requires exactly one pass through the data.
- The Less-Than-One-Scan Algorithm: This is the core innovation. Using Hoeffding’s inequality, the algorithm determines the probability that the current ensemble's prediction matches the "complete" ensemble (the one that would have seen all $K$ subsets). After training on a few subsets, the algorithm checks a validation set. If the confidence threshold (e.g., 99.7%) is met, the algorithm stops reading data and returns the current model.
Crucially, this framework is learner-independent. Unlike previous "fast" algorithms that only worked for decision trees, this method works for any inductive learner, including rule-based systems (RIPPER) and Naive Bayes (NB).
Experimental Results
The researchers evaluated their approach on three distinct datasets: KDDCUP’98 (Donation), Credit Card Fraud (5 million records), and Adult (UCI). The evaluation focused on both traditional accuracy and cost-sensitive applications.
As shown in the results above, the "Less Than One Scan" approach (Sequential) achieved accuracy comparable to or better than the full-batch ensemble while reading significantly less data. On natural, unsorted data, the algorithm typically required only 40% to 70% of the data to reach the confidence threshold. In the Credit Card Fraud experiments, the ensemble actually outperformed a single model trained on the entire dataset, increasing total benefits by $7,000 to $10,000.
Robustness to Bias
A key strength of the Hoeffding-based approach is its distribution independence. If the data is "biased" (e.g., sorted by transaction amount), the Hoeffding error remains high for longer. The algorithm "senses" this lack of confidence and automatically reads more data to compensate.
Even when intentionally challenged with biased, sorted data, the algorithm correctly identified the need for more information, eventually reading ~90% of the data to maintain high accuracy and benefit levels, as seen in the tables above.
Key Insights and Discussion
- The I/O Bottleneck: For massive datasets, the number of disk touches is the most critical metric for scalability. By reducing this to a fraction of a single scan, the authors provide a significant speedup over traditional scalable learners.
- Ensembles for Efficiency: While ensembles are typically used to boost accuracy, here they serve as a statistical tool to justify early stopping.
- Limitations: The algorithm requires a validation set to test for convergence. While this can be managed with minimal memory, it is an additional requirement. Furthermore, performance can be sensitive to the number of partitions ($K$) and the confidence threshold ($p$).
In conclusion, this framework demonstrates that for many large-scale learning tasks, reading the entire dataset is often unnecessary. By leveraging statistical bounds, researchers can build robust models with a fraction of the I/O cost.
Summary updated