Efficient Computation of Frequent Itemsets In A Subcollection of Multiple Set Families
Shen, Hong; Liang, Weifa; Ng, Jack C
Description
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...[Show more]
dc.contributor.author | Shen, Hong | |
---|---|---|
dc.contributor.author | Liang, Weifa | |
dc.contributor.author | Ng, Jack C | |
dc.date.accessioned | 2015-12-13T23:24:09Z | |
dc.date.available | 2015-12-13T23:24:09Z | |
dc.identifier.issn | 0350-5596 | |
dc.identifier.uri | http://hdl.handle.net/1885/92090 | |
dc.description.abstract | 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. | |
dc.publisher | Slovene Society Informatika | |
dc.source | Informatica | |
dc.subject | Keywords: Algorithms; Database systems; Parallel processing systems; Program processors; Set theory; Frequent itemsets; Multiple set families; Data mining | |
dc.title | Efficient Computation of Frequent Itemsets In A Subcollection of Multiple Set Families | |
dc.type | Journal article | |
local.description.notes | Imported from ARIES | |
local.description.refereed | Yes | |
local.identifier.citationvolume | 23 | |
dc.date.issued | 1999 | |
local.identifier.absfor | 080109 - Pattern Recognition and Data Mining | |
local.identifier.ariespublication | MigratedxPub23066 | |
local.type.status | Published Version | |
local.contributor.affiliation | Shen, Hong, Griffith University | |
local.contributor.affiliation | Liang, Weifa, College of Engineering and Computer Science, ANU | |
local.contributor.affiliation | Ng, Jack C, University of Queensland | |
local.bibliographicCitation.issue | 4 | |
local.bibliographicCitation.startpage | 543 | |
local.bibliographicCitation.lastpage | 548 | |
dc.date.updated | 2015-12-12T09:19:21Z | |
local.identifier.scopusID | 2-s2.0-0033356233 | |
Collections | ANU Research Publications |
Download
Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.
Updated: 17 November 2022/ Responsible Officer: University Librarian/ Page Contact: Library Systems & Web Coordinator