On pruning techniques in map-reduce style CbO algorithms
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989592%3A15310%2F22%3A73615097" target="_blank" >RIV/61989592:15310/22:73615097 - isvavai.cz</a>
Result on the web
<a href="https://link.springer.com/article/10.1007/s10472-022-09787-1" target="_blank" >https://link.springer.com/article/10.1007/s10472-022-09787-1</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s10472-022-09787-1" target="_blank" >10.1007/s10472-022-09787-1</a>
Alternative languages
Result language
angličtina
Original language name
On pruning techniques in map-reduce style CbO algorithms
Original language description
A fundamental task in formal concept analysis is the enumeration of formal concepts. Among the fastest algorithms for this task belong algorithms which are based on Close-by-One (CbO), a tree recursive algorithm using lexicographical order of formal concepts to ensure that each formal concept is enumerated exactly once. State-of-the-art algorithms based on CbO, e.g. FCbO, In-Close4, and In-Close5, employ several techniques, which we call pruning, to avoid some unnecessary computations. However, the number of the formal concepts can be exponential w.r.t. dimension of the input data. Therefore, the algorithms do not scale well and large datasets become intractable. To resolve this weakness, several parallel and distributed algorithms were proposed. We propose four new CbO-based algorithms intended for Apache Spark or a similar programming model and show how the pruning can be incorporated into them. We experimentally evaluate the impact of the pruning and demonstrate the scalability of the new algorithms.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2022
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
ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE
ISSN
1012-2443
e-ISSN
1573-7470
Volume of the periodical
90
Issue of the periodical within the volume
11-12
Country of publishing house
CH - SWITZERLAND
Number of pages
18
Pages from-to
1107-1124
UT code for WoS article
000750326500001
EID of the result in the Scopus database
2-s2.0-85123959409