## 摘要

Many applications need to deal with the additive and multiplicative subcollections over a group of set families (databases). This paper presents two efficient algorithms for computing the frequent itemsets in these two types of subcollections respectively. Let T be a given subcollection of set families of total size m whose elements are drawn from a domain of size n. We show that ifT is an additive subcollection we can compute all frequent itemsets in T in O(m2^{n}/(pn) + log p) time on an EREW PRAM with 1 ≤ p ≤ m2^{n}/n processors, at a cost of maintaining the occurrences of all itemsets in each individual set family. If T is a multiplicative subcollection, we can compute all itemsets in T in O(mk/p + min {m′/p 2^{n}, n3^{n} log m′/p}) time on an EREW PRAM with 1 ≤ p ≤ min {m,2^{n}} processors, where m′ = min {m,2^{n}}. These present improvements over direct computation of the frequent itemsets on the subcollection concerned.

原文 | English |
---|---|

頁（從 - 到） | 543-547 |

頁數 | 5 |

期刊 | Informatica (Slovenia) |

卷 | 23 |

發行號 | 4 |

出版狀態 | Published - 12月 1999 |

對外發佈 | 是 |