Mining high-speed data streams

By Pedro M. Domingos, Geoff Hulten. 2000

2,445 citations recorded by the source corpus.

Many organizations today have more than very large databases; they have databases that grow without limit at a rate of several million records per day. Mining these continuous data streams brings unique opportunities, but also new challenges. This paper describes and evaluates VFDT, an anytime system that builds decision trees using constant memory and constant time per example. VFDT can incorporate tens of thousands of examples per second using off-the-shelf hardware. It uses Hoeffding bounds to guarantee that its output is asymptotically nearly identical to that of a conventional learner. We study VFDT's properties and demonstrate its utility through an extensive set of experiments on synthetic data. We apply VFDT to mining the continuous stream of Web access data from the whole University of Washington main campus.

Subfields: Artificial Intelligence, Information Systems, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

In Signal Processing

Citations in the corpus

Nothing Else Matters: Model-Agnostic Explanations By Identifying Prediction Invariance (2016, methodology): “This uses the same insight as Hoeffding trees [3], with the key difference that we can control the sampling distribution, and thus can use the bounds to sample the regions of the input space that reduce the uncertainty between the precision estimates with as few samples as possible.”
Learning Fair Rule Lists (2019, methodology): “In addition, they relied on the use of an Hoeffding tree [19] to provide better fairness and accuracy in the online setting.”
Memory Efficient Experience Replay for Streaming Learning (2018, background): “Many are based on Hoeffding Decision Trees [6], [18], [25], [36],”
Lifelong Machine Learning with Deep Streaming Linear Discriminant Analysis (2019, background): “Hoeffding Decision Trees [4, 16, 21, 27, 28] incrementally grow decision trees over time under the Hoeffding bound theoretical guarantees.”
Towards Making Systems Forget with Machine Unlearning (2015, methodology): “Since VFDT supports the C4.5 data format, the intermediate output of OSNSF (i.e., the extracted feature values for each cluster) can be easily fed into VFDT.”
Interpreting Blackbox Models via Model Extraction (2017, background): “A related result is [20], but their analysis is limited to discrete features, for which convergence is much easier to analyze.”
Reacting to Different Types of Concept Drift: The Accuracy Updated Ensemble Algorithm (2014, background): “Compared to VFDT-based ensembles, such as ASHT and HOT, we do not limit base classifier size and do not use any windows.”
Scalable and efficient multi-label classification for evolving data streams (2012, methodology): “Here, we extend the Hoeffding Tree to deal with multi-label data: a Multi-label Hoeffding Tree.”
Data mining with differential privacy (2010, methodology): “We generated synthetic datasets using a method adapted from [6].”
Continuous queries over data streams (2001, background): “In terms of building classical data mining models over a single data stream, reference [Hid99] considers frequent itemsets and association rules, reference [GMMO00] considers clustering, and references [ DH00 , HSD01] consider decision trees.”
Stream-51: Streaming Classification and Novelty Detection from Videos (2020, background): “Online learning in a single pass with severe memory and compute constraints, also called streaming learning [2, 5, 10, 13, 14, 20, 35], more closely matches how embedded agents must learn and make inferences in real-time.”
Interpretable models from distributed data via merging of decision trees (2013, methodology): “Among centralized approaches for tree construction VFDT is probably the most popular method [13].”
Density-Based Clustering over an Evolving Data Stream with Noise (2006, background): “Analyzing and mining such kinds of data have been becoming a hot topic [1, 2, 4, 6, 10, 14].”
Mondrian Forests: Efficient Online Random Forests (2014, background): “incremental CART [5], ITI [23], VFDT [11] and dynamic trees [21], but to the best of our knowledge, these are focused on learning decision trees and have not been generalized to online random forests.”
Adaptive random forests for evolving data stream classification (2017, methodology): “3 GP was originally introduce in [23] as nmin, we use GP for consistency with the rest of our nomenclature.”
Time-series data mining (2012, positive): “Many models have already been extended to control data streams, such as clustering [Domingos and Hulten 2000], classi.cation [Hulten et al. 2001], segmentation [Keogh et al. 2003a], or anomaly detection [Chuah and Fu 2007].”
A Framework for Clustering Evolving Data Streams (2003, background): “The data stream problem has been extensively researched in recent years because of the large number of relevant applications [1, 3, 6, 8, 13].”
Consistency of Online Random Forests (2013, methodology): “Our algorithm makes use of a bounded fringe and adopts the technique of Domingos & Hulten (2000) to control the policy for adding and removing leafs from the fringe.”
Efficient decision tree construction on streaming data (2003, methodology): “The existing algorithms typically achieve either a deterministic bound on the accuracy [17], or a probabilistic bound [10].”