SPRINT: A Scalable Parallel Classifier for Data Mining
Published 3 September 1996
John Shafer, Rakesh Agrawal, Manish Mehta
Citations781
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new decision-tree-based classification algorithm, called SPRINT, is presented that removes all of the memory restrictions, and is fast and scalable, and designed to be easily parallelized, allowing many processors to work together to build a single consistent model.
Abstract
Classification is an important data mining problem. Although classification is a wellstudied problem, most of the current classification algorithms require that all or a portion of the the entire dataset remain permanently in memory. This limits their suitability for mining over large databases. We present a new decision-tree-based classification algorithm, called SPRINT that removes all of the memory restrictions, and is fast and scalable. The algorithm has also been designed to be easily parallelized, allowing many processors to work together to build a single consistent model. This parallelization, also presented here, exhibits excellent scalability as well. The combination of these characteristics makes the proposed algorithm an ideal tool for data mining. 1
Keywords
Computer Science
BiometricsClassification and Regression Trees.
23,841 Citations1984Alexander Gordon, Leo Breiman +3 more
C4.5: Programs for Machine Learning
23,665 Citations1992J. R. Quinlan
A complete guide to the C4.5 system as implemented in C for the UNIX environment, which starts from simple core learning methods and shows how they can be elaborated and extended to deal with typical problems such as missing data and over hitting.
Genetic Algorithms in Search, Optimization and Machine Learning
17,773 Citations1988David E. Goldberg, David Robson
Machine LearningInduction of Decision Trees
14,815 Citations1986J. R. Quinlan
This paper summarizes an approach to synthesizing decision trees that has been used in a variety of systems, and it describes one such system, ID3, in detail, which is described in detail.
IEEE ASSP MagazineAn introduction to computing with neural nets
7,858 Citations1987Richard P. Lippmann
Programs for Machine Learning
5,794 Citations1994Steven L. Salzberg, Alberto M. Segre
In his new book, C4.5: Programs for Machine Learning, Quinlan has put together a definitive, much needed description of his complete system, including the latest developments, which will be a welcome addition to the library of many researchers and students.
TechnometricsMachine Learning, Neural and Statistical Classification
2,188 Citations1995Bill Fulkerson, D. Michie +2 more
IEEE Transactions on Knowledge and Data EngineeringDatabase mining: a performance perspective
1,488 Citations1993R. K. Agrawal, Tomasz Imieliński +1 more
The authors' perspective of database mining as the confluence of machine learning techniques and the performance emphasis of database technology is presented and an algorithm for classification obtained by combining the basic rule discovery operations is given.
Computer systems that learn: classification and prediction methods from statistics, neural nets, machine learning, and expert systems
906 Citations1991Sholom M. Weiss, Casimir A. Kulikowski
This book discusses how to Estimate the True Performance of a Learning System, and the Importance of Unbiased Error Rate Estimation, and Machine Learning: Easily Understood Decision Rules.
Lecture notes in computer scienceSLIQ: A fast scalable classifier for data mining
753 Citations1996Manish Mehta, Rakesh Agrawal +1 more
Issues in building a scalable classifier are discussed and the design of SLIQ, a new classifier that uses a novel pre-sorting technique in the tree-growth phase to enable classification of disk-resident datasets is presented.
IEEE Transactions on Knowledge and Data EngineeringThe Gamma database machine project
667 Citations1990David J. DeWitt, Shahram Ghandeharizadeh +4 more
The design of the Gamma database machine and the techniques employed in its implementation are described and a thorough performance evaluation of the iPSC/s hypercube version of Gamma is presented.
An Interval Classifier for Database Mining Applications
266 Citations1992Rakesh Agrawal, Sakti P. Ghosh +3 more
Preliminary experimental results indicate that IC not only has retrieval and classi cation accuracy advantages, but also compares favorably with current tree classi ers, such as ID3, which were primarily designed for minimizing classiCation errors.
Experiments on multistrategy learning by meta-learning
147 Citations1993Philip K. Chan, Salvatore J. Stolfo
Meta-leaming is proposed as a general technique to combine the results of multiple learning algorithms, each applied to a set of training data, to improve overall prediction accuracy.
Parallel sorting on a shared-nothing architecture using probabilistic splitting
142 Citations2002David J. DeWitt, Jeffrey F. Naughton +1 more
The authors consider the problem of external sorting in a shared-nothing multiprocessor with two techniques for determining ranges of sort keys: exact splitting, using a parallel version of the algorithm proposed by Iyer, Ricard, and Varman; and probabilistic splitting, which uses sampling to estimate quantiles.
Elsevier eBooksExperiments on the Costs and Benefits of Windowing in ID3
52 Citations1988Jarryl Wirth, Jason Catlett
It is concluded that in noisy domains (where ID3 is now commonly used), windowing should be avoided, and the use of windowing considerably increased the CPU requirements of ID3 but produced no significant benefits.
Induction over large data bases
42 Citations1979J. R. Quinlan
Techniques for discovering rules by induction from large collections of instances are developed based on an iterative scheme for dividing the instances into two sets, only one of which needs to be randomly accessible.