일반기술

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

1. 기술의 개요본 기술은 최근 웹에서 정보 교환, 저장의 표준으로 사용이 급증하고 있는 XML문서에 적용할 수 있는 유용 정보 추출의 한 방법으로, 이진 코드를 이용하여 XML 데이터들을 표현한 후 일련의 비트 시퀀스들의 집합으로 재 표현된 XML 데이터들로부터 사용자로부터 직접 입력받는 최소지지도 Σ값을 만족하는 최대 Σ-빈번 서브트리 추출 방법을 제공함에 있다.2. 기술의 특징본 기술은 모든 입력 XML 트리들을 이진 코드표현으로 나타내는 단계, 이진 코드로 명시된 트리들로부터 모든 빈번 프리픽스 PAIRSETS를 얻어내는 단계 및, 얻어진 PAIRSETS로부터 다시 트리 구조로 변형하는 총 3단계로 구성된다. 이진 코드 표현 단계에서는 먼저, 각 노드에 대한 N 비트의 이진 코드 생성이 수행된 후, 이를 이용해 노드들의 연속된 연결로 각각의 경로들을 나타낸다. 빈번 프리픽스 PAIRSETS 생성 단계에서는 각 경로들을 DEPTH에 맞게 분해한 후, 그 분해된 N 비트의 프리픽스들을 키로 하여 이 키를 포함하는 트리 인덱스들과 쌍을 이뤄 PAIRSET의 원소로 설정한다. 프리픽스 PAIRSETS으로부터 최종적인 빈번 서브트리 생성을 위해 필요한 모든 빈번 프리픽스 PAIRSETS을 유도해 낸다. 최종 단계에서는 앞서 구해진 빈번 프리픽스 PAIRSETS으로부터 서브트리 구조를 생성한다. 본 기술은 XML 문서가 반구조적인 형식이라는 것을 기반으로 하여 미리 정해진 스키마가 없는 문서들을 대상으로 효율적으로 최소 지지도 Σ를 만족하는 공통의 서브트리 발견을 목적으로 한다.