파급

이석균 상상인 2023 상상인 Vol.- No.6

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

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

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

이석균,류승환 단국대학교 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.

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

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.

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

이석균,엄현민 한국산업정보학회 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.

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

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

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

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

전문대학교 도서관 독서프로그램 연구-G대학교 도서관 북클럽 ‘가야(GAYA)’를 중심으로

이석균 한국교양교육학회 2023 교양교육연구 Vol.17 No.3

Under the task of cultivating professionals, the imbalance between vocational education and liberal arts education is deepening. In addition, compared to university libraries, the number of college libraries operating reading programs is small, and related research is lacking. Therefore, this study presents a library-centered reading program model for junior colleges and examines it through actual cases. The environment, readers, and cultural characteristics of junior colleges were examined, and a reading program that integrated reading and writing was constructed based on Mikhail Bakhtin's “dialogueism”. The reading program was designed according to the pre-, middle-, and post-reading stages, and was applied in the library of G College, after which the case studies were analyzed. The differences and significance of this study are as follows. First, a library-centered liberal arts reading program was presented at a junior college where vocational education was the main focus. Second, a reference model for the library reading program of colleges was presented. Lastly, the need for competence among college librarians tasked with educating students in reading was presented. 전문대학교는 전문직업인 양성이라는 과제 아래 직업교육과 교양교육의 불균형이 심화되고 있다. 또한 4년제 대학도서관과 비교해서 인력, 예산 부족 등의 이유로 독서프로그램을 운영하고 있는 전문대학교 도서관의 수가 적으며, 이와 관련된 연구도 부족하다. 이에 본 연구는 전문대학교 도서관 중심 독서프로그램 모델을 제시하여 실제 사례를 통해 추진 방안 및 교육적 의의를 살펴보고자 한다. 전문대학교의 환경, 독자, 문화 특성을 살펴보고, 미하일 바흐친의 대화주의를 기반으로 읽기와 쓰기를 통합한 독서프로그램을 구성하였다. 독서프로그램은 독서 전, 중, 후 단계에 맞추어 설계되었으며, 텍스트를 읽고 쓰기로 응답하는 과정에서 인성을 함양시킬 수 있도록 구성하였다. 이를 G대학교 도서관에 실제 적용하였고, 사례를 분석하였다. 프로그램 참여 학생들은 문학 텍스트를 기반으로 삶과 인간에 대한 질문에 자신만의 의미를 담아 응답적 글쓰기로 답하였다. 학생들의 글에는 동일시, 재형상화, 가치관 형성, 위로·공감, 도식화, 사회적 상상력 등 적극적이고 능동적인 이해가 담겨 있었다. 학생들은 텍스트를 포함하면서, 텍스트를 넘는 의미를 재생산하였다. 이러한 응답적 이해는 주제를 내면화하고, 인성 함양에 도움을 주었다. 본 연구의 차별점 및 의의는 다음과 같다. 첫째, 직업교육이 주를 이루는 전문대학교에서 도서관이 중심이 된 교양교육 독서프로그램 참고모델을 제시하였다. 둘째, 전문대학교 도서관 독서프로그램 실제 사례 분석을 통해 추진 방안 및 교육적 의의를 제시하였다. 셋째, 대학도서관 사서의 독서교육자로서의 역량 필요성을 제시하였다.