Perfect Hashing Schemes for Mining Association Rules

ASIAIR > College of Computer Science > Department of Computer Science and Information Engineering > Journal Artical > Item 310904400/6558

Please use this identifier to cite or link to this item: http://asiair.asia.edu.tw/ir/handle/310904400/6558

Title:	Perfect Hashing Schemes for Mining Association Rules
Authors:	Chang, C. C.;Lin, C. Y
Date:	2005-03
Issue Date:	2009-12-17 06:58:37 (UTC+0)
Publisher:	Asia University
Abstract:	Hashing schemes are widely used to improve the performance of data mining association rules, as in the DHP algorithm that utilizes the hash table in identifying the validity of candidate itemsets according to the number of the table's bucket accesses. However, since the hash table used in DHP is plagued by the collision problem, the process of generating large itemsets at each level requires two database scans, which leads to poor performance. In this paper we propose perfect hashing schemes to avoid collisions in the hash table. The main idea is to employ a refined encoding scheme, which transforms large itemsets into large 2-itemsets and thereby makes the application of perfect hashing feasible. Our experimental results demonstrate that the new method is also efficient (about three times faster than DHP), and scalable when the database size increases. We also propose another variant of the perfect hash scheme with reduced memory requirements. The properties and performances of several perfect hashing schemes are also investigated and compared.
Relation:	The Computer Journal 48(2):168-179
Appears in Collections:	[Department of Computer Science and Information Engineering] Journal Artical

Files in This Item:

File	Description	Size	Format
		0Kb	Unknown	587	View/Open
310904400-6558.doc		78Kb	Microsoft Word	269	View/Open