TY - JOUR
T1 - Efficient computation of frequent itemsets in a subcollection of multiple set families
AU - Shen, Hong
AU - Liang, Weifa
AU - Ng, Joseph
N1 - Copyright:
Copyright 2005 Elsevier Science B.V., Amsterdam. All rights reserved.
PY - 1999/12
Y1 - 1999/12
N2 - 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(m2n/(pn) + log p) time on an EREW PRAM with 1 ≤ p ≤ m2n/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 2n, n3n log m′/p}) time on an EREW PRAM with 1 ≤ p ≤ min {m,2n} processors, where m′ = min {m,2n}. These present improvements over direct computation of the frequent itemsets on the subcollection concerned.
AB - 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(m2n/(pn) + log p) time on an EREW PRAM with 1 ≤ p ≤ m2n/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 2n, n3n log m′/p}) time on an EREW PRAM with 1 ≤ p ≤ min {m,2n} processors, where m′ = min {m,2n}. These present improvements over direct computation of the frequent itemsets on the subcollection concerned.
UR - http://www.scopus.com/inward/record.url?scp=0033356233&partnerID=8YFLogxK
M3 - Journal article
AN - SCOPUS:0033356233
SN - 0350-5596
VL - 23
SP - 543
EP - 547
JO - Informatica (Slovenia)
JF - Informatica (Slovenia)
IS - 4
ER -