A lattice-free concept lattice update algorithm. Issue 2 (17th February 2016)

• Record Type: Journal Article
• Authors: Outrata, Jan
• Is Part Of: International journal of general systems. Volume 45:Issue 2(2016)
• Page Start: 211
• Page End: 231
• Publication Date: 2016-02-17
• Subjects: Concept lattice -- update algorithm -- formal concepts; System theory -- Periodicals; 003
• DOI: 10.1080/03081079.2015.1072928
• Languages: English
• ISSNs: 0308-1079

Abstract

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.