A lattice-free concept lattice update algorithm
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989592%3A15310%2F16%3A33160380" target="_blank" >RIV/61989592:15310/16:33160380 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1080/03081079.2015.1072928" target="_blank" >http://dx.doi.org/10.1080/03081079.2015.1072928</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1080/03081079.2015.1072928" target="_blank" >10.1080/03081079.2015.1072928</a>
Alternative languages
Result language
angličtina
Original language name
A lattice-free concept lattice update algorithm
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/EE2.3.20.0059" target="_blank" >EE2.3.20.0059: Reintegration of Czech Scientist and Creation of Top Level Team in Information Sciences</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
International Journal of General Systems
ISSN
0308-1079
e-ISSN
—
Volume of the periodical
45
Issue of the periodical within the volume
2
Country of publishing house
GB - UNITED KINGDOM
Number of pages
21
Pages from-to
211-231
UT code for WoS article
000372036100008
EID of the result in the Scopus database
2-s2.0-84960273273