Hermes: a simple and efficient algorithm for building the AOC-poset of a binary relation |
| |
Authors: | Anne Berry Alain Gutierrez Marianne Huchard Amedeo Napoli Alain Sigayret |
| |
Affiliation: | 1. LIMOS (CNRS UMR 6158 - Université Clermont-Ferrand II), Clermont-Ferrand, France 2. LIRMM (CNRS UMR 5506 – Université de Montpellier II), Montpellier, France 3. LORIA (CNRS UMR 7503 – Inria Nancy Grand Est – Université de Lorraine), Vandoeuvre-lès-Nancy, France
|
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|