DocumentCode :
3717296
Title :
An efficient map-reduce algorithm for computing formal concepts from binary data
Author :
Raj Bhatnagar;Lalit Kumar
Author_Institution :
University of Cincinnati
fYear :
2015
Firstpage :
1519
Lastpage :
1528
Abstract :
The problem of discovering all formal concepts embedded in a binary relational dataset is of significant interest for many data analysis and processing problems. The problem of enumerating all concepts for a dataset is known to be NP-hard. A number of Map-Reduce based algorithms have been developed to conquer the difficulty of processing large datasets. But these algorithms are not very scalable because at core all these algorithms stick to a DFS based sequential search for individual concepts, applying Map-Reduce formalism to parallelize the processing at nodes of the DFS tree. We have present here a completely different and Map-Reduce based formulation for parallelizing the concept discovery problem. One major difference of our approach is that we seek to find a sufficient set of concepts only, and this sufficient set can be used to generate all other concepts in the lattice. This formulation is not very suitable for sequential execution but adapts extremely well to the parallel environments based on Map-Reduce operators. We show in this paper that our algorithm is significantly faster than all the known Map-reduce formulations for discovering concepts in binary relational datasets. We have presented in this paper the outline of the theoretical foundations for our algorithm and empirical tests with a number of benchmarking datasets. We also show that the computationally very difficult problem of finding 3-clusters in pairs of binary relational datasets can also be made very efficient by our formulation.
Keywords :
"Context","Algorithm design and analysis","Yttrium","Itemsets","Vocabulary","Lattices","Formal concept analysis"
Publisher :
ieee
Conference_Titel :
Big Data (Big Data), 2015 IEEE International Conference on
Type :
conf
DOI :
10.1109/BigData.2015.7363915
Filename :
7363915
Link To Document :
بازگشت