A lattice-free concept lattice update algorithm

Abstract

Upon a change of input data, one usually wants an update of output computed from the data rather than recomputing the whole output over again. In Formal Concept Analysis, update of concept lattice of input data when introducing new objects to the data can be done by any of the so-called incremental algorithms for computing concept lattice. The algorithms use and update the lattice while introducing new objects to input data one by one. The present concept lattice of input data without the new objects is thus required by the computation. However, the lattice can be large and may not fit into memory. In this paper, we propose an efficient algorithm for updating the lattice from the present and new objects only, not requiring the possibly large concept lattice of present objects. The algorithm results as a modification of the Close-by-One algorithm for computing the set of all formal concepts, or its modifications like Fast Close-by-One, Parallel Close-by-One or Parallel Fast Close-by-One, to compute new and modified formal concepts and the changes of the lattice order relation only. The algorithm can be used not only for updating the lattice when new objects are introduced but also when some existing objects are removed from the input data or attributes of the objects are changed. We describe the algorithm, discuss efficiency issues and present an experimental evaluation of its performance and a comparison with the AddIntent incremental algorithm for computing concept lattice.

Keywords:

• Concept lattice
• update algorithm
• formal concepts

Notes

No potential conflict of interest was reported by the author.

This paper is a revised and extended version of the paper presented at the CLA 2013 conference and included in the proceedings. The algorithms for computing concept lattice and its update were substantially redesigned and improved, a pseudocode of the latter, which was not included in the conference paper, was added, and the experimental evaluation was extended (more benchmark data-sets, memory usage).

Additional information

Funding

This work was supported by the European Social Fund and the state budget of the Czech Republic, under ESF [Project No. CZ.1.07/2.3.00/20.0059].