A localized algorithm for parallel association mining
Mohammed Javeed Zaki, Srinivasan Parthasarathy, Wei Li · 1997
Discovery of association rules is an important database mining problem.Mining forassociation nrlesinvolves extracting patterns from large databases and inferring useful rules from them.Several parallel arsd sequential algorithms have been proposed in the literature tosolve this problem.Almost all of these algorithms make repeated passes over thedatabase todetennine the commonly occurring patterns oritemsets (set ofitems), thus incurnnghigh I/O overhead.Intheparallel case, these algorithms do a reduction at the end of each pass to construct the global patterns, thus incurnng high synchronization cost,In this paper we describes new parallel association reining algorithm, Our algorithm is a result of detailed study of the available parallelism and the properties of associations.The algorithm usesa scheme to cluster related frequent itemsets together, and to partition them among the processors, At the same time it also uses a different database layout which clusters related transactions together, and selectively replicates the database so that theportion of thedatabase needed for the computation of associations is local to each processor.After the initial set-up phase, the algorithm eliminates the need for further communication or synchronization, 'rlrealgorit hmfurtherscanst helocal database partition only three times, thus minimizing I/O overheads.Urdikeprevious approaches, thealgorithms uses simple intersection operations to compute frequent item sets and doesn 't have to maintain or search complex hash structures.Our experimental testbed is a 32-processor DEC Alpha clusterinter-connected bythe Memory Channel network.Wepresent results on the performance of our algorithm on various databases, andcompare itagainst awellknown parallel algorithm, Ouralgorithm outperforms it by an more than an order of magnitude.Award (CCR-9409 120) and ARPA contract F19628-94-C-O057.Pemlissiotl 10 moke digilal/h2rd copies ot':111 or pflll 01'[111s nullcn;ll Iilr pwwnnl or classroom ust is grnnled \Yilhool lit pro\,idcd 11101 (he wspics are noI m:ide or dis[ritw led I'01 proli[ or comnterci; i] odwm(agc, Ilw cop\lright notice, the title oftlm pul?lico[lon Jml IIS d;LIC I , ppmr.:md nolic~s i.\ given tlvsl cqyiglll is hy pem)wion ot'lhe .i~il.Inc. "1"0 tq)y oll)er\vis.2, 10 reptthlisll.10 post on wrvcrs or 10 rcdlstrihu(c 10 lisw.rctltlirm spccilic permission and/or fee .V'AA 97 Ne\vpwr,Rhode [S1;1111{ [ :$/4 ~opyrigl)t 1997 ACM 0.89791 -X9(J-W97/06 ,.$'3.50