Hermes: an efficient algorithm for building Galois sub-hierarchies

Anne Berry 1 Marianne Huchard 2 Amedeo Napoli 3 Alain Sigayret 1
2 MAREL - Models And Reuse Engineering, Languages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 ORPAILLEUR - Knowledge representation, reasonning
Inria Nancy - Grand Est, LORIA - NLPKD - Department of Natural Language Processing & Knowledge Discovery
Abstract : Given a binary relation R on a set O of objects and a set A of attributes, the Galois sub-hierarchy (also called AOC-poset) is the partial order on the introducers of objects and attributes in the corresponding concept lattice. We present a new efficient algorithm for building a Galois sub-hierarchy which runs in O(min{nm, n ^{\alpha}}), where n is the number of objects or attributes, m is the size of the relation, and n ^{\alpha} is the time required to perform matrix multiplication (currently \alpha = 2.376).
Document type :
Conference papers
Complete list of metadatas

Cited literature [23 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00743882
Contributor : Marianne Huchard <>
Submitted on : Sunday, October 21, 2012 - 3:52:56 PM
Last modification on : Wednesday, April 3, 2019 - 1:22:57 AM
Long-term archiving on : Tuesday, January 22, 2013 - 3:39:06 AM

File

paperAnneBerry.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : lirmm-00743882, version 1

Citation

Anne Berry, Marianne Huchard, Amedeo Napoli, Alain Sigayret. Hermes: an efficient algorithm for building Galois sub-hierarchies. CLA: Concept Lattices and their Applications, Oct 2012, Fuengirola, Málaga, Spain. pp.21-32. ⟨lirmm-00743882⟩

Share

Metrics

Record views

1280

Files downloads

595