Browse

Graph Indexing for Label-Constrained Reachability Queries
제한된 라벨 도달 질의를 위한 그래프 인덱싱 기법

Cited 0 time in Web of Science Cited 0 time in Scopus
Authors
Mohammadsadegh Najafi
Advisor
Srinivasa Rao Satti
Issue Date
2020
Publisher
서울대학교 대학원
Keywords
Label Constrained Reachability QueriesEdge Labeled GraphDisjoint ReachabilityBFS제한된 라벨 도달 질의간선 레이블 그래프개별적 도달 가능성너비 우선 탐색
Description
학위논문 (석사) -- 서울대학교 대학원 : 공과대학 컴퓨터공학부, 2020. 8. Srinivasa Rao Satti.
Abstract
계속해서 발전하는 세계에서 우리는 간선에 레이블이 포함된 그래프로 표현된 소셜 네트워크, 세만틱 웹 및 인용 네트워크 데이터를 계속해서 접하게 된다.
이렇게 그래프 형태로 구축된 데이터 내의 지식은 기저의 그래프를 질의함으로서 영향력을 발휘한다.
기본적으로 수행되는 그래프 질의는 주어진 소스 정점과 타켓 정점간의 도달 가능성을 판별한다.
또한 해당 질의는 간선에 라벨이 부여된 그래프 형태에 대해서 대상 라벨 집합을 제한하는 형태로도 주로 수행된다.
Valstar 등[SIGMOD-2017]에 의해 상기 문제가 제시되었으며, 그들은 해당 라벨 제한 질의를 빠르게 지원하는 landmark indexing이라는 방식을 제안하였다.
본 논문을 통해 우리는 간편하고 실제적이며 공간 효율적으로 처리할 수 있는 제한된 라벨 도달 질의 수행 방식을 소개한다.
다양한 종류의 그래프에 대한 실험을 통하여 우리가 제시한 질의 알고리즘이 상당한 수준의 공간 효율성을 보임을 확인한다.
또한 landmark indexing과 비교하였을 때 제안된 처리 방식의 질의 처리 시간 및 사용되는 공간이 개선되었음을 보인다.
In our ever-growing world, we are faced with graph data in social networks, semantic webs, or a citation network stored in an edge-labeled graph. A good deal of knowledge in such a graph-structured data can be leveraged by querying the underlying graph. A fundamental query determines reachability between a given source and a target. The reachability query in the edge-labeled graph often also involves constraining the label set. This problem has recently been addressed by Valstar et al.~[SIGMOD-2017], who proposed an approach called Landmark Indexing to support label-constrained queries faster. In this work, we introduce simple, practical, and space-efficient solutions for efficiently evaluating label-constrained reachability (LCR) queries. Experimental results on both real and synthetic graphs demonstrate significant space efficiency benefits of our solutions. In fact, our schemes improve upon both the query time and space usage in comparison with landmark indexing.
Language
eng
URI
https://hdl.handle.net/10371/169365

http://dcollection.snu.ac.kr/common/orgView/000000161949
Files in This Item:
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Computer Science and Engineering (컴퓨터공학부)Theses (Master's Degree_컴퓨터공학부)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse