An Optimization of Hashing Mechanism for the DHP Association Rules Mining Algorithm

Hyung-Bong Lee; Ki-Hyeon Kwon

One of the most distinguished features of the DHP association rules mining algorithm is that it counts the support of hash key combinations composed of k items at phase k-1, and uses the counted support for pruning candidate large itemsets to improve performance. At this time, it is desirable for each hash key combination to have a separate count variable, where it is impossible to allocate the variables owing to memory shortage. So, the algorithm uses a direct hashing mechanism in which several hash key combinations conflict and are counted in a same hash bucket. But the direct hashing mechanism is not efficient because the distribution of hash key combinations is unvalanced by the characteristics sourced from the mining process. This paper proposes a mapped perfect hashing function which maps the region of hash key combinations into a continuous integer space for phase 3 and maximizes the efficiency of direct hashing mechanism. The results of a performance test experimented on 42 test data sets shows that the average performance improvement of the proposed hashing mechanism is 7.3% compared to the existing method, and the highest performance improvement is 16.9%. Also, it shows that the proposed method is more efficient in case the length of transactions or large itemsets are long or the number of total items is large.

Citation status

KCI Citation Counts (0)
REFERENCES (16)
열림/닫힘 버튼
* 2021년 이후 발행 논문의 참고문헌은 현재 구축 중입니다.

[journal] 임승환 / 2010 / Mining of Multi-dimensional Association Rules over Interval Data using Clustering and Characterization / 정보과학회논문지 : 컴퓨팅의 실제 및 레터 / 한국정보과학회 16(1) : 60~64

[confproc] 이혜리 / 2009 / 마이크로 어레이 데이터에서 특정 클래스 식별을 위한 이진 연관규칙 추출 / 한국지능시스템학회 2009년도 추계 학술발표 논문집 : 293~294

[journal] 송성렬 / 2009 / "IPTV 환경에서의 점진적 데이터를 위한 효과적인 연관규칙 추출 기법 / 한국정보과학회 2009 가을 학술발표논문집 36(2) : 246~251

[journal] 이병엽 / 2009 / Model of Customer Classification Target Marketing in Automotive Corporation / 한국콘텐츠학회 논문지 / 한국콘텐츠학회 9(4) : 313~322

[journal] 권형준 / 2009 / A Multimedia Recommender System Using User Playback Time / 인터넷정보학회논문지 / 한국인터넷정보학회 10(1) : 111~121

[confproc] 임영희 / 2008 / 연관 규칙 마이닝을 이용한 한국 신노년층의 생활 만족도에 관한 연구 / 한국가정관리학회 2008년 추계학술대회 : 164~173

[book] M.Schrader, / 2009 / Oracle Essbase & Oracle OLAP / McGraw-Hill,Oct

[journal] Mark Hall / 2009 / The WEKA Data Mining Software: An Update / SIGKDD Explorat- ions, 11(1)

[confproc] J.S.Park / 1995 / An Effective Hash-Based Algorithm for Mining Association Rules / Proceedings of ACM SIGMOD, : 175~186

[confproc] J. Han / 2000 / Mining frequent patterns without candidate generation / Proceedings ACM SIGMOD Int'l Conf. Management of Data(SIGMOD' 00)

[journal] 이형봉 / 2008 / Performance Evaluation of the FP-tree and the DHP Algorithms for Association Rule Mining / 정보과학회논문지 : 데이타베이스 / 한국정보과학회 35(3) : 199~207

[confproc] R.Agrawal, / 1993 / Mining Association Rules between Sets of Items in Large Databases / Proceedings of ACM SIGMOD on Management of Data : 207~216

[confproc] R.Agrawal / 1994 / Fast Algorithms for Mining Association Rules / Proceedings of the 20th Inte-rnational Conference on Very Large Databases : 487~499

[journal] 이형봉 / 2004 / Improvement of DHP Association Rules Algorithm for Perfect Hashing / 정보과학회논문지 : 데이타베이스 / 한국정보과학회 31(2) : 91~98

[journal] 이형봉 / 2006 / An Efficient Hashing Mechanism of the DHP Algorithm for Mining Association Rules / 정보처리학회논문지D / 한국정보처리학회 13(6) : 651~660

[web] R.Agrawal / Synthetic Data Generation Code for Associations and Sequential Patterns / http://www.almaden.ibm.com/cs/projects/iis/hdb/ Projects/data_mining/mining.shtml

KJC Korea
Journal Central

Statistics

Tools

Sharing

Issue List

Citation status