Fast incremental algorithm for building concept lattice

Abstract

To incrementally update the existing concept lattice with the inserted new object, this paper first identifies the basic problems to solve, through analyzing the process of incremental updating. Then, tree structure is employed to organize the set of concepts in concept lattice. Based on the tree structure, a fast incremental algorithm is developed to incrementally update the existing concept lattice by traversing its set of concepts with the defined visiting order. On visiting each concept node, the node type will be identified and the corresponding updating operation will be executed. The organization of concepts in tree structure and the defined visiting order on it can greatly reduce the search space of parents and children of newborn concept node and help to identify the node type, and consequently improve the speed of the algorithm. In the end, experimental results on artificially generated datasets are produced, which manifest that the algorithm in this paper runs much faster than the famous Godin's algorithm.