online read us now
Paper details
Number 4 - December 2018
Volume 28 - 2018
Optimization on the complementation procedure towards efficient implementation of the index generation function
Grzegorz Borowik
Abstract
In the era of big data, solutions are desired that would be capable of efficient data reduction. This paper presents a summary
of research on an algorithm for complementation of a Boolean function which is fundamental for logic synthesis and data
mining. Successively, the existing problems and their proposed solutions are examined, including the analysis of current
implementations of the algorithm. Then, methods to speed up the computation process and efficient parallel implementation
of the algorithm are shown; they include optimization of data representation, recursive decomposition, merging, and
removal of redundant data. Besides the discussion of computational complexity, the paper compares the processing times
of the proposed solution with those for the well-known analysis and data mining systems. Although the presented idea is
focused on searching for all possible solutions, it can be restricted to finding just those of the smallest size. Both approaches
are of great application potential, including proving mathematical theorems, logic synthesis, especially index generation
functions, or data processing and mining such as feature selection, data discretization, rule generation, etc. The problem
considered is NP-hard, and it is easy to point to examples that are not solvable within the expected amount of time. However,
the solution allows the barrier of computations to be moved one step further. For example, the unique algorithm can
calculate, as the only one at the moment, all minimal sets of features for few standard benchmarks. Unlike many existing
methods, the algorithm additionally works with undetermined values. The result of this research is an easily extendable
experimental software that is the fastest among the tested solutions and the data mining systems.
Keywords
data reduction, feature selection, indiscernibility matrix, logic synthesis, index generation function