DHP 연관 규칙 탐사 알고리즘을 위한 효율적인 해싱 메커니즘
An Efficient Hashing Mechanism of the DHP Algorithm for Mining Association Rules
1
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
Apriori 알고리즘에 기반한 연관 규칙 탐사 알고리즘들은 후보 빈발 항목 집합의 계수 관리를 위한 자료구조로 해시 트리를 사용하고, 많은 시간이 그 해시 트리를 검색하기 위해 소요된다. DHP 연관 규칙 탐사 알고리즘은 해시 트리에 대한 검색 시간을 절약하기 위해 검색 대상인 후보 빈발 항목 집합의 개수를 최대한 줄이고자 노력한다. 이를 위해 사전에 예비 후보 빈발 항목 집합에 대한 간편 계수를 실시한다. 이 때, 예비 계수에 필요한 계산 부담을 줄이기 위해 아주 간단한 직접 해시 테이블 사용을 권고한다. 이 논문에서는 DHP 연관 규칙 탐사 알고리즘의 단계 2에서 사전 전지를 위해 사용되는 직접 해시 테이블 H2와 모든 단계에서 후보 빈발 항목 집합의 계수를 위해 사용되는 해시 트리 Ck에 적용될 수 있는 효율적인 해싱 메카니즘을 제안하고 검증한다. 검증 결과 일반적인 단순 제산(mod) 연산 방법을 사용했을 때보다 제안 방법을 적용했을 경우 최대 82.2%, 평균 18.5%의 성능 향상이 얻어지는 것으로 나타났다.
Abstract
Algorithms for mining association rules based on the Apriori algorithm use the hash tree data structure for storing and counting supports of the candidate frequent itemsets and the most part of the execution time is consumed for searching in the hash tree. The DHP(Direct Hashing and Pruning) algorithm makes efforts to reduce the number of the candidate frequent itemsets to save searching time in the hash tree. For this purpose, the DHP algorithm does preparative simple counting supports of the candidate frequent itemsets. At this time, the DHP algorithm uses the direct hash table to reduce the overhead of the preparative counting supports. This paper proposes and evaluates an efficient hashing mechanism for the direct hash table H2 which is for pruning in phase 2 and the hash tree Ck, which is for counting supports of the candidate frequent itemsets in all phases. The results showed that the performance improvement due to the proposed hashing mechanism was 82.2% on the maximum and 18.5% on the average compared to the conventional method using a simple mod operation.
참고문헌 (11)
- 박종수, "연관 규칙 탐사와 그 응용", 16(9), pp.37~44 (1998)
- R. Agrawal, "Mining Association Rules between Sets of Items in Large Databases", pp.207~216 (1993)
- R. Agrawal, "Fast Algorithms for Mining Association Rules", pp.487~499 (1994)
- J. S. Park, "An Effective Hash-Based Algorithm for Mining Association Rules", pp.175~186 (1995)
- 이재문, "복합 해쉬 트리를 이용한 효율적인 연관 규칙 탐사 알고리즘", 26(3), pp.343~352 (1999)
- Jiawei Han, "Mining frequent patterns without candidate generation", pp.1~12 (2000)
- R. Agrawal, "Synthetic Data Generation Code for Associations and Sequential Patterns" (1999)
- A. Savasere, "An Efficient Algorithm for Mining Association Rules in Large Databases", pp.432~444 (1995)
- 이재문, "대용량 주기억장치 시스템에서 효율적인 연관 규칙 탐사 알고리즘", 9-D(4), pp.579~586 (2002)
- 이형봉, "완전 해싱을 위한 DHP 연관 규칙 탐사 알고리즘의 개선 방안", 31(2), pp.91~98 (2004)
- Zarka Cvetanovic, "AlphaServer 4100 Performance Characterization", 8(4), pp.3~20 (1996)