A fast incremental algorithm for deleting objects from a concept lattice

摘要

The formal context may not be fixed in a real-life application of formal concept analysis, which means that we have to update the present lattice or compute a new lattice from scratch. In this paper, we propose an efficient incremental algorithm, referred to as FastDeletion, to delete objects from a concept lattice. The algorithm improves two fundamental procedures shared by other algorithms. These two procedures include determining which concepts need to be deleted and fixing the covering relation. We describe the algorithm thoroughly, prove correctness of our improvements, discuss time complexity issues, and present an experimental evaluation of its performance and comparison with another algorithm. Empirical analyses demonstrate that our algorithm is superior when applied to various types of formal contexts.