The paper is devoted to association rules mining using BOINC{ project based on Enterprise Desktop Grid. A high-level algorithm description is given. A BOINC{based application is developed and validated. Several experiments with the aim of performance evaluation are performed. Ways to further develop the approach are described. Association rules mining is one of the Data Mining methods aimed to data analysis. This method is a well-studied area, because of its importance in many problems of data analysis. Association rules express the association between records in a transactional database. The problem of discovering frequent itemsets in a transactional data set (the so called FIM problem) is the rst step of association rules mining. A number of algorithms have been suggested to discover frequent itemsets: Apriori [7], FP-Growth [8], Eclat [9], and others. The Berkeley Open Infrastructure for Network Computing (BOINC) is an open source software framework for distributed and grid computing [1]. BOINC is based on the client/server model. A central server has project's database storing information about registered users and associated hosts, applications, tasks and results of calculations as well as other information. Also there are special services on the central server: { Work generator which generates new workunits and corresponding input les. { Feeder is used to enhance the performance scheduler and to reduce a number of queries to the database of project. { Scheduler which assigns jobs to a client taking into account its characteristics. { Transitioner handles state transitions of workunits and results.
{ Validator which decides (following the special procedure) whether results are correct. { Assimilator which periodically checks the completed jobs and processes results according to application-speci c rules. { File deleter deletes input and output les as jobs are completed. { Database purger writes result and workunit records to XML-format archive les, then deletes them from the database.
Ordinary BOINC{project should be computational intensive instead of data
intensive because of poor connection between BOINC server and its clients.
Our research is based on Enterprise Desktop Grid to work with data-intensive
applications with speed of local-area networks. The performance of Enterprise
Desktop Grid also can be improved by advanced scheduling [
The appropriate adaptation of the software is required to use an Enterprise Desktop Grid for data processing. The software uses the BOINC API to implement interaction between a BOINC server, client and running application.
This paper presents the native BOINC-based application for mining association rules in big data sets based on Enterprise Desktop Grid. The performance evaluation experiments are performed; the directions of the future work are discussed. 2
Association rule is an implication X ! Y , where X and Y are (not large) data sets. Such a rule has two important characteristics: support (s) and con dence (c) of the rule. The association X ! Y means that if a transaction contains data set X then it also contains data set Y ; there are s% of transactions in the database containing both X and Y ; there are c% of all transactions that contain X also contain Y .
A modi cation of Partition algorithm is used to solve the problem of nding
frequent itemsets in large volumes of data. Partition itself is a parallel modi
cation of a well-known Apriori algorithm, it has good scalability and performance.
The description of the algorithm can be found in paper [
The algorithm requires two scans of the initial database and six steps [
Several experiments with the aim of validation and performance evaluation of the Partition algorithm implementation were performed. We used a BOINCbased Enterprise Desktop Grid with up to 32 computing nodes connected to BOINC-server by local area network.
First of all, we validated the application by test source datasets from the
Frequent Itemset Mining Dataset Repository (FIMDR) [
However, because of data-intensive nature of the project BOINC's overhead is very large comparing with ordinary compute intensive applications (see Fig. 2 to compare overheads association rules mining and SETI@HOME projects). The main performance limitation in the performed experiments is still the network bandwidth. BOINC-server should distribute a database between computing nodes that becomes a very time-consuming operation. Nevertheless use of Enterprise Desktop Grid (and a local-area network) allows to improve the speed of data analysis. 4
BOINC is a popular tool to perform large-scale computational experiments. BOINC-based Enterprise Desktop Grid allows to small and medium companies or small scienti c groups to solve their private problems using their own computing resources. One of such private problems is analysis of big datasets of an organization.
This study shows the way to extract association rules from big data sets using BOINC-based Enterprise Desktop Grid. We adapted the Partition algorithm for BOINC and performed the experiments on performance evaluation of association rules extraction. Our results show that Enterprise Desktop Grid allows to reduce expended time for data analysis.
There are also several ways to overcome a limitation of the network bandwidth. For example, the Partition algorithm can be adapted to process data at the point of gathering these data, i.e. POS-terminal of a supermarket can analyse a market basket together with other POS-terminals without gathering their data. This removes the need to transfer a source database through a network. There are also some more workarounds to the problem of limitation the network bandwidth.
Also BOINC can be much more useful in case of searching the optimal values of minimal support. In this case one have to perform data analysis multiple times (using di erent values of minimal support) with the same data. So, the overhead will be reduced comparing with computations.
Further development of the study will be devoted to adapting other methods of data analysis to BOINC-environment. Also it is important to combine the developed tool with special visualization software.