트리구조의 문서에 대한 편집스크립트 조정

이석균,엄현민 한국산업정보학회 2019 한국산업정보학회논문지 Vol.24 No.2

Since most documents used in web, XML, office applications are tree-structured, diff, merge, and version control for tree-structured documents in multi-user environments are crucial tasks. However research on edit scripts which is a basis for them is in primitive stage. In this paper, we present a document model for understanding the change of tree-structured documents as edit scripts are executed, and propose a method of switching adjacent edit operations on tree-structured documents based on the analysis of the effects of edit operations. Mostly, edit scripts which are produced as the results of diff on tree-structured documents only consist of basic operations such as update, insert, delete. However, when move and copy are included in edit scripts, because of the characteristics of their complex operation, it is often that edit scripts are generated to execute in two passes. In this paper, using the proposed method of switching edit operations, we present an algorithm of transforming the edit scripts of X-treeESgen, which are designed to execute in two passes, into the ones that can be executed in one pass.

있는데 없는 참 이상한 외 1편

이석균 고요아침 2022 열린시학 Vol.27 No.2

EA성과평가 모델의 설계 및 적용사례에 관한 연구

이석균,이영민,류성열,Lee, Seok-Kyun,Lee, Young-Min,Rhew, Sung-Yul 한국정보처리학회 2009 정보처리학회논문지D Vol.16 No.3

현재 정부 각 부처는 “정보시스템의 효율적 도입 및 운영 등에 관한 법률”에 의해 EA를 도입하여 운용하고 있으나 이의 평가 체계 및 지표는 제대로 갖춰져 있지 않다. 특히 EA의 성과평가를 위한 모델이 없을 뿐만 아니라 측정 할 수 있는 방법도 미흡하다. 본 연구에서는 EA성과평가를 위해 국내 범정부 성과참조모델과 미 연방 성과참조모델을 기반으로 8개의 평가 영역 및 17개의 평가지표를 도출하였다. 또한, 미 OMB 및 국내 범정부 EA성숙도 모델을 기반으로 8개의 평가 영역 및 10개의 평가지표를 도출하여, 이를 기반으로 EA 성과평가를 위한 업무, 고객, 프로세스, 인적자본 및 기술의 5개 영역으로 구성된 성과평가 모델을 제안하였다. 제안한 모델의 검증을 위해 3개 기관에 적용하여 각 기관의 EA 성과를 평가하였고, 평가 결과를 검증하기 위해 범정부 EA성숙도 모델의 성과평가 영역과도 비교 평가하였다. 또한, 제안한 성과평가모델의 측정지표를 기존의 EA성숙도 모델 및 성과참조모델과도 비교 분석하였다. 이러한 비교 분석 결과를 바탕으로 제안한 성과평가모델을 검증하였다. Korean government has operated EA by the act on efficient introduction of information system and operation, etc. But the evaluation system for EA and the criteria don't prepare well. Particularly, There is no model for EA performance measurement and the way is insufficient. In this study, we derived 8 areas and 17 criteria for the performance evaluation based on the Performance Reference Model of U.S FEA and Korea. And we also derived 8 areas and 10 criteria for it based on the OMB EA Assessment Framework and the EA maturity model in Korea. We propose the performance evaluation model of the five areas that consists of the business performance, customer performance, process, human resource and the technology for EA performance evaluation. To verify the model, we applied the model to three organizations and evaluated EA performance. In addition, we compared the performance result with the performance evaluation area of EA maturity model of Korea to verify the result. We also analyzed the criteria of the proposed performance evaluation model with the current EA maturity model and Performance Reference Model of Korea. As a result of the evaluation, we verified of the proposed performance evaluation model, too.

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

이석균,김동아,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+는 실행시간 측면에서 기존 알고리즘들과 유사하나 대응효율성에 기반한 대응과정의 개선을 통해 두 문서 간의 노트들의 대응률을 향상시킨 알고리즘이다.

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.

공간 데이터에 대한 최근접 질의 처리에 관한 연구

이석균 단국대학교 1999 論文集 Vol.34 No.-

삽입/삭제 편집연산 기반의 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.

공간 데이터에 대한 최근접 질의 처리에 관한 연구

이석균,류승환 단국대학교 1999 論文集 Vol.34 No.-

In spatial database systems, various kinds of queries exist. A frequent type of queries in spatial database systems is the query to find nearest neighbors. Many studies have been performed on processing such queries, and one representative work, which uses index structure of R-tree family, is 「Nearest Neighbor Queries」 by Roussopoulos. However, the algorithm proposed by Roussopoulos has suffered perfomance decrease during searching, since his algorithm does not utilize all the information on the nodes already visited. In this paper, in order to resolve this problem, we present an improved algorithm to find nearest neighbors using a global priority queue. Finally, by experimenting these algorithms on various test data, we show that the performance of our improved algorithm is superior to the Roussopoulos's algorithm.

데이터 제공원의 신뢰도를 고려한 확장관계형 데이터 모델

이석균,정철용,서용무 한국경영정보학회 1997 한국경영정보학회 학술대회논문집 Vol.1997 No.-

연어

이석균 고요아침 2017 열린시학 Vol.22 No.3