메뉴 건너뛰기
.. 내서재 .. 알림
소속 기관/학교 인증
인증하면 논문, 학술자료 등을  무료로 열람할 수 있어요.
한국대학교, 누리자동차, 시립도서관 등 나의 기관을 확인해보세요
(국내 대학 90% 이상 구독 중)
로그인 회원가입 고객센터 ENG
주제분류

추천
검색

논문 기본 정보

자료유형
학위논문
저자정보

이소민 (충북대학교, 충북대학교 대학원)

지도교수
유재수
발행연도
2021
저작권
충북대학교 논문은 저작권에 의해 보호받습니다.

이용수4

표지
AI에게 요청하기
추천
검색

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

초록· 키워드

오류제보하기
최근 그래프 데이터는 여러 영역에서 객체들 사이의 관계를 모델링하기 위해 사용되고 있다. 네트워크 기술의 발전과 더불어 소셜 네트워크 서비스의 확산으로 그래프 데이터의 크기는 점차 방대해지고 있으며 그래프 데이터는 실시간으로 변화되면서 입력된다. 따라서 실시간 그래프 스트림 상에서 연속 질의 처리 수행의 필요성이 증가하고 있다. 또한, 실제 응용 환경에서는 메모리 크기가 제한되어 있기 때문에 크기가 큰 그래프 데이터를 모두 메모리에 유지하기 어렵다. 따라서 제한된 메모리 환경을 고려한 연속 서브 그래프 매칭 기법이 필요하다. 본 논문에서는 제한된 메모리 환경에서 그래프 스트림을 효율적으로 처리하기 위한 슬라이딩 윈도우 기반 연속 서브 그래프 매칭 기법을 제안한다. 제안하는 기법은 실체화 뷰 기반의 질의 처리 기법을 활용한다. 제한된 메모리 환경에서 그래프 스트림에 의해 갱신되는 질의 중간 결과들을 효율적으로 관리하기 위해 두 계층 캐싱 기법을 제안한다. 상위 계층에는 자주 활용되는 데이터를 관리하고, 하위 계층에는 다음 질의 처리 시 사용될 가능성이 있는 데이터를 관리한다. 본 논문에서는 효율적인 캐시 교체를 위해 색인 특성 기반의 캐시 교체 기법을 제안한다. 제안하는 캐시 교체 기법은 기존에 제안된 트라이 색인 구조의 효율성을 향상시키기 위해 통계 데이터를 기반으로 한다. 또한, 질의 타입의 다양성을 고려하기 위해 정점 및 간선에 대한 와일드카드 연산을 제공한다. 자체 성능 평가와 비교 성능 평가를 통해 제안하는 기법의 우수성을 입증한다.

목차

Ⅰ. 서 론 1
Ⅱ. 관련 연구 5
1. 실체화 뷰 5
2. 연속 서브 그래프 매칭 기법 8
(1) DAG 기반 연속 서브 그래프 매칭 기법 8
(2) 전이 상태 기반 연속 서브 그래프 매칭 기법 10
(3) 실체화 뷰 기반 연속 서브 그래프 매칭 기법 13
3. 기존 연구의 특징 및 문제점 19
Ⅲ. 제안하는 연속 서브 그래프 매칭 기법 20
1. 전체 시스템 구조도 20
2. 색인 관리자 24
3. 캐시 관리자 28
(1) 두 계층 캐시 28
(2) 캐시 교체 기법 31
4. 질의 처리 관리자 37
(1) 전체 처리 절차 37
(2) 서브 그래프 매칭 처리 39
(3) 연속 서브 그래프 매칭 처리 42
Ⅳ. 성능평가 44
1. 성능평가 환경 44
2. 자체 성능 평가 47
(1) 캐시 교체 기법에 따른 평균 윈도우 처리 시간 47
(2) 캐시 교체 기법에 따른 적중률 비율 49
(3) 캐시 가중치에 따른 평균 윈도우 처리 시간 52
3. 비교 성능 평가 54
(1) 질의 복잡도에 따른 속도 향상 비율 54
(2) 윈도우 크기에 따른 평균 윈도우 처리 시간 비율 57
(3) 스트림 변경 비율에 따른 평균 윈도우 처리 시간 60
Ⅴ. 결론 63
참고문헌 64

최근 본 자료

전체보기

댓글(0)

0