language: en

Scalability of Hierarchical Meta-Learning on Partitioned Data

Philip K. Chan
Computer Science Florida Institute of Technology
Melbourne, FL 32901
pkc@cs.fit.edu

[FAX: (407) 984-8461]

Salvatore J. Stolfo
Department of Computer Science Columbia University
New York, NY 10027
sal@cs.columbia.edu

[(212) 939-7080]

May 8, 1997

Abstract In this paper we study the issue of how to scale machine learning algorithms, that typically are designed to deal with main-memory based datasets, to efficiently learn models from large distributed databases. We have explored an approach called meta-learning that is related to the traditional approaches of data reduction commonly employed in distributed database query processing systems. We explore the scalability of learning arbiter and combiner trees from partitioned data. Arbiter and combiner trees integrate classifiers trained in parallel from small disjoint subsets. Previous work demonstrated the efficacy of these meta-learning architectures in terms of accuracy of the computed meta-classifiers. Here we discuss the computational performance of constructing arbiter and combiner trees in terms of speedup and scalability as a function of database size and number of partitions. The performance of serial learning algorithms is evaluated. We then analyze the performance of the algorithms used to construct combiner and arbiter trees in parallel. Our empirical results validate these analyses and indicate that the techniques can effectively scale up to large datasets with millions of records using cheap commodity hardware.

Keywords: speedup, scalability, arbiter and combiner trees, meta-learning, parallel/distributed processing, inductive learning

[This work was partially funded by grants from NSF (IRI-96-32225 & CDA-96-25374), ARPA (F30602 96-1-0311), and NYSSTF (423115-445).]