Distributed formal concept analysis algorithms based on an iterative MapReduce framework

Biao Xu, Ruairí De Fréin, Eric Robson, Mícheál Ó Foghlú

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

31 Citations (Scopus)

Abstract

While many existing formal concept analysis algorithms are efficient, they are typically unsuitable for distributed implementation. Taking the MapReduce (MR) framework as our inspiration we introduce a distributed approach for performing formal concept mining. Our method has its novelty in that we use a light-weight MapReduce runtime called Twister which is better suited to iterative algorithms than recent distributed approaches. First, we describe the theoretical foundations underpinning our distributed formal concept analysis approach. Second, we provide a representative exemplar of how a classic centralized algorithm can be implemented in a distributed fashion using our methodology: we modify Ganter's classic algorithm by introducing a family of algorithms, namely MRGanter and MRGanter+ where the prefix denotes the algorithm's lineage. To evaluate the factors that impact distributed algorithm performance, we compare our algorithms with the state-of-the-art. Experiments conducted on real datasets demonstrate that MRGanter+ is efficient, scalable and an appealing algorithm for distributed problems.

Original languageEnglish
Title of host publicationFormal Concept Analysis - 10th International Conference, ICFCA 2012, Proceedings
PublisherSpringer
Pages292-308
Number of pages17
Volume10
ISBN (Print)9783642298912
DOIs
Publication statusPublished - 2012
Event10th International Conference on Formal Concept Analysis, ICFCA 2012 - Leuven, Belgium
Duration: 07 May 201210 May 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7278 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th International Conference on Formal Concept Analysis, ICFCA 2012
Country/TerritoryBelgium
CityLeuven
Period07/05/201210/05/2012

Keywords

  • Distributed Mining
  • Formal Concept Analysis
  • MapReduce

Fingerprint

Dive into the research topics of 'Distributed formal concept analysis algorithms based on an iterative MapReduce framework'. Together they form a unique fingerprint.

Cite this