Minimal generators, an affordable approach by means of massive computation

 

Abstract

Closed sets and minimal generators are fundamental elements to build a complete knowledge representation in formal concept analysis. The enumeration of all the closed sets and their minimal generators from a set of rules or implications constitutes a complex problem, drawing an exponential cost. Even for small datasets, such representation can demand an exhaustive management of the information stored as attribute implications. In this work, we tackle this problem by merging two strategies. On the one hand, we design a pruning, strongly based on logic properties, to drastically reduce the search space of the method. On the other hand, we consider a parallelization of the problem leading to a massive computation by means of a map-reduce like paradigm. In this study we have characterized the type of search space reductions suitable for parallelization. Also, we have analyzed different situations to provide an orientation of the resources (number of cores) needed for both the parallel architecture and the size of the problem in the splitting stage to take advantage in the map stage.

Citation

Please, cite this work as:

[Ben+19] F. Benito-Picazo, P. Cordero, M. Enciso, et al. “Minimal generators, an affordable approach by means of massive computation”. In: The Journal of Supercomputing 75.3 (Mar. 2019), pp. 1350-1367. ISSN: 1573-0484. DOI: 10.1007/s11227-018-2453-z. URL: https://doi.org/10.1007/s11227-018-2453-z.

BibTeX

@Article{Benito-Picazo2019,
    author={Benito-Picazo, F.
    and Cordero, P.
    and Enciso, M.
    and Mora, A.},
    title={Minimal generators, an affordable approach by means of massive computation},
    journal={The Journal of Supercomputing},
    year={2019},
    month={Mar},
    day={01},
    volume={75},
    number={3},
    pages={1350-1367},
    abstract={Closed sets and minimal generators are fundamental elements to build a complete knowledge representation in formal concept analysis. The enumeration of all the closed sets and their minimal generators from a set of rules or implications constitutes a complex problem, drawing an exponential cost. Even for small datasets, such representation can demand an exhaustive management of the information stored as attribute implications. In this work, we tackle this problem by merging two strategies. On the one hand, we design a pruning, strongly based on logic properties, to drastically reduce the search space of the method. On the other hand, we consider a parallelization of the problem leading to a massive computation by means of a map-reduce like paradigm. In this study we have characterized the type of search space reductions suitable for parallelization. Also, we have analyzed different situations to provide an orientation of the resources (number of cores) needed for both the parallel architecture and the size of the problem in the splitting stage to take advantage in the map stage.},
    issn={1573-0484},
    doi={10.1007/s11227-018-2453-z},
    url={https://doi.org/10.1007/s11227-018-2453-z}
}

Bibliometric data

The following data has been extracted from resources such as OpenAlex, Dimensions, PlumX or Altmetric.

5

CITATIONS

5 Total citations

0 Recent citations

1.16 Field Citation Ratio

n/a Relative Citation Ratio

• Citations
• CrossRef - Citation Indexes: 1
• Scopus - Citation Indexes: 7

• Captures
• Mendeley - Readers: 12

-

see details

Cites

The following graph plots the number of cites received by this work from its publication, on a yearly basis.

Papers citing this work

The following is a non-exhaustive list of papers that cite this work:

[1] P. Cordero, M. Enciso, A. Mora, et al. “Interactive Search by Using Minimal Generators”. In: Computational Intelligence and Mathematics for Tackling Complex Problems 2. Springer International Publishing, 2022, p. 147–153. ISBN: 9783030888176. DOI: 10.1007/978-3-030-88817-6_17. URL: http://dx.doi.org/10.1007/978-3-030-88817-6_17.

[2] P. Cordero, M. Enciso, Á. Mora, et al. “A Formal Concept Analysis Approach to Cooperative Conversational Recommendation”. In: International Journal of Computational Intelligence Systems 13.1 (2020), p. 1243. ISSN: 1875-6883. DOI: 10.2991/ijcis.d.200806.001. URL: http://dx.doi.org/10.2991/ijcis.d.200806.001.

[3] P. Cordero, M. Enciso, A. Mora, et al. “Parameterized simplification logic I: reasoning with implications and classes of closure operators”. In: International Journal of General Systems 49.7 (Oct. 2020), p. 724–746. ISSN: 1563-5104. DOI: 10.1080/03081079.2020.1831484. URL: http://dx.doi.org/10.1080/03081079.2020.1831484.

[4] D. López-Rodríguez, E. Muñoz-Velasco, and M. Ojeda-Aciego. “Formal Methods in FCA and Big Data”. In: Complex Data Analytics with Formal Concept Analysis. Springer International Publishing, Dec. 2021, p. 201–224. ISBN: 9783030932787. DOI: 10.1007/978-3-030-93278-7_9. URL: http://dx.doi.org/10.1007/978-3-030-93278-7_9.

[5] M. Ojeda-Hernández, I. P. Cabrera, and P. Cordero. “Quasi-closed elements in fuzzy posets”. In: Journal of Computational and Applied Mathematics 404 (Apr. 2022), p. 113390. ISSN: 0377-0427. DOI: 10.1016/j.cam.2021.113390. URL: http://dx.doi.org/10.1016/j.cam.2021.113390.

[6] T. Pattison, M. Enciso, Á. Mora, et al. “Scalable Visual Analytics in FCA”. In: Complex Data Analytics with Formal Concept Analysis. Springer International Publishing, Dec. 2021, p. 167–200. ISBN: 9783030932787. DOI: 10.1007/978-3-030-93278-7_8. URL: http://dx.doi.org/10.1007/978-3-030-93278-7_8.