A Dynamic Adaptation of AD-trees for Efficient Machine Learning on Large Data Sets (2000)

Paul Komarek, Andrew Moore

Tags

AD-trees, Association Rules, Bayesian Networks, Cached Sufficient Statistics, Efficient Statistical Algorithms, Statistical Data Mining for Astrophysics

Abstract

This paper has no novel learning or statistics: it is concerned with making a wide class of pre-existing statistics and learning algorithms computationally tractable when faced with data sets with massive numbers of records or attributes.

It briefly reviews the static AD-tree structure of Moore and Lee (1998), and offers a new structure with more attractive properties:

1. the new structure scales better with the number of attributes in the data set;
2. it has zero initial build time;
3. it adaptively caches only statistics relevant to the current task; and
4. it can be used incrementally in cases where new data is frequently being appended to the data set.

We provide a careful explanation of the data structure, and then empirically evaluate the performance under varying access patterns induced by different learning algorithms such as association rules, decision trees and Bayes net structures.

We conclude by discussing the longer term benefits of the new structure: the eventual ability to apply AD-trees to data sets with real-valued attributes.

Full text

Download (application/pdf, 106.0 kB)

Approximate BibTeX Entry

@inproceedings{komarek-lazy,
    Year = {2000},
    Pages = {495--502},
    Booktitle = {Proceedings of the 17th International Conference on Machine Learning},
    Editor = {P. Langley},
    Author = { Paul Komarek, Andrew Moore },
    Title = {A Dynamic Adaptation of AD-trees for Efficient Machine Learning on Large Data Sets}
}