A fast, on-line generalization algorithm for knowledge discovery Original Research Article

We present an O(n) algorithm for generalizing a database relation using concept hierarchies, where n is the number of tuples in the input relation. The algorithm is based on a variant of Han et al.ʹs attribute-oriented O(n log n) algorithm. Our algorithm is an on-line algorithm; fast performance is achieved because after encountering a tuple and generalizing it, the location of the appropriate counter to increment is calculated instead of searched for.