대응효율성을 통한 변화 탐지 알고리즘의 성능 개선

이석균,김동아,Lee, Suk-Kyoon,Kim, Dong-Ah 한국정보처리학회 2007 정보처리학회논문지D Vol.14 No.2

Recently, the needs for effective real time change detection algorithms for XML/HTML documents and 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. 최근 웹 문서의 변조의 탐지, 버전 관리 등을 위한 XML/HTML 문서들에 대한 효과적인 실시간 변화탐지 알고리즘의 필요성이 증대하고 있다. 특히 대용량의 XML/HTML 문서들에 대한 실시간 변화탐지 응용들은 최소비용의 편집스크립트를 계산하는 알고리즘 보다는 실시간 처리가 가능한 빠른 휴리스틱 알고리즘들을 필요로 한다. 기존의 휴리스틱 알고리즘들은 실행속도는 빠르나 생성되는 편집스크립트의 질이 만족스럽지 못하다. 본 논문에서는 기존의 알고리즘 XyDiff와 X-tree Diff를 소개하고 이들 알고리즘들의 문제점들을 분석하고 문제점들을 개선한 알고리즘 X-tree Diff+를 제안한다. X-tree Diff+는 실행시간 측면에서 기존 알고리즘들과 유사하나 대응효율성에 기반한 대응과정의 개선을 통해 두 문서 간의 노트들의 대응률을 향상시킨 알고리즘이다.

삽입/삭제 편집연산 기반의 XML 문서 병합

이석균,Lee, Suk-Kyoon 한국정보처리학회 2009 정보처리학회논문지D Vol.16 No.4

오피스 및 과학 분야의 문서 작업 등에서 XML의 사용이 보편화되고 협업이 요구됨에 따라 효과적인 XML 문서 병합 방법이 필요하다. 이에 대한 해결 방안으로 본 논문에서는 동일 원본 문서에 대한 다수 사용자의 편집 작업들의 병합을 위한 이론적 틀을 제시한다. 문서들의 병합시 문서 자체를 병합하는 기존의 방법들과는 달리, 사용자의 편집 작업을 원본 문서에 적용되는 일련의 편집 연산들, 즉 편집 스크립트로 표현하고 다수 사용자의 편집 스크립트들을 병합하고 원본 문서에 적용하여 문서의 병합 효과를 이루고자 한다. 이를 위해 삽입과 삭제연산으로 구성된 편집스크립트를 전제로 정적 편집 스크립트, 편집 스크립트의 간섭 및 충돌 등의 개념들을 정의하고 편집 스크립트들의 충돌 조건과 병합시 편집 스크립트 조정기법을 제안한다. 이 방법은 분산 환경에서 네트워크 부하를 줄이며 각 편집 작업의 의미가 보존되어 버전관리에 효과적이다. The method of effectively merging XML documents becomes necessary, as the use of XML is popular and the collaborative editing is required in the areas such as office documents and scientific documents editing works. As a solution to this problem, in this paper we present a theoretical framework for merging individual editing works by muli-users to a same source document. Different from existing approaches which merge documents themselves when they are merged, we represent editing works with a series of edit operations applied to a source document, which is called a edit script, merge those edit scripts by multi-users, and apply the merged one to the source document so that we can achieve the same effect of merging documents. In order to do this, assuming edit scripts based on insertion and deletion edit operations, we define notions such as static edit scripts, the intervention between edit scripts and the conflict between the ones, then propose the conflict conditions between edit scripts and the method of adjusting edit scripts when merged. This approach is effective in reducing network overhead in distributed environments and also in version management systems because of preserving the semantics of individual editing works.

X-tree Diff: 트리 기반 데이터를 위한 효율적인 변화 탐지 알고리즘

이석균,김동아,Lee, Suk-Kyoon,Kim, Dong-Ah 한국정보처리학회 2003 정보처리학회논문지 C : 정보통신,정보보안 Vol.10 No.6

인터넷 사용이 급속도로 증가함에 따라 XML/HTML 문서와 같이 트리 구조로 표현되는 데이터의 변화 탐지가 중요한 연구 분야로 등장하고 있다. 본 논문에서는 효율적인 변화 탐지를 위한 데이터 구조로 X-tree와 이에 기초한 휴리스틱 변화 탐지 알고리즘 X-tree Diff 를 제안한다. X-tree Diff 는 X-tree 의 변화 내용에 대한 최소 비용 편집 스크립트를 찾는 알고리즘과는 달리 휴리스틱 트리 대응 알고리즘을 통해 병화 내용을 확인하는 알고리즘으로, X-tree 에 속한 모든 노드에 대해 각각의 노드를 루트로 하는 서브트리의 구조와 서브트리속에 속한 노드들의 데이터들을 128비트 해시값으로 표현한 값인 트리 MD를 각 노드에 저장하고, 이를 변화 탐지 과정에서 활용하여 신-구 버전의 X-tree들에 속한 서브트리들의 비교을 효율적으로 처리한다. X-tree Diff 는 4단계로 구성되며 1)신-구버넌의 X-tree노드들에 대해, 우선 1:1 대응이 가능한 모든 동등한 서브트리 쌍을 찾고, 2) 이들 서브트리 쌍의 루트로부터 신-구 버전의 X-tree의 루트까지의 경로 상에 존재하는 노드들에 대한 대응관계를 결정한다. 3) 그 후 신-구 버전의 X-tree의 루트들로부터 깊이 우선 탐색으로 노드를 방문하며 대응이 결정되지 않은 노드들에 대한 대응여부를 결정해 나간다. 4) 마지막까지 대응여부가 결정되지 않은 도드들은 삭제나 삽입된 것으로 간주한다. X-tree Diff XML 문서들에 대한 버저닝(Versioning) 을 목적으로 설계된 BUILD Diff 알고리즘과 달리 XML/HTML 에 공통적으로 사용할 수 있을 뿐 아니라, 알고리즘이 명확하고 간결하여 다양한 형태의 확장이 가능하다. 알고리즘의 성능도 개선되어 신-구 X-tree의 노드의 수를 n이라 할 때, O(n)의 시간 복잡도를 갖는다. 제안된 알고리즘은 현재 보안 관련 상용 시스템인 WIDS(Web-Document Instrusion Detection System) 에서 사용되고 있으며, 본 논문에서는 WIDS를 이용하여 20여개 신문-방송 사이트에서 변화가 탐지된 11,000 개 페이지에 대한 성능평가를 보이고 있다. We present X-tree Diff, a change detection algorithm for tree-structured data. Our work is motivated by need to monitor massive volume of web documents and detect suspicious changes, called defacement attack on web sites. From this context, our algorithm should be very efficient in speed and use of memory space. X-tree Diff uses a special ordered labeled tree, X-tree, to represent XML/HTML documents. X-tree nodes have a special field, tMD, which stores a 128-bit hash value representing the structure and data of subtrees, so match identical subtrees form the old and new versions. During this process, X-tree Diff uses the Rule of Delaying Ambiguous Matchings, implying that it perform exact matching where a node in the old version has one-to one corrspondence with the corresponding node in the new, by delaying all the others. It drastically reduces the possibility of wrong matchings. X-tree Diff propagates such exact matchings upwards in Step 2, and obtain more matchings downwsards from roots in Step 3. In step 4, nodes to ve inserted or deleted are decided, We aldo show thst X-tree Diff runs on O(n), woere n is the number of noses in X-trees, in worst case as well as in average case, This result is even better than that of BULD Diff algorithm, which is O(n log(n)) in worst case, We experimented X-tree Diff on reat data, which are about 11,000 home pages from about 20 wev sites, instead of synthetic documets manipulated for experimented for ex[erimentation. Currently, X-treeDiff algorithm is being used in a commeercial hacking detection system, called the WIDS(Web-Document Intrusion Detection System), which is to find changes occured in registered websites, and report suspicious changes to users.

X-treeDiff+기반의 한글 문서에 대한 변화 탐지

이석균(Suk Kyoon Lee) 한국산업정보학회 2010 한국산업정보학회논문지 Vol.15 No.4

XML 문서에 대한 변화탐지는 중요한 연구 분야이다. 그러나 한글 문서 파일 형식으로 XML이 지원되고 있음에도 한글 문서의 특성을 반영한 변화 탐지 연구는 아직 미비하다. 한글 문서는 일반적인 XML 문서와는 달리 서식 정보의 비중이 매우 커서 X-treeDiff+와 같은 일반적인 XML 문서의 변화탐지 알고리즘을 그대로 적용하기에는 적합하지 않다. 본 논문에서는 한글 문서에 대한 변화탐지를 위해 새로운 내용 기반의 대응 알고리즘을 제안하고 이를 X-treeDiff+에 구현하였다. 실험을 통해 제안된 알고리즘은 대부분의 편집과정의 문서에 대해 우수한 성능을 보이고 있음을 제시했다. The change detection of XML documents is a major research area. However, though XML becomes a file format for Hangul documents, research on change detection of Hangul documents based on the characteristics of Hangul documents is rather scarce. Since format data in Hangul documents are very large, which is different from ordinary XML documents, it is not proper to apply general XML change detection algorithms such as X-treeDiff+ to Hangul documents without any change. In this paper, we propose new contents-based matching algorithm and implement it in X-treeDiff+. The result of our testing shows better performance for most documents in editing process.

X-treeDiff+ 기반의 프로그램 복제 탐지

이석균(Suk Kyoon Lee) 대한전자공학회 2010 電子工學會論文誌-CI (Computer and Information) Vol.47 No.4

컴퓨터 프로그래밍 교육에서 프로그램 복제는 프로그래밍 학습 효율을 저해하는 심각한 요인이다. 본 논문에서는 학생들이 프로그래밍 과제의 무분별한 복제를 방지하기 위해 유사 또는 동일 프로그램을 탐지하는 기법을 제안한다. 지문법이나 스트링 매칭을 기반으로 하는 기존의 탐지 기법과는 달리, 우선 C 프로그램을 파싱하여 문법요소를 엘리먼트로 하는 XML 문서로 변화시킨 후 XML 문서의 변화탐지 알고리즘인 X-treeDiff+를 실행시켜 그 차이를 분석하는 방법을 취한다. 이때 대응의 정도를 나타내는 유사도와 두 문서의 차이로 제시되는 일련의 편집연산인 편집스크립트를 프로그램 복제의 관점에서 분석하여 복제 여부에 대한 판단을 하게 된다. 편집스크립트의 분석은 두 프로그램 간의 변환 과정을 유추할 수 있게 하여 기존 방법들과는 달리 사용자는 과제의 성격이나 복제의 정도를 고려한 정성적인 판단이 가능하다는 장점이 있다. Program plagiarism is a significant factor to reduce the quality of education in computer programming. In this paper, we propose the technique of identifying similar or identical programs in order to prevent students from reckless copying their programming assignments. Existing approaches for identifying similar programs are mainly based on fingerprints or pattern matching for text documents. Different from those existing approaches, we propose an approach based on the program structur. Using paring progrmas, we first transform programs into XML documents by representing syntactic components in the programs with elements in XML document, then run X-tree Diff+, which is the change detection algorithm for XML documents, and produce an edit script as a change. The decision of similar or identical programs is made on the analysis of edit scripts in terms of program plagiarism. Analysis of edit scripts allows users to understand the process of conversion between two programs so that users can make qualitative judgement considering the characteristics of program assignment and the degree of plagiarism.

다중 사용자를 위한 Dynamic Time Warping 기반의 특징 강조형 제스처 인식 모델

이석균 ( Suk Kyoon Lee ),엄현민 ( Hyun Min Um ),권혁태 ( Hyuck Tae Kwon ) 한국정보처리학회 2016 정보처리학회논문지. 소프트웨어 및 데이터 공학 Vol.5 No.10

최근 제안된 FsGr 모델은 가속도 센서 기반의 제스처 인식을 위한 방법으로 DTW 알고리즘을 두 단계로 적용하여 인식률을 개선하였다. FsGr 모델에서는 유사제스처 집합 개념을 정의하는데 훈련과정에서 유사제스처 집합들을 생성한다. 제스처 인식의 1차 인식 시도에서 유사제스처 집합이 정의된 제스처로 판정되면, 이 유사제스처 집합의 제스처들에 대해 특징이 강조된 부분들을 추출해 DTW를 통한 2차 인식을 시도한다. 그러나 동일 제스처도 사용자의 신체 크기, 나이, 성별, 등의 신체적인 특징에 따라 매우 다른 특성을 보이고 있어 FsGr 모델을 다중 사용자 환경에 적용하기에는 한계가 있다. 본 논문에서는 이를 다중 사용자 환경으로 확장한 FsGrM 모델을 제안하고 이를 사용한 스마트TV의 채널 및 볼륨 제어 프로그램을 보인다. FsGr model, which has been proposed recently, is an approach of accelerometer-based gesture recognition by applying DTW algorithm in two steps, which improved recognition success rate. In FsGr model, sets of similar gestures will be produced through training phase, in order to define the notion of a set of similar gestures. At the 1st attempt of gesture recognition, if the result turns out to belong to a set of similar gestures, it makes the 2nd recognition attempt to feature-strengthened parts extracted from the set of similar gestures. However, since a same gesture show drastically different characteristics according to physical traits such as body size, age, and sex, FsGr model may not be good enough to apply to multi-user environments. In this paper, we propose FsGrM model that extends FsGr model for multi-user environment and present a program which controls channel and volume of smart TV using FsGrM model.

실시간 온라인 스케줄링 알고리즘들의 분석 및 성능 비교

이석균(Suk Kyoon Lee),임준택(Joon Taek Lim) 한국정보과학회 1995 한국정보과학회 학술발표논문집 Vol.22 No.1

실시간 시스템을 위한 다중 프로세서(multiprocessor) 지원은 점차 중요시되어 가고 있다. 다중프로세서 시스템에서 실시간 산발적인 테스크(real-time sporadic task)들을 위한 기존의 온라인 스케쥴링 알고리즘인 EDA는 스케쥴링 파워가 떨어지는 단점이, LLA는 문맥교환 오버헤드(context switching overhead)가 큰 단점이 있다. 이 두가지 단점을 보완한 EDZL을 소개하고 그 이론적인 분석 및 시뮬레이션을 통한 성능분석을 통해 EDZL이 EDA나 LLA보다 뛰어남을 보인다.

XML 문서에 대한 편집스크립트 생성 알고리즘

이석균(Suk Kyoon Lee) 大韓電子工學會 2011 電子工學會論文誌-CI (Computer and Information) Vol.48 No.1

최근 XML문서의 변화탐지가 중요한 연구 분야로 등장하고 있지만 변화탐지의 결과, 즉 편집스크립트에 대한 연구는 아직 초보적인 수준이다. 본 연구에서는 XML 문서의 변화탐지 알고리즘인 X-treeDiff+의 편집스크립트 생성알고리즘인 X-treeESgen을 제시한다. 이는 실행시간 O(n)의 성능을 가지면서 기존의 다른 알고리즘과 달리 삽입, 삭제, 갱신의 기본연산 이외에 이동 및 복사 연산을 지원한다. 또한 편집스크립트 생성과정이 변화탐지의 대응과정과 독립적으로 설계되어 있어 다양한 튜닝이 가능한 특징이 있다. While detecting changes in XML documents has emerged as a major research area, the level of research on edit scripts, which are the result of the change detection, is not far from satisfactory. In this paper, we present X-treeESgen, the algorithm generating edit scripts used in X-treeDiff+, a change detection alogrithm for XML documents. X-treeESgen shows the time complexity of O(n), and support move and copy operations in addition to the basic set that is update, insert, and delete operations. Note that no other change detection algorithm provide all the operations. Also, since the process of generating edit scripts in X-treeESgen is designed independent of the process of matching, various tuning techniques may be applied.

VOQL* : 귀납적으로 정의된 형식 시맨틱을 지닌 시각 객체 질의어

이석균(Suk Kyoon Lee) 한국정보과학회 2000 정보과학회논문지 : 데이타베이스 Vol.27 No.2

객체 데이타베이스를 위해 최근에 제안된 VOQL(Visual Object Query Language)은 경로식과 집합 관련 조건을 시각화하고 형식 시맨틱을 제공하는데 성공적이었다. 그러나 기존의 VOQL은 몇가지 문제들이 있다. VOQL에서는 집합 관련 조건만이 허용되고, 변수 개념을 위한 명시적인 언어 구문이 없어서 질의문들은 종종 어색하고 직관적이지 못하다. 본 논문에서는 이러한 문제들을 극복하도록 VOQL을 확장한 VOQL*를 제안한다. 시각변수 개념을 도입하고 이에 기초하여 VOQL의 문법과 시맨틱을 수정하였다. VOQL*의 언어 구문들은 OOPC의 문법을 반영하도록 조심스럽게 정의되어서, 시각변수, 시각요소, VOQL* 단순 텀(term), VOQL* 구조 텀, VOQL* 기본 포뮬라(formula), VOQL* 포뮬라, VOQL* 질의문 등의 VOQL* 구문들이 OOPC 구문들처럼 계층적이고 귀납적으로 구성되어 있다. 가장 중요한 것은 VOQL*의 각 구문의 시맨틱이 OOPC를 사용하여 재귀적 방법을 통한 형식 정의가 이루어진다는 점이다. 잘 정의된 문법과 시맨틱으로 말미암아, VOQL*의 질의문들은 명확하고 간결하고 직관적이다. 또한 VOQL* 질의문을 OOPC 질의문으로 번역하는 효과적인 절차를 제공한다. VOQL*는 로직의 문법적 구조를 반영하는 잘 정의된 문법과 귀납적 방법으로 형식 시맨틱을 제공하는 첫번째 시각 질의어이다. The Visual Object Query Language (VOQL) recently proposed for object databases has been successful in visualizing path expressions and set-related conditions, and providing formal semantics. However, VOQL has several problems. Due to unrealistic assumptions, only set-related conditions can be represented in VOQL. Due to the lack of explicit language construct for the notion of variables, queries are often awkard and less intuitive. In this paper, we propose VOQL*, which extends VOQL to remove these drawbacks. We introduce the notion of visual variables and refine the syntax and semantics of VOQL based on visual variables. We carefully design the language constructs of VOQL* to reflect the syntax of OOPC, so that the constructs such as visual variables, visual elements, VOQL* simple terms, VOQL* structured terms, VOQL* basic formulas, VOQL* formulas, and VOQL* query expressions are hierarchically and inductively constructed as those of OOPC. Most important, we formally define the semantics of each language construct of VOQL* by induction using OOPC. Because of the well-defined syntax and semantics, queries in VOQL* are clear, concise, and intuitive. We also provide an effective procedure to translate queries in VOQL* into those in OOPC. We believe that VOQL* is the first visual query language with the well-defined syntax reflecting the syntactic structure of logic and semantics formally defined by induction.

신뢰도와 불확실성을 지원하는 확장 관계형 데이타 모델

이석균(Suk Kyoon Lee) 한국정보과학회 1997 정보과학회논문지(B) Vol.24 No.4

데이타의 불확실성과 데이타의 신뢰도를 동시에 표현하는 확장 관계형 데이타 모델을 제안한다. 데이타의 신뢰도(reliability)는 불확실성의 근원을 데이타를 제공하고 있는 제공원(source)의 신뢰도로 정의하며, 데이타의 불확실성(uncertainty)은 퍼지 또는 확률 분포 등으로 나타나는 데이타의 표현 형태(uncertainty representation)를 의미한다. 데이타의 신뢰도와 불확실성은 상호 밀접한 관계를 가지므로 현실성 있는 데이타 모델은 이 두 개념을 동시에 지원해야 한다. 본 논문에서는 확률이론에 입각하여 속성 값(attribute 값)의 불확실성과 속성 값에 대한 제공원의 신뢰도를 표현하며 이에 따른 selection 연산을 정의하는 확장 관계형 모델을 제안하는 데 이는 신뢰도와 불확실성에 동시에 고려하는 최초의 확장 관계형 데이타 모델이다. We propose an extended relational data model which can represent both the uncertainty in data and the reliability of data. The reliability of data is defined as the reliability of the source for data, while the uncertainty in data is defined as the uncertainty representation of data (e.g a fuzzy distribution, a probability distribution, etc) Since the reliability of data and the uncertainty in data are closely related to each other, a realistic data model should support the concept of reliability as well as that of uncertainty. In this paper, we represent the uncertainty in data and the reliability of data at the level of attribute value in terms of the theory of probability, then define the selection operation. Our approach is the extended relational data model which consider both the uncertainty in data and the reliability of data.