A Dynamic Load Balancing Scheme for Distributed Formal Concept Analysis

摘要

Formal Concept Analysis (FCA) finds applications in several areas including data mining, artificial intelligence, and software engineering. FCA algorithms are computationally expensive and their recursion tree has an irregular structure. Several parallel algorithms have been implemented to manage the computational complexity of FCA. Most of them assume a shared memory environment where they maintain a shared queue of computational tasks and the workers store and retrieve tasks from that queue. Although the shared queue approach addresses the computation skew by fine grained sharing, it causes communication bottlenecks in a distributed memory environment. In this work, we propose static and dynamic load balancing strategies that are applicable in distributed memory environment. We parallelize the FCA algorithm called Linear time Closed itemset Miner and show that the proposed load balancing strategies effectively deal with the computation skew. They not only distribute the load evenly among the workers but also minimize the communication overhead.