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.
[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
@article{ART001473699}, author={Hyung-Bong Lee and Ki-Hyeon Kwon}, title={An Optimization of Hashing Mechanism for the DHP Association Rules Mining Algorithm}, journal={Journal of The Korea Society of Computer and Information}, issn={1598-849X}, year={2010}, volume={15}, number={8}, pages={13-21}
TY - JOUR AU - Hyung-Bong Lee AU - Ki-Hyeon Kwon TI - An Optimization of Hashing Mechanism for the DHP Association Rules Mining Algorithm JO - Journal of The Korea Society of Computer and Information PY - 2010 VL - 15 IS - 8 PB - The Korean Society Of Computer And Information SP - 13 EP - 21 SN - 1598-849X AB - 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. KW - DHP;직접 해싱(direct hashing);사상 완전 해싱(mapped perfect hashing) DO - UR - ER -
Hyung-Bong Lee and Ki-Hyeon Kwon. (2010). An Optimization of Hashing Mechanism for the DHP Association Rules Mining Algorithm. Journal of The Korea Society of Computer and Information, 15(8), 13-21.
Hyung-Bong Lee and Ki-Hyeon Kwon. 2010, "An Optimization of Hashing Mechanism for the DHP Association Rules Mining Algorithm", Journal of The Korea Society of Computer and Information, vol.15, no.8 pp.13-21.
Hyung-Bong Lee, Ki-Hyeon Kwon "An Optimization of Hashing Mechanism for the DHP Association Rules Mining Algorithm" Journal of The Korea Society of Computer and Information 15.8 pp.13-21 (2010) : 13.
Hyung-Bong Lee, Ki-Hyeon Kwon. An Optimization of Hashing Mechanism for the DHP Association Rules Mining Algorithm. 2010; 15(8), 13-21.
Hyung-Bong Lee and Ki-Hyeon Kwon. "An Optimization of Hashing Mechanism for the DHP Association Rules Mining Algorithm" Journal of The Korea Society of Computer and Information 15, no.8 (2010) : 13-21.
Hyung-Bong Lee; Ki-Hyeon Kwon. An Optimization of Hashing Mechanism for the DHP Association Rules Mining Algorithm. Journal of The Korea Society of Computer and Information, 15(8), 13-21.
Hyung-Bong Lee; Ki-Hyeon Kwon. An Optimization of Hashing Mechanism for the DHP Association Rules Mining Algorithm. Journal of The Korea Society of Computer and Information. 2010; 15(8) 13-21.
Hyung-Bong Lee, Ki-Hyeon Kwon. An Optimization of Hashing Mechanism for the DHP Association Rules Mining Algorithm. 2010; 15(8), 13-21.
Hyung-Bong Lee and Ki-Hyeon Kwon. "An Optimization of Hashing Mechanism for the DHP Association Rules Mining Algorithm" Journal of The Korea Society of Computer and Information 15, no.8 (2010) : 13-21.