Complexity aspects of multi-machine aggregations in a rough-granular computation framework

We investigate computational complexity of a task of optimizing multi-machine execution of analytical data processing operations. We concentrate on an example of aggregation queries in Infobright´s database engine, which is designed using the paradigms of rough sets and granular computing. The task is to optimize decomposition of data blocks and aggregation groups among machines having access to a shared data storage. The paper includes some examples of optimization functions and constraints, as well as the proof of NP-hardness of the considered task for some of them. It can be treated as a guideline for developing scalable data processing and mining methods based on massive parallelism and approximate computing.