Study On GPU-based Union Algorithm Of Concept Lattices

Concept lattices theory, also called formal concept analysis (FCA), is an effectivetool to used in knowledge representation and knowledge discovery, has beensuccessfully used in knowledge engineering, machine learning, information retrieval,data mining, semantic Web, software engineering, many the field. To analyze the datausing concept lattice theory, we must first build the data corresponding concept latticein which the key issue is the efficiency of the algorithm to build cells, and an effectivemethod to improve the efficiency of the algorithm is parallel computing.With the development of hardware graphics processing technology, GPU’s abilityhas a great progress, and it begin to be used as a general-purpose computing unit.Relative to the CPU, GPU parallelism with higher and lower cost, which makes theparallel GPU-based parallel computing technology will soon become the hot area ofresearch.This paper studies the status of paper of building lattice algorithm at home andabroad, compared to Batch and incremental construction of concept lattice algorithm,combined with today’s parallel GPU general computing advantages, proposed theGPU-based merger algorithm of concept lattices.The algorithm is implemented on theGPU,the main idea of it is concept lattices merger. Firstly, Algorithm forms thebackground of redundant processing, exclude the complex data those who do not needto determine (objects or property); then reasonably split the formal context by itsstorage order of the objects or the attributs; Next, using GPU multi-threadingmechanism for building lattice for sub-context, where construction algorithm tosub-context is also based on the combined thinking of the concept lattice (verticalintegration); Finally, parallel-horizontaly mergering concept lattice generated by thesub contexts to get the original concept lattice corresponding the orginal formalcontext.Experimental results show that the algrothim improves the efficiency of thebuilding lattice under a certain size of data, thus the algorithm is effective.The article also proposed algorithm can be optimized in several aspects, includingforms and dynamic load balancing into the background and so on.