Paper Info
Title
Evaluation of Different BDD Libraries to Extract Concepts in FCA --- Perspectives and Limitations
Abstract
This paper presents evaluation of different types of Binary Decision Diagrams (BDDs) applied to Formal Concept Analysis (FCA). The aim is to increase the FCA capability to handle large formal contexts and perform faster operations over different types of this data structure. The main idea is to represent formal context using BDDs for later extraction of the set of all formal concepts from this implicit representation. A comparison of a concept extraction algorithm using contexts implemented as table and BDD are presented. BDD is evaluated over two different implementation libraries, BuDDy and CUDD. A ZBDDs (Zero-Supressed BDDs) version of the concepts extraction algorithm is also provided. BDD has been evaluated based on several types of randomly generated synthetic contexts with large amounts of objects. Contexts are evaluated according to the computational time complexity required to build and extract the set of all concepts from it. In this work, it is shown that BDD could be used to deal with large formal contexts especially when those have few attributes and many objects. To overcome the limitations of having contexts with fewer attributes, one could consider vertical partitions of the context to be used with distributed FCA algorithms based on BDD.
Year
DOI
Venue
2009
10.1007/978-3-642-01970-8_36
ICCS (1)
Keywords
Field
DocType
large formal context,extract concepts,different implementation library,formal concept,concept extraction algorithm,large amount,formal context,different bdd libraries,fca capability,different type,concepts extraction algorithm,zero-supressed bdds,time complexity,binary decision diagram,formal concept analysis
Data structure,Extraction algorithm,Computer science,Binary decision diagram,Theoretical computer science,Concept extraction,Time complexity,Formal concept analysis
Conference
Volume
ISSN
Citations 
5544
0302-9743
0
PageRank 
References 
Authors
0.34
3
3
Name
Order
Citations
PageRank
Andrei Rimsa1131.98
Luis E. Zárate210725.52
Mark A. J. Song3108.68