데이터 재사용을 고려한 효율적인 연속 서브 그래프 매칭 기법

최도진,복경수,유재수 한국정보과학회 2019 정보과학회논문지 Vol.46 No.8

With an increase in the utilization of graph streams in various applications, a continuous subgraph matching scheme is required to search the subgraphs that undergo changes in real time. In this paper, we propose an efficient continuous subgraph matching scheme that reuses indexing and performs distributed processing in graph stream environments. In order to perform distributed processing, we propose a query decomposition method based on the degree and subsequently manage the decomposed subqueries as an index. The proposed scheme reuses indexing information to reduce the load on the index caused by the environment in which multiple queries are entered. We also conduct query allocation through a cost model that calculates the indexing load of each server. For efficient performance of distributed processing in stream environments, the proposed scheme was implemented in Storm. Various performance evaluations were conducted to demonstrate the superiority of the proposed scheme. 다양한 응용에서 그래프 스트림에 대한 활용이 증가됨에 따라 실시간으로 변화되는 서브 그래프를 탐색하기 위해서는 연속 서브 그래프 매칭 기법이 필요하다. 본 논문에서는 그래프 스트림에서의 색인 재사용과 분산 처리가 가능한 효율적인 연속 서브 그래프 매칭 기법을 제안한다. 서브 그래프 매칭 질의를 분산 처리하기 위해 차수 기반의 질의 분할 기법을 제안하고 그래프 스트림을 분할된 질의 기반으로 색인한다. 다수의 질의가 입력되는 환경에서 야기되는 색인의 부하를 감소시키기 위해서 색인 정보를 재사용한다. 또한, 각 서버의 색인 부하를 계산하는 비용 모델을 통해 질의 할당을 수행한다. 제안하는 기법은 스트림 환경에서 효율적인 분산 처리를 수행하기 위해 스톰에서 구현된다. 우수성을 입증하기 위해 다양한 성능 평가를 수행한다.

이종 학술 문헌 사이트 기반 동명이인 판별 기법

최도진,장준혁,김윤아,송상호,김상혁,임종태,김종훈,복경수,유재수 한국콘텐츠학회 2023 한국콘텐츠학회논문지 Vol.23 No.3

현재 서비스 중인 학술 문헌 사이트는 이미 무수히 많은 연구결과물을 가지고 있기 때문에 같은 이름을 가진 동명이인이 흔하게 존재한다. 이러한 상황에서 학술 문헌 사이트에서 어떠한 연구결과물을 찾기 위해 연구자의 이름이나 문서의 키워드로 검색을 할 때 찾고자 하는 연구자의 모든 연구결과물을 한 번에 찾기가 쉽지 않다. 본 논문에서는 이종의 학술 문헌 사이트에 저장되어 있는 모든 연구결과물을 기반으로 동명이인 판별 기법을 제안한다. 제안하는 기법은 학술 문헌 사이트에서 제공하는 데이터를 통합하여 수집하고, 수집한 데이터에서 동명이인 판별에 필요한 속성을 이용하여 군집 분석 기법으로 동명이인을 판별한다. 마지막으로 제안하는 기법의 우수성을 입증하기 위해 성능 평가를 수행한다. 비교 성능 평가 수행 결과 기존의 규칙 기반 기법, 심층학습 기법보다 우수한 F1-Score를 보이며 동명이인 판별에 가장 적합한 기법임을 나타내었다. 학술 문헌 사이트에서 동명이인으로 인한 불편함이 해소될 것으로 기대한다.

대용량 그래프 스트림 환경에서 데이터 재사용을 고려한 근사 Top-k 서브 그래프 매칭 기법

최도진,복경수,유재수 한국콘텐츠학회 2020 한국콘텐츠학회논문지 Vol.20 No.8

With the development of social network services, graph structures have been utilized to represent relationships among objects in various applications. Recently, a demand of subgraph matching in real-time graph streams has been increased. Therefore, an efficient approximate Top-k subgraph matching scheme for low latency in real-time graph streams is required. In this paper, we propose an approximate Top-k subgraph matching scheme considering data reuse in graph stream environments. The proposed scheme utilizes the distributed stream processing platform, called Storm to handle a large amount of stream data. We also utilize an existing data reuse scheme to decrease stream processing costs. We propose a distance based summary indexing technique to generate Top-k subgraph matching results. The proposed summary indexing technique costs very low since it only stores distances among vertices that are selected in advance. Finally, we provide k subgraph matching results to users by performing an approximate Top-k matching on the summary indexing. In order to show the superiority of the proposed scheme, we conduct various performance evaluations in diverse real world datasets. 소셜 네트워크 서비스의 발전과 함께 다양한 응용에서 객체 간의 관계를 표현하기 위한 그래프 자료구조가 자주 활용되고 있다. 최근에는 실시간 그래프 스트림에서 서브 그래프 매칭의 요구가 늘어나고 있다. 따라서 실시간 그래프 스트림에서 높은 응답성을 위한 효율적인 근사 Top-k 매칭 기술이 필요하다. 본 논문에서는 그래프 스트림 환경에서 데이터 재사용을 고려한 근사 Top-k 서브 그래프 매칭 기법을 제안한다. 제안하는 기법은 대용량 스트림을 효율적으로 처리하기 위해서 기존 분산 스트림 처리 플랫폼인 스톰을 활용하고 스트림 처리 비용을 감소시키기 위한 기존 데이터 재사용 방법을 활용한다. Top-k 결과 생성을 위해서 거리 기반의 요약 색인 기법을 제안한다. 제안하는 요약 색인은 사전에 선택된 정점 간의 거리 값만을 저장하기 때문에 색인의 부하가 적다. 제안하는 요약 색인에서의 근사 Top-k를 수행하여 사용자에게 근사한 k개의 결과를 제공한다. 제안하는 기법의 우수성을 입증하기 위해 다양한 실세계 그래프 데이터 집합에서의 성능 평가를 수행한다.

워드 임베딩 기반 근사 Top-k 레이블 서브그래프 매칭 기법

최도진,오영호,복경수,유재수 한국콘텐츠학회 2022 한국콘텐츠학회논문지 Vol.22 No.8

지식 그래프 및 단백질 상호 작용과 같은 실제 데이터에서 개체들과 개체들의 관계 및 구조를 나타내기 위해 레이블 그래프를 사용한다. IT의 급속한 발전과 데이터의 폭발적인 증가로 사용자에게 관심 있는 정보를 제공하기 위한 서브 그래프 매칭 기술이 필요하다. 본 논문은 레이블의 의미적 유사성과 그래프 구조 차이를 고려한 근사 Top-k 서브 그래프 매칭 기법을 제안한다. 제안하는 기법은 레이블 의미적 유사도를 고려하기 위하여 FastText을 활용한 학습 모델을 이용한다. 레이블 간 의미적 유사도를 미리 계산한 LSG(Label Similarity Graph)를 통해 처리 속도의 효율을 높인다. LSG를 통해 레이블이 정확하게 일치해야 확장이 가능한 기존 연구의 한계를 해결한다. 2-hop까지 탐색을 수행함으로써 질의 그래프에 대한 구조적 유사성을 지원한다. 매칭된 서브 그래프는 유사도 값 기반으로 Top-k 결과를 제공한다. 제안하는 기법의 우수성을 보이기 위하여 다양한 성능평가를 수행한다. Labeled graphs are used to represent entities, their relationships, and their structures in real data such as knowledge graphs and protein interactions. With the rapid development of IT and the explosive increase in data, there has been a need for a subgraph matching technology to provide information that the user is interested in. In this paper, we propose an approximate Top-k labeled subgraph matching scheme that considers the semantic similarity of labels and the difference in graph structure. The proposed scheme utilizes a learning model using FastText in order to consider the semantic similarity of a label. In addition, the label similarity graph(LSG) is used for approximate subgraph matching by calculating similarity values between labels in advance. Through the LSG, we can resolve the limitations of the existing schemes that subgraph expansion is possible only if the labels match exactly. It supports structural similarity for a query graph by performing searches up to 2-hop. Based on the similarity value, we provide k subgraph matching results. We conduct various performance evaluations in order to show the superiority of the proposed scheme.

스파크 환경에서 내용 기반 이미지 검색을 위한 효율적인 분산 인-메모리 고차원 색인 기법

최도진,박송희,김연동,위지원,이현병,임종태,복경수,유재수 한국정보과학회 2020 정보과학회논문지 Vol.47 No.1

Content-based image retrieval that searches an object in images has been utilizing for criminal activity monitoring and object tracking in video. In this paper, we propose a high-dimensional indexing scheme based on distributed in-memory for the content-based image retrieval. It provides similarity search by using massive feature vectors extracted from images or objects. In order to process a large amount of data, we utilized a big data platform called Spark. Moreover, we employed a master/slave model for efficient distributed query processing allocation. The master distributes data and queries. and the slaves index and process them. To solve k-NN query processing performance problems in the existing distributed high-dimension indexing schemes, we propose optimization methods for the k-NN query processing considering density and search costs. We conduct various performance evaluations to demonstrate the superiority of the proposed scheme. 영상에서 범죄 행위 모니터링 및 추적을 위해서 이미지 내에 포함된 객체를 검색하는 내용 기반 검색이 활용되고 있다. 본 논문에서는 내용 기반 이미지 검색을 위해 이미지 또는 객체에서 추출한 대용량 특징 벡터를 이용한 유사도 검색을 지원하는 분산 인-메모리 기반 고차원 색인 기법을 제안한다. 대용량 분산 처리를 위해 빅데이터 플랫폼인 스파크를 활용하고 효율적인 분산 질의 처리 할당을 위해 마스터/슬레이브 모델을 활용한다. 마스터에서는 데이터 및 질의 분배를 수행하고 슬레이브에서는 데이터를 색인한다. 더불어 기존 분산 고차원 색인 기법에서 k-최근접 질의 처리의 성능 문제를 해결하기 위해서 밀집도 및 탐색 비용을 고려한 k-최근접 질의 최적화 기법을 제안한다. 제안하는 기법의 우수성 및 타당성을 입증하기 위해 다양한 성능 평가를 수행한다.

알저네이트 및 카이틴 고정화 Zymomonas mobilis 에 의한 쏠비톨의 연속생산

최도진,김원극전억한 한국생물공학회 1990 KSBB Journal Vol.5 No.3

Ethanol을 주로 생산하는 균주인 Z. mobilis의 cell wall 투과성을 높인 후 고정화하여 sorbitol 생산에 이용 하였다. 그러나, toluene으로 투과성을 높은 cell은 oxidoreductase의 유출, 손실로 인하여 sorbitol conversion efficency가 급격히 저하되었다. 따라서, 이와같은 enzymcd의 유출을 방지 하기 위하여, 투과성을 향상시킨 cell을 0.25% glutaraldehyd로 처리한 후 alginate와 chitin에 고정화하여 회석율 $0.2h^{-1}$에서 연속배양을 한 결과 210시간동안 효소활성도의 저하는 거의 일어나지 않았다. 이와같은 연속배양에서 얻어진 sorbitol productivity는 3.5g / l-h로 측정 되었다. This study describes the sorbitol production with permeabilized cells of Zymomonas mobilis immobilized in Ca-alginate. Toluene treated cells lose glucose-fructose oxidoreductase activity due to leaking of enzyme from the cells. In order to prevent this leakage, the permeabilized cells were immobilized in alginate and chitin. No significant loss of enzyme activity was apparent during 210h operation in a continuous process. The productivity of the continuous process was estimated to be about 3.5g/l -h for sorbitol at dilution rate $0.2h^{-1}$.

Concurrency Control Method to Provide Transactional Processing for Cloud Data Management System

최도진,송석일 한국콘텐츠학회 2016 International Journal of Contents Vol.12 No.1

As new applications of cloud data management system (CDMS) such as online games, cooperation edit, social network, and so on, are increasing, transaction processing capabilities for CDMS are required. Several transaction processing methods for cloud data management system (CDMS) have been proposed. However, existing transaction processing methods have some problems. Some of them provide limited transaction processing capabilities. Some of them are hard to be integrated with existing CDMSs. In this paper, we proposed a new concurrency control method to support transaction processing capability for CDMS to solve these problems. The proposed method was designed and implemented based on Spark, an in-memory distributed processing framework. It uses RDD (Resilient Distributed Dataset) model to provide fault tolerant to data in the main memory. In our proposed method, database stored in CDMS is loaded to main memory managed by Spark. The loaded data set is then transformed to RDD. In addition, we proposed a multi-version concurrency control method through immutable characteristics of RDD. Finally, we performed experiments to show the feasibility of the proposed method.

분산 고차원 거리 기반 색인에서 기계 학습을 활용한 k-최근접 질의 최적화

최도진(Dojin Choi),위지원(Jiwon Wee),김연동(Yeondong Kim),이현병(Hyeonbyeong Lee),임종태(Jongtae Lim),복경수(Kyoungsoo Bok),유재수(Jaesoo Yoo) 한국정보과학회 2019 한국정보과학회 학술발표논문집 Vol.2019 No.12

학술 문헌 기반 동명이인 처리 연구 동향 분석

최도진(Choi do-jin),장준혁(Jang jun-hyeok),송상호(Song sang-ho),오영호(Oh young-ho),RETITI DIOP EMANE Christopher,김상혁(Kim sang-hyeuk),이서희(Lee seo-heui),정상준(Chung sang-jun),전종우(Jeon jong-woo),김종훈(Kim jong-hun),복경수 한국콘텐츠학회 2022 한국콘텐츠학회 종합학술대회 논문집 Vol.2022 No.7

학술 빅데이터 기반 연구 그룹 분석 시스템 설계

최도진(Choi do-jin),복경수(Bok kyoung-soo),유재수(Yoo jae-soo) 한국콘텐츠학회 2022 한국콘텐츠학회 종합학술대회 논문집 Vol.2022 No.7