| 한글제목(Korean Title) |
대응효율성을 통한 변화 탐지 알고리즘의 성능 개선 |
| 영문제목(English Title) |
Improving Performance of Change Detection Algorithms through the Efficiency of Matching |
| 저자(Author) |
이석균
김동아
|
| 원문수록처(Citation) |
VOL 14-D NO. 02 PP. 0145 ~ 0156 (2007. 04) |
한글내용
(Korean Abstract) |
최근 웹 문서의 변조의 탐지, 버전 관리 등을 위한 XML/HTML 문서들에 대한 효과적인 실시간 변화탐지 알고리즘의 필요성이 증대하고 있다. 특히 대용량의 XML/HTML 문서들에 대한 실시간 변화탐지 응용들은 최소비용의 편집스크립트를 계산하는 알고리즘 보다는 실시간 처리가 가능한 빠른 휴리스틱 알고리즘들을 필요로 한다. 기존의 휴리스틱 알고리즘들은 실행속도는 빠르나 생성되는 편집스크립트의 질이 만족스럽지 못하다. 본 논문에서는 기존의 알고리즘 XyDiff와 X-tree Diff를 소개하고 이들 알고리즘들의 문제점들을 분석하고 문제점들을 개선한 알고리즘 X-tree Diff+를 제안한다. X-tree Diff+는 실행시간 측면에서 기존 알고리즘들과 유사하나 대응효율성에 기반한 대응과정의 개선을 통
해 두 문서 간의 노드들의 대응률을 향상시킨 알고리즘이다. |
영문내용
(English Abstract) |
Recently, the needs for effective real-time change detection algorithms for XML/HTML documents are increased in such fields as the detection of defacement attacks to web documents, the version management, and so on. Especially, those applications of real-time change
detection for large number of XML/HTML documents require
fast heuristic algorithms to be used in real-time
environment, instead of algorithms which compute minimal cost-edit scripts. Existing heuristic algorithms are fast in execution time, but do not provide satisfactory
edit script. In this paper, we present existing algorithms
XyDiff and X-tree Diff, analyze their problems and propose
algorithm X-tree Diff which improve problems in existing ones. X-tree Diff has similar performance in execution time with existing algorithms, but it improves matching ratio between nodes from two documents by refining
matching process based on the notion of efficiency of
matching. |
| 키워드(Keyword) |
계층구조 문서
XML
diff 알고리즘
변화탐지
Hierarchically-structured documents
XML
diff algorithm
Change Detection
|
| 파일첨부 |
PDF 다운로드
|
