On pruning techniques in map-reduce style CbO algorithms

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

On pruning techniques in map-reduce style CbO algorithms

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

On pruning techniques in map-reduce style CbO algorithms

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2022

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE

ISSN

1012-2443

e-ISSN

1573-7470

Svazek periodika

90

Číslo periodika v rámci svazku

11-12

Stát vydavatele periodika

CH - Švýcarská konfederace

Počet stran výsledku

18

Strana od-do

1107-1124

Kód UT WoS článku

000750326500001

EID výsledku v databázi Scopus

2-s2.0-85123959409