중첩 조건이 없는 규칙 검색 시간 단축을 위한 다계층 인덱싱 기술 (Multilevel Indexing for Reducing Searching Time of Rules without Overlapping Conditions)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회 컴퓨팅의 실제 논문지 / 27권 / 2호 / 69 ~ 75페이지
· 저자명 : 김광수, 박동환, 진성일

초록

규칙 기반 시스템은 비교적 간단한 규칙을 사용하여 데이터로부터 유효한 정보를 추출하는 인공 지능 응용에 사용된다. 규칙 기반 시스템은 일반적으로 학습이 없으므로 시스템 설치 후 즉시 작동하는 장점이 있으나, 규칙 매칭에 복잡한 처리가 필요하다. 기존의 규칙 매칭 방법들은 규칙들이 서로 중첩되는 조건을 가질 때 빠르지만, 조건들이 중첩되지 않는 경우 검색 속도가 저하된다. 본 논문에서는 규칙의 조건이 중첩되지 않을 때 규칙 검색 시간을 단축하기 위한 다단계 인덱싱 방법을 제안한다. 제안된 방법은 2단계 검색 트리를 사용하며, 트리의 각 레벨에서 서로 다른 값을 사용하여 규칙을 분류한다. 첫 번째 단계에서는 조건에 포함된 센싱 값의 수를 사용하며, 두 번째 단계에서는 각 센싱 값의 범위를 사용하였다. 분석적 방법을 통해 최적의 서브 그룹 수를 정의하였으며, 실험 결과를 통해 제안된 방법의 빠른 검색 시간을 확인하였다. 검색 시간은 기존의 PHREAK 방식보다 약 3 배 정도 빠르다.

영어초록

A rule-based system is used in artificial intelligence applications, which extract meaningful information from data with relatively simple rules. This system offers a benefit that it can be activated immediately after system installation as usually it does not require learning, but it needs complex processing in rule matching. Previous rule matching algorithms achieve high performance when the rules have many overlapping conditions, but if that is not the case, the searching speed slows down.
This paper describes a multilevel indexing method for reducing the rule retrieval time when the conditions in rules do not overlap. The proposed method generates a two-level indexing tree using different values at each level to classify the rules. The number of sensing types in the conditions is used at the first step and the number of ranges of each sensing value is used at the second step. The optimal number of ranges is defined by an analytical method. The experimental results show that the proposed method can achieve a fast search time. Its searching time is about three times faster than that of the PHREAK method.

참고자료

· 없음