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

Given a relation ?? ? ?? × ?? on a set ?? of objects and a set ?? 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.