Details

Autor(en) / Beteiligte

• Berry, Anne
• Gutierrez, Alain
• Huchard, Marianne
• Napoli, Amedeo
• Sigayret, Alain

Titel

Hermes: a simple and efficient algorithm for building the AOC-poset of a binary relation

Ist Teil von

• Annals of mathematics and artificial intelligence, 2014-10, Vol.72 (1-2), p.45-71

Ort / Verlag

Cham: Springer International Publishing

Erscheinungsjahr

2014

Link zum Volltext

Quelle

SpringerLink

Beschreibungen/Notizen

• Given a relation R ⊆ O × A on a set O of objects and a set A of attributes, the AOC-poset (Attribute/Object Concept poset), is the partial order defined on the “introducers” of objects and attributes in the corresponding concept lattice. In this paper, we present Hermes , a simple and efficient algorithm for building an AOC-poset which runs in O ( m i n { n m , n α }), where n is the number of objects plus the number of attributes, m is the size of the relation, and n α is the time required to perform matrix multiplication (currently α = 2.376). Finally, we compare the runtime of Hermes with the runtime of other algorithms computing the AOC-poset: Ares , Ceres and Pluton . We characterize the cases where each algorithm is the more relevant.