On a data warehouse, either manual analyses supported by appropriate visualization tools or (semi-) automatic data mining may be performed, e.g. clustering, classification and summarization. Attribute-oriented generalization is a common method for the task of summarization. Typically, in a data warehouse update operations are collected and applied to the data warehouse periodically. Then, all derived information has to be updated as well. Due to the very large size of the base relations, it is highly desirable to perform these updates incrementally. In this paper, we present algorithms for incremental attribute-oriented generalization with the conflicting goals of good efficiency and minimal overly generalization. The algorithms for incremental insertions and deletions are based on the materialization of a relation at an intermediate generalization level, i.e. the anchor relation. Our experiments demonstrate that incremental generalization can be performed efficiently at a low degree of overly generalization. Furthermore, an optimal cardinality for the sets of updates can be determined experimentally yielding the best efficiency.