Publication - A Parallel Algorithm for Computing Borders

Envoyer
Publications

A Parallel Algorithm for Computing Borders

Auteurs : Hanusse Nicolas, Maabout Sofian

Conf : 20th Conference on Information and Knowledge Management (CIKM?11) 24-28 octobre,Glasgow, Ecosse (2011)

Web : http://dl.acm.org/citation.cfm?doid=2063576.2063814

The border concept has been introduced by Mannila and Toivonen in their seminal paper [20]. This concept finds many applications, e.g maximal frequent itemsets, minimal functional dependencies, emerging patterns between consecutive database instances and materialized view selection. For large transactions and relational databases defined on n items or attributes, the running time of any border computations are mainly dominated by the time T (for standard sequential algorithms) required to test the interestingness, in general the frequencies, of sets of candidates.

In this paper we propose a general parallel algorithm for computing borders whatever the application is. We prove the efficiency of our algorithm by showing that: (i) it generates exactly the same number of candidates as the standard sequential algorithm and, (ii) if the interestingness test time of a candidate is bounded by Δ then for a multi-processor shared memory machine with p cores, we prove that the total interestingness time Tp < T/p + 2 Δ n. We implemented our algorithm in the maximal frequent itemset (MFI) mining setting and our experiments confirm our theoretical performance guarantee.