AOC-poset algorithms

The AOC-poset (or pruned concept hierarchy, or Galois Sub-hierarchy) is the sub-order of the concept lattice restricted to Attribute-Concepts (highest concept introducing an attribute) and Object-Concepts (lowest concept introducing an object).

There are currently 4 published algorithms for building the AOC-poset:

Ares (incremental)
Ceres
Pluton
Hermes

Results

Below are the results of the comparisons between the algorithms implemented in Java:

On randomly generated binary relations (uniform distribution)

Varying the object number (bitset implementation)
Varying the attribute number (bitset implementation)
Varying the object number (bitset, hashset and Trove_hashset implementations)
Square relations
Low density square relations (to compare with real cases)

On a few real binary relations

Datasets

Randomly generated datasets and ArgoUML based datasets are available HERE.
Tables from Konect:

slashdot-threads 2940x2928 d=0.0035
opsahl-collaboration 16727x22016 d=0.000591
ca-AstroPh 35545x37541 d=0.000281
opsahl-openflights 2940x2928 d=0.00354
dblp-cite 12589x12124 d=0.000154
lasagne-spanishbook 12644x9834
opsahl-ucforum 900x523 d=0.015
sociopatterns-infectious 408x411 d=0.0164

Tool

Download the AOC-poset builder tool

Terminology

Inheritance Knowledge space. Godin and Mili 1993. Robert Godin, Hafedh Mili, Building and maintaining analysis-level class hierarchies using Galois Lattices, Proceeding of OOPSLA '93, ACM SIGPLAN Notices, Volume 28 Issue 10, Oct. 1, 1993, pp. 394 - 410

Pruned concept hierarchy. Godin et al 1998. Robert Godin, Hafedh Mili, Guy W. Mineau, Rokia Missaoui, Amina Arfi, Thuy-Tien Chau. Design of Class Hierarchies Based on Concept (Galois) Lattices. TAPOS 4(2): 117-134 (1998)

Galois Sub-hierarchy. Dicky et al 1995. Hervé Dicky, Christophe Dony, Marianne Huchard, and Thérèse Libourel. ARES, Adding a class and REStructuring Inheritance Hierarchies. in Proc. of Bases de Données avancées (BDA’95), pages 25–42, 1995.

AOC-poset. Osswald and Petersen, 2001/2003. Rainer Osswald, Wiebke Petersen. Logical Approach to Data-Driven Classification. In Proc. of KI 2003: Advances in Artificial Intelligence, 26th Annual German Conference on AI. Lecture Notes in Computer Science 2821, pp 267-281, Springer.

References

Ares. Hervé Dicky, Christophe Dony, Marianne Huchard, and Thérèse Libourel. ARES, Adding a class and REStructuring Inheritance Hierarchies. in Proc. of Bases de Données avancées (BDA’95), pages 25–42, 1995. paper

Ceres. Hervé Leblanc, Sous-hiérarchies de Galois : un modèle pour la construction et l'évolution des hiérarchies d'objets. Thèse de doctorat de l'Université Montpellier 2. 2000. thesis (french) The algorithm is also outlined in a previous comparative study. draft.

Pluton. Anne Berry, Marianne Huchard, Ross M. McConnell, Alain Sigayret, and Jeremy Spinrad. Efficiently Computing a Linear Extension of the Sub-hierarchy of a Concept Lattice. In Int. Conf. on Formal Concept Analysis (ICFCA 2005), volume 3403 of Lecture Notes in Computer Science, pages 208–222. Springer, 2005. draft

Hermes. Anne Berry, Marianne Huchard, Amedeo Napoli, Alain Sigayret Hermes: an efficient algorithm for building Galois sub-hierarchies in Proc. of Concept Lattices and Their Applications (CLA 2012). pp. 21-32. Université de Malaga. paper