XML 데이타 색인을 위한 경로 분할 기법

김종익(Jongik Kim),김형주(Hyoung-Joo Kim) 한국정보과학회 2004 정보과학회논문지 : 데이타베이스 Vol.31 No.3

XML에 대한 질의 언어는 데이타 그래프 내의 경로를 이용하여 질의를 표현한다. 특히, 경로에 패턴 (예를 들어, 정규식)을 사용함으로써, 데이타의 구조를 정확히 알지 못하더라도 질의가 가능하도록 한다. 이때, 패턴을 이용하는 질의는 데이타 그래프의 탐색범위를 크게 넓히게 된다. 기존의 XML색인 기법은 질의의 탐색범위를 줄이기 위해 데이타 그래프 내의 서로 동일한 경로들을 하나로 묶어 작은 크기의 색인 그래프를 생성하는 방법을 이용한다.. 하지만 이러한 색인들은 많은 경우 색인의 크기가 데이타 그래프의 크기만큼 증가하게 되어 질의의 탐색범위를 줄이지 못하고, 따라서 효율적인 질의 처리를 보장하지 못한다. 본 논문에서는 데이타 내에 존재하는 모든 경로를 분할(partitioning)하고 질의 처리시 질의에 맞는 분할 영역을 빠르게 찾아낼 수 있는 색인 그래프를 제안한다. 본 논문에서 제안하는 색인 그래프는 데이타 그래프의 크기와 상관없이 색인 그래프의 크기를 조절할 수 있다. 따라서 색인 그래프의 크기를 작게 구성함으로써 색인 그래프 탐색 비용을 크게 줄일 수 있다. 본 논문에서는, 실험을 통해 기존의 그래프 기반 색인 기법들보다 본 논문의 색인 기법이 보다 효율적임을 보이고 색인의 크기 변화에 따른 성능 변화에 대해 알아본다. Query languages for XML use paths in a data graph to represent queries. Actually, paths in a data graph are used as a basic constructor of an XML query. User can write more expressive queries by using patterns (e.g. regular expressions) for paths. There are many identical paths in a data graph because of the feature of semi-structured data. Current researches for indexing XML utilize identical paths in a data graph, but such an index can grow larger than source data graph and cannot guarantee efficient access path. In this paper we propose a partitioning technique that can partition all the paths in a data graph. We develop an index graph that can find appropriate partitions for a path query efficiently. The size of our index graph can be adjusted regardless of the source data. So, we can significantly improve the cost for index graph traversals. In the performance study, we show our index much faster than other graph based indexes.

텔레매틱스 서비스 시스템의 설계 및 구현

김종익(Jongik Kim),김철수(Chulsu Kim),윤대섭(Daesub Yoon),한우용(Woo-Yong Han),권오천(Oh-Cheon Kwon) 한국정보과학회 2005 한국정보과학회 학술발표논문집 Vol.32 No.2

최근 인터넷의 성장과 CDMA등의 무선 통신의 활성화로 인하여 이동 중인 차량 내에서 다양한 정보를 사용하기 위한 기술이 개발 중이다. 본 논문에서는 차량 단말에 여러가지 텔레매틱스 서비스를 제공하기 위한 차량 단말, 텔레매틱스 서비스 서버, 텔레매틱스 컨텐츠 서버의 3단계 구조를 가지는 텔레매틱스 서비스 시스템을 제안한다. 제안하는 시스템은 차량 단말과 서비스 서버 사이의 통신 방법 및 서비스 서버 내의 서비스 응용이 다양한 컨텐츠를 제공하기 위한 프레임워크를 제공한다.

가변길이 그램의 역리스트 생성을 이용한 효율적인 유사 문자열 검색 기법

김종익(Jongik Kim) 한국정보과학회 2016 정보과학회논문지 Vol.43 No.11

유사 문자열 검색을 위해 기존의 기법들은 우선 후보 문자열 집합을 생성한 후에 후보 문자열을 검증하는 방법을 사용한다. 이때, 유사 문자열 검색의 성능을 결정짓는 가장 중요한 요소는 후보 생성방법이다. 기존의 기법들은 질의 문자열로부터 고정길이 q-그램들을 선택하고, 선택된 q-그램에 해당하는 역리스트를 이용해 후보 문자열을 생성한다. 본 논문에서는 질의 문자열 내의 가변길이 그램들을 사용하여 후보 문자열을 생성할 수 있는 기법과 질의 문자열로부터 최적의 가변길이 그램들의 조합을 선택하는 동적 프로그래밍 알고리즘을 제안한다. 실험을 통해 제안하는 기법이 기존의 기법들 보다 유사 문자열 검색의 성능을 향상시킴을 보인다. Existing techniques for string similarity search first generate a set of candidate strings and then verify the candidates. The efficiency of string similarity search is highly dependent on candidate generation methods. State of the art techniques select fixed length q-grams from a query string and generate candidates using inverted lists of the selected q-grams. In this paper, we propose a technique to generate candidates using variable length grams of a query string and develop a dynamic programming algorithm that selects an optimal combination of variable length grams from a query string. Experimental results show that the proposed technique improves the performance of string similarity search compared with the existing techniques.

레벨 정보를 이용한 효과적인 구조 조인 기법

김종익(Jongik Kim) 한국정보과학회 2008 정보과학회 컴퓨팅의 실제 논문지 Vol.14 No.6

구조 조인은 XML 경로 질의를 처리하기 위한 대표적인 방법 중의 하나이다. 최근의 연구에서는 B+트리 등에 색인된 가로 방향의 엘리먼트 분포 정보를 이용하여 조인 결과에 포함되지 않는 엘리먼트들을 조인 연산에서 배제하는 방법에 초점을 맞추고 있다. 하지만, 이러한 방법은 조인 연산 자체가 매우 복잡해지며 분포 정보를 위한 색인의 부담으로 항상 좋은 성능을 보장하지는 못한다. 본 논문에서는 레벨 정보를 이용하여 조인 결과에 참여하지 못하는 엘리먼트들을 효과적으로 걸러내는 구조 조인 기법을 제안한다. 제안하는 기법의 레벨 정보는 엘리먼트의 세로방향의 분포정보라는 점에서 기존의 기법과 차별화되며 조인 연산을 위한 별도의 색인을 필요로 하지 않는다는 장점을 가진다. 본 논문에서는 실험을 통하여 제안된 기법의 효율성을 보인다. Structural join is one of the most typical techniques for evaluating XML path queries. Recent researches for structural joins focus on techniques of skipping unnecessary elements using the horizontal distribution information of elements that is indexed on a structure like B+ tree. However, those techniques make the structural join complicated and cannot guarantee efficient join processing due to the overhead of an index structure. In this paper, we propose a new structural join technique that exploits the level information of XML elements. Our technique can skip unnecessary elements using level information, which is vertical distribution information of elements. Through the experimental results, we show that our technique can evaluate structural joins efficiently.

자동적인 몸체모델 생성과 눈깜박임 정보를 이용한 자동 비디오객체 추출시스템

김종익(JongIk Kim),김진상(Jinsang kim),조원경(Won-Kyung Cho) 한국통신학회 2004 한국통신학회 학술대회논문집 Vol.2004 No.11

모델변환을 이용한 의미있는 비디오객체 추출방법

김종익(JongIk Kim),김진상(Jinsang kim),조원경(Won-kyung Cho) 한국통신학회 2004 한국통신학회 학술대회논문집 Vol.2004 No.7

XDBox : XML 객체 저장소의 구현

김종익(Jongik Kim),최일환(Ilhwan Choi),이현숙(Hyun-Sook Lee),김형주(Hyoung-Joo Kim) 한국정보과학회 2003 한국정보과학회 학술발표논문집 Vol.30 No.1A

XML은 반 구조 데이터(semi-structured data)의 일종으로 데이터들이 정형화된 구조를 가지고 있지 않다는 것이 특징이다. 기존의 데이터베이스 시스템은 고정된 스키마를 통해 데이터를 저장 관리하기 때문에 정형화된 구조를 가지지 않는 XML 문서를 저장하기에는 한계가 있다. 본 논문에서는 정형화된 구조를 가지지 못하는 XML 문서를 효과적으로 저장하고 관리할 수 있는 저장장치를 구현하고 구현 사항에 대해 설명한다. 본 논문의 저장 장치는 XML을 DOM트리로 표현한 후 DOM트리의 각 노드를 객체로 만들어 저장한다. 본 논문의 저장 장치는 다중 사용자를 지원하기 위해 클라이언트 서버 구조로 구성되어 있으며 각 객체는 전용 파일, 관계형 시스템의 LOB등 다양한 하부 구조에 저장될 수 있다.

효율적인 유사 문자열 검색을 위한 클러스터링 기법

김종익(Jongik Kim) 한국정보과학회 2011 정보과학회 컴퓨팅의 실제 논문지 Vol.17 No.7

유사 문자열 검색은 오류를 포함할 수 있는 텍스트 데이터에서 필수적이라 할 수 있다. 유사 문자열 검색을 위해 제안된 대부분의 알고리즘들은 길이가 매우 긴 역리스트들을 병합하는 연산을 수행한다. 본 논문에서는 역리스트 병합 범위를 줄이기 위해 역리스트 내에 존재하는 문자열의 분포와 빈도를 이용하는 문자열 데이터 클러스터링 기법을 제안한다. 또한, 클러스터 별 역리스트를 효과적으로 추출할 수 있는 분할 역색인을 제안한다. 본 논문에서는 실험을 통해 기존 병합 알고리즘들이 클러스터 별로 역리스트를 병합함으로써 역리스트의 탐색범위를 크게 줄이고 이에 따라 성능이 크게 향상되는 것을 보인다. Similarity searches are indispensible to string data because string data often contain errors by nature. Many techniques for string similarity searches are based on merging inverted lists. In this paper, we propose a clustering technique for string data by exploiting the distribution and frequency of strings in inverted lists. We also propose a partitioned inverted index to effectively retrieve a group inverted lists from clusters. Experimental results show that the proposed technique improves existing algorithms significantly.

경로 식별자를 이용한 다중 정규경로 처리기법

김종익(Jongik Kim),정태선(Tae-Sun Chung),김형주(Hyoung-Joo Kim) 한국정보과학회 2002 정보과학회논문지 : 데이타베이스 Vol.29 No.4

XML에 대한 질의는 데이타 그래프 내의 경로에 대한 질의를 기반으로 하며 그래프 내의 임의의 경로를 표시하기 위해 정규식을 사용한다. 일반적으로 의미있는 질의를 표현하기 위해서는 질의 내에 여러 개의 정규식을 포함하는 경우가 많다. 그럼에도 불구하고 기존의 연구는 주로 단일 정규식으로 이루어진 질의의 최적화 방법을 다루고 있다. 본 논문에서는 데이타 그래프를 탐색하지 않고 다중 정규 경로 질의를 처리할 수 있는 방법을 제시한다. 본 논문에서는 다중 정규 경로를 효율적으로 처리하기 위해서 데이타 그래프 상의 임의의 두 노드 사이에 경로가 존재하는지를 직접 알 수 있는 방법인 경로 식별자를 제안하고 경로 식별자를 만드는 방법을 제공한다. 또한 본 논문에서 제안된 방법을 구현하여 그 성능에 대한 결과를 제공한다. Queries on XML are based on paths in the data graph, which is represented as an edge labeled graph model. All proposed query languages for XML express queries using regular expressions to traverse arbitrary paths in the data graph. A meaningful query usually has several regular path expressions in it, but much of recent research is more concerned with optimizing a single path expression. In this paper, we present an efficient technique to process multiple path expressions in a query. We developed a data structure named as the path identifier(PID) to identify whether two given nodes lie on the same path in the data graph or not, and utilized the PID for efficient processing of multiple path expressions. We implement our technique and present preliminary performance results.

한강 살리기 4공구 여주보가 지역 환경에 미치는 영향에 관한 문헌적 고찰

김종익(Jongik Kim),이태관(Taegwan Lee) 계명대학교 낙동강환경원 2010 環境科學論集 Vol.14 No.1

The 4 major rivers restoration plan of South Korea was first announced as a part of the “Green New Deal” policy. Yeoju weir, which is constructed under this restoration plan, is to provide water security, maintain the level of water depth, and prevent flood control. Yeoju weir also pursues regional development centered on rivers that elevates local economical growth, regional culture, and quality of life. However, there is a possibility that Hyohongneung and Sejongneung which are Joseon-era royal tombs alongside a Yeoju county would be damaged and as a result, those neung-type tombs would be negated by UNESCO World Heritage Site. Moreover, a slower flow velocity deteriorates the water quality, and the increased ground water level overflows or forms its surroundings wetlands. Therefore, after weir construction, it is necessary to provide fundamental resolution of floods and water scarcity and to secure the status of two tombs as they are under UNESCO policy.