We present GDBR (Generalize DataBase Relation) and FIGR (Fast, Incremental Generalization and Regeneralization), two enhancements of Attribute Oriented Generalization, a well known knowledge discovery from databases technique. GDBR and FIGR are both O(n) and, as such, are optimal. GDBR is an online algorithm and requires only a small, constant amount of space. FIGR also requires a constant amount of space that is generally reasonable, although under certain circumstances, may grow large. FIGR is incremental, allowing changes to the database to be reflected in the generalization results without rereading input data. FIGR also allows fast regeneralization to both higher and lower levels of generality without rereading input. We compare GDBR and FIGR to two previous algorithms, LCHR and AOI, which are O(n log n) and O(np), respectively, where n is the number of input tuples and p the number of tuples in the generalized relation. Both require O(n) space that, for large input, causes memory problems. We implemented all four algorithms and ran empirical tests, and we found that GDBR and FIGR are faster. In addition, their runtimes increase only linearly as input size increases, while the runtimes of LCHR and AOI increase greatly when input size exceeds memory limitations.

Practical tools for knowledge discovery from databases must be efficient enough to handle large data sets found in commercial environments. Attribute-oriented induction has proved to be a useful method for knowledge discovery. Three algorithms are AOI, LCHR and GDBR. We have implemented efficient versions of each algorithm and empirically compared them on large commercial data sets. These tests show that GDBR is consistently faster than AOI and LCHR. GDBR's times increase linearly with increased input size, while times for AOI and LCHR increase non-linearly when memory is exceeded. Through better memory management, however, AOI can be improved to provide some advantages.