Incrementally Maintaining Classification Using an RDBMS

The proliferation of imprecise data has motivated both researchers and the database industry to push statistical techniques into Relational DataBase Management Systems (RDBMSes). The authors study strategies to maintain model-based views for a popular statistical technique, classification, inside an RDBMS in the presence of updates (to the set of training examples). They make three technical contributions: A strategy that incrementally maintains classification inside an RDBMS. An analysis of the above algorithm that shows that the algorithm is optimal among all deterministic algorithms (and asymptotically within a factor of 2 of a non-deterministic optimal strategy). A novel hybrid architecture based on the technical ideas that underlie the above algorithm which allows one to store only a fraction of the entities in memory.