1 Introduction Learning from very large and distributed databases imposes major performance challenges for data mining. Many databases have grown too large to fit into main memory. Learning a monolithic classifier will be very slow since it requires all data be held in main memory. Some databases are inherently distributed and cannot be brought into a single site for a variety of reasons. It is very hard to learn a single classifier under these constraints. One such application is to learn a fraud detection model from different participating credit card companies whose datasets are huge and strictly distributed. Yet there are some databases that have large amounts of new data available periodically or in real time. To re-learn a new model of the whole data set each time an increment is provided is both expensive and inefficient.