일반기술

이진 코드를 이용한 엑스엠엘 데이터들의 최대 σ-빈번서브트리 추출방법

*원리 및 구성본 기술은 최근 웹에서 정보 교환, 저장의 표준으로 사용이 급증하고 있는 XML문서에 적용할 수 있는 유용 정보 추출의 한 방법으로, 이진 코드를 이용하여 XML 데이터들을 표현한 후 일련의 비트 시퀀스들의 집합으로 재 표현된 XML 데이터들로부터 사용자로부터 직접 입력받는 최소지지도 Σ값을 만족하는 최대 Σ-빈번 서브트리 추출 방법을 제공함에 있다. 본 발명은 모든 입력 XML 트리들을 이진 코드표현으로 나타내는 단계, 이진 코드로 명시된 트리들로부터 모든 빈번 프리픽스 PAIRSETS를 얻어내는 단계 및, 상기 얻어진 PAIRSETS로부터 다시 트리 구조로 변형하는 총 3단계로 구성된다. 이진 코드 표현 단계에서는 먼저, 각 노드에 대한 N 비트의 이진 코드 생성이 수행된 후, 이를 이용해 노드들의 연속된 연결로 각각의 경로들을 나타낸다. 빈번 프리픽스 PAIRSETS 생성 단계에서는 각 경로들을 DEPTH에 맞게 분해한 후, 그 분해된 N 비트의 프리픽스들을 키로 하여 이 키를 포함하는 트리 인덱스들과 쌍을 이뤄 PAIRSET의 원소로 설정한다. 프리픽스 PAIRSETS으로부터 최종적인 빈번 서브트리 생성을 위해 필요한 모든 빈번 프리픽스 PAIRSETS을 유도해 낸다. 최종 단계에서는 앞서 구해진 빈번 프리픽스 PAIRSETS으로부터 서브트리 구조를 생성한다. 본 발명은 XML 문서가 반구조적인 형식이라는 것을 기반으로 하여 미리 정해진 스키마가 없는 문서들을 대상으로 효율적으로 최소 지지도 Σ를 만족하는 공통의 서브트리 발견을 목적으로 한다.*본 기술의 장점첫째, 본 XML 트리 데이터들을 대상으로 빈번 서브트리 패턴을 생성하는 방식은 네트워크 상에서 전송, 저장되는 정보를 제공하는 모든 반구조적 객체들에 적용 가능하다. 따라서, 전자 상거래, 문서 교환, 정보 공유 등의 등에 활용할 수 있다. 또한, 이종 환경에서의 XML 문서들을 통합하는 시스템에 요구되는 복잡도와 저장공간 그리고 수행 시간이 적은 효율적인 방식이므로 인테그레이션 시스템에 적용 가능하다.둘째, 최근 들어 국내외에서 XML 형식을 기반으로하는 문서나 언어의 사용이 증가하고 있으며, 이와 더불어 효율적으로 공통 패턴들을 분석하는 서비스를 제공하기 위한 XML 마이닝 시스템에 대한 연구/개발도 활발히 진행중이다. 따라서, XML 기반의 이기종 환경에 적합한 빈번 서브트리 패턴 생성 알고리즘의 사용도 증가할 것으로 기대.셋째, 이진 코드 표현 방식과 PairSet이라는 새로운 정의에 의존함으로써 기존 대부분의 알고리즘에서 요구되어 온 에지 조인 생성을 생략함으로써 이를 통해 기존의 방식에 비해 요구되는 계산량을 감소시킨다 또한, 가장 많이 쓰이며 그 효과가 검증된 Apriori 방식을 사용함으로 알고리즘의 구조를 복잡하게 만들지 않는다.