그래프 스트림 환경에서 효율적인 연속 서브 그래프 매칭 기법 :Efficient continuous subgraph matching schemes in graph stream environments

최도진

추천

검색

자료유형: 학위논문

저자정보: 최도진 (충북대학교, 忠北大學校)

지도교수: 柳哉秀

발행연도: 2020

저작권: 충북대학교 논문은 저작권에 의해 보호받습니다.

이용수5

이 논문의 연구 히스토리 (9)

2023

대용량 그래프 스트림 환경에서의 효율적인 서브 그래프 매칭 기법

최도진 , 유재수 한국콘텐츠학회 종합학술대회 논문집 2023.05 학술대회자료

2022

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

최도진 , 오영호 , 복경수 외 1명 한국콘텐츠학회논문지 2022.08 학술저널

2021

효율적인 서브 그래프 매칭을 위한 색인 특성 기반 캐시 교체 기법

최도진 , 이소민 , 복경수 외 1명 한국콘텐츠학회 종합학술대회 논문집 2021.08 학술대회자료

2020

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

최도진 , 복경수 , 유재수 한국콘텐츠학회논문지 2020.08 학술저널

그래프 스트림 환경에서 효율적인 연속 서브 그래프 매칭 기법

최도진 2020.01 학위논문

2019

간선 유형 및 가중치를 고려한 연속 서브 그래프 매칭 기법

최도진 , 복경수 , 이병엽 외 1명 한국콘텐츠학회 종합학술대회 논문집 2019.05 학술대회자료

그래프 스트림에서 효율적인 근사 Top-k 서브 그래프 매칭 기법

최도진 , 복경수 , 유재수 한국콘텐츠학회 종합학술대회 논문집 2019.05 학술대회자료

2018

분산 스트림 처리 환경에서 연속적인 서브 그래프 매칭기법

최도진 , 김민영 , 복경수 외 1명 한국정보과학회 학술발표논문집 2018.12 학술대회자료

그래프 스트림에서 효율적인 연속 서브 그래프 매칭 기법

최도진 , 복경수 , 유재수 한국정보과학회 학술발표논문집 2018.06 학술대회자료

이 논문의 후속연구가 궁금하신가요?
연관 학술논문 또는 학술발표를 통해 보다 발전된 연구결과를 확인하실 수 있습니다.
이 논문의 연구 히스토리 확인하기

초록· 키워드

오류제보하기

소셜 네트워크 서비스의 발전과 함께 다양한 응용에서 객체 간의 관계를 표현하기 위한 그래프 자료구조가 자주 활용되고 있다. 기존의 응용은 그래프 자료구조를 활용하여 가치 있는 정보를 생산하기 위하여 이상 감지, 그래프 클러스터링, 서브 그래프 매칭과 같은 그래프 분석 기법을 활용한다. 그래프 분석의 복잡도를 해결하기 위해서 그래프 분석 기법에 대한 최적화 연구가 활발하게 진행되고 있다. 본 논문에서는 그래프 스트림 환경에서 효율적인 연속 서브 그래프 매칭 기법을 제안한다. 제안하는 기법에서는 연속 Exact 서브 그래프 매칭과 연속 근사 Top-k 서브 그래프 매칭 질의를 다룬다.
첫 번째, 본 논문에서는 효율적인 분산 연속 서브 그래프 매칭 기법을 제안한다. 제안하는 기법은 대용량 스트림을 효율적으로 처리를 위해서 기존 분산 스트림 처리 플랫폼을 활용하고, 분산 서브 그래프 매칭을 위해 질의 분할 방법, 질의 할당 방법을 제안한다. 그래프의 차수 특성을 활용하여 질의를 분할하고, 분할된 질의를 분산 노드에 할당하여 질의를 분산하여 처리한다. 질의 할당은 분산 처리 시스템에서 특정 노드에 부하가 발생하는 상황을 발생시키지 않기 위하여, 각 노드의 스트림 처리 부하, 색인 부하를 고려한다.
두 번째, 본 논문에서는 불필요한 색인 및 스트림 처리 비용을 감소시키기 위한 색인 재사용 및 선택적 색인 방법을 제안한다. 유사한 서브 그래프 매칭 질의가 자주 발생하면, 각 질의에 대한 결과를 생성하기 위해서 서로 다른 색인을 구축하는 경우가 태반이다. 동일한 데이터에 대한 불필요한 색인은 서버의 부하를 야기한다. 제안하는 기법에서는 유사한 질의에 대한 검사를 수행하여, 기존 색인에 질의 목록에 추가하여 색인 부하를 감소하는 방법을 제시한다. 또한, 질의와 관련된 스트림만을 관리하여 스트림 처리 비용을 감소시킨다.
세 번째, 본 논문에서는 질의의 다양성을 제공한다. 기존 연구에서는 서브 그래프 매칭의 제약 조건으로 레이블, 가중치, 방향성 중 일부만 지원하는 질의를 제안하였다. 제안하는 기법에서는 레이블과 가중치, 그래프의 편집 거리 및 가중치 차이에 대한 연산(+,-,=,*)을 제공하여 사용자에게 질의에 대한 다양성을 제공한다.
마지막으로, 본 논문에서 효율적인 근사 연속 Top-k 서브 그래프 매칭 기법을 제안한다. 제안하는 근사 Top-k 서브 그래프 매칭 기법은 질의와 데이터 그래프 간의 차이 (레이블, 가중치, 편집 거리)를 기반으로 차이가 적은 순으로 k개의 결과를 제공한다. 질의 처리 비용 감소 및 응답성 높은 질의 처리를 수행하기 위해서 정확한 Top-k 개를 생성하지 않고, 근사한 k개의 결과를 제공한다.
제안하는 기법의 우수성을 입증하기 위해 다양한 실세계 그래프 데이터 집합에서의 성능 평가를 수행한 결과 제안하는 기법이 기존 기법보다 우수한 성능을 보였다. 성능 평가 결과, 제안하는 기법이 기존 기법에 비해 분산 시스템의 확장성, 질의 확장성, 스트림 처리량 측면에서 우수한 성능을 나타냈다.

With the development of social network services, graph structures have been utilized to represent relationships among objects in various applications. The applications utilize graph algorithms such as an anomaly detection, a graph clustering, a subgraph matching to make valuable information. A studies of optimization of graph algorithms have been actively done to solve complexity problems of graph algorithms. In this thesis, we propose an efficient continuous subgraph matching scheme in graph stream environments. The proposed schemes deal with an exact continuous subgraph matching and an approximate continuous top-k subgraph matching.
First, we propose an efficient distributed continuous subgraph matching scheme. The proposed scheme utilizes existing distributed stream processing platform to handle a large amount of stream data. We also present a query decomposition scheme and a query allocation scheme for distributed subgraph matching. We utilize a degree of graph to decompose queries, and we assign decomposed queries to each nodes to gain distributed processing. In the query decomposition scheme, it considers a stream load and an indexing load of each nodes to avoid a situation which particular node have extreme loads.
Second, we present an index reuse and selective indexing scheme to decrease unnecessary indexing and stream processing cost. When a similar subgraph query frequently occurs, existing subgraph matching schemes construct separate indexes of each query for making each query results. Unnecessary indexes on the same dat cause a load on the server. We propose an index load reduction method by checking similar queries and adding them to the list of queries of existing index. In addition, we manage streams related to queries only to reduce stream processing cost.
Third, we provide a diversity of subgraph query. Existing studies proposed limited query type that provide a query type only one of that such as a label, a weight, and directivity. The proposed method provides diverse query types such as a label, a weight, an edit distance, and an operation of weight difference (+, -, =, *).
Finally, we propose an efficient continuous approximate top-k subgraph matching scheme. The proposed approximate top-k subgraph matching scheme provide k results in the order of smallest difference based on the difference (a label, a weight, and an edit distance) between the query and the data graph. We provide approximated k results to users in order to reduce query processing cost and perform high responsibility of query processing.
In order to show the superiority of the proposed continuous subghraph matching schemes, we compare them with the existing schemes through performance evaluation in diverse real world dataset. As a result, it is shown that the proposed continuous subgraph matching schemes outperforms the existing schemes in terms of the scalability of distributed system, the scalability of query, and stream processing throughput.

Ⅰ. 서 론 1
1. 연구의 필요성 1
2. 연구 목적 및 특징 4
3. 연구의 구성 6
Ⅱ. 관련 연구 7
1. 용어 정의 7
(1) 그래프 정의 7
(2) 서브 그래프 매칭 8
(3) 연속 서브 그래프 매칭 9
(4) 그래프 스트림 10
2. 서브 그래프 매칭 15
(1) 조인 기반 서브 그래프 매칭 15
(2) Path 기반 서브 그래프 매칭 17
3. 실시간 그래프 스트림 기반 서브 그래프 매칭 19
(1) DAG 기반 서브 그래프 매칭 기법 19
(2) Dominate 기반 서브 그래프 매칭 기법 21
(3) 전이 상태 기반 서브 그래프 매칭 기법 24
4. Top-k 서브 그래프 매칭 27
(1) Wei Chen 기법 27
(2) Xiaohuan Shan 기법 29
Ⅲ. 제안하는 연속 서브 그래프 매칭 기법 33
1. 연구 동기 34
2. 전체 시스템 구조도 37
(1) 전체 처리 절차 37
(2) 질의 스트림 처리 절차 42
(3) 질의 유형 59
3. Exact 연속 서브 그래프 매칭 64
(1) 데이터 색인 64
(2) 부분 서브 그래프 매칭 69
(3) 최종 서브 그래프 매칭 77
4. 근사 Top-k 연속 서브 그래프 매칭 80
(1) D_List 82
(2) 초기 서브 그래프 매칭 85
(3) 연속 서브 그래프 매칭 88
(4) Compaction Manager 90
Ⅳ. 성능 평가 92
1. 성능 평가 환경 92
2. Exact 연속 서브 그래프 매칭 기법 94
(1) 색인 할당 방법 성능 평가 94
(2) 질의 처리 방법 성능 평가 97
3. 근사 Top-k 연속 서브 그래프 매칭 105
4. 성능 평가 결과 108
Ⅴ. 결론 및 향후 연구 111
참고문헌 113

최근 본 자료

전체보기

구분	그룹	데이터 항목
AI 학습용 데이터	원문	원문 PDF 파일
AI 학습용 데이터	원문 + 메타 (기본/상세)	원문 PDF 파일 및 서지정보 CSV
대량 구매용 데이터	B2B 구독 방식	특정 자료 한정으로 원문 접근 권한 부여
대량 구매용 데이터	URL 전달 방식	바로 PDF 뷰어를 열람할 수 있는 URL 제공

구분	그룹	데이터 항목
AI 학습용 데이터	기본 메타	발행기관명, 간행물명, 권호명, 권(vol), 호(issue), 통권, 발행연도, 발행월, 논문명, 저자명, 시작페이지, 종료페이지, 전체페이지, 상세페이지URL
상세 메타 데이터	발행기관 메타	발행기관 이명, 영문명, 창립연도, 홈페이지URL, 발행기관 소개
	간행물 메타	부제목, 간행물 유형, ISSN, ISBN, 최초발행연도, 폐간연도, 간행빈도, 발행주기, 등재사항, 이용수, 피인용수, 권호수, 논문수, 표지이미지
	논문 메타	작성 언어, 부제목, 대등제목, 목차, 키워드, 초록, 이미지, 참고문헌, 이용수, 피인용수, 논문활용도, DBpia통합주제분류, KDC분류, DDC분류, 한국연구재단분류, UCI, DOI
	저자 메타	소속기관, 소속부서, 직급, 연구분야, 연구키워드, 이용수, 피인용수, 저자 논문활용도

구분	그룹	데이터 항목
※ 결합형/맞춤형 메타 데이터는 신청 내용에 따라 다양하게 제공 가능
이용순위 정보	주제분야별 많이 이용된 논문	“인문학”에서 많이 이용된 논문 TOP100
	이용기관별 많이 이용된 논문	“중고등학교”에서 많이 이용된 논문 TOP100
	세부기관별 많이 이용된 논문	“서울대학교”에서 많이 이용된 논문 TOP100
	키워드별 많이 이용된 논문	“Chat GPT”에서 많이 이용된 논문 TOP100
키워드 정보	많이 이용된 키워드	특정기간/분야/저널 내 많이 이용된 키워드
	많이 발행된 키워드	특정기간/분야/저널 내 많이 발행된 키워드
	많이 검색된 키워드	특정기간/분야/저널 내 많이 검색된 키워드
	연구 트렌드 키워드	특정 키워드 연관 연구동향 분석 데이터 키워드

논문 기본 정보

이 논문의 연구 히스토리 (9)

초록· 키워드

목차

최근 본 자료

댓글(0)