그룹 스카이라인에서의 why-not 질의 처리 기법
Answering Why-not Query on Group Skyline
- 주제(키워드) 데이터베이스 , 스카이라인 , 그룹 스카이라인 , 와이낫 질의 , Database , Skyline , Group skyline , Why-not query
- 발행기관 서강대학교 일반대학원
- 지도교수 박석
- 발행년도 2021
- 학위수여년월 2021. 2
- 학위명 석사
- 학과 및 전공 일반대학원 컴퓨터공학과
- UCI I804:11029-000000065809
- 본문언어 한국어
- 저작권 서강대학교 논문은 저작권보호를 받습니다.
초록/요약
스카이라인(Skyline) 이란, 다차원 데이터 셋에서 주어진 차원을 모두 고려하는 경우에 어떤 데이터 개체에게도 지배당하지 않는 데이터 개체들의 집합이라고 할 수 있다. 그룹 스카이라인이란, 스카이라인 개념을 집합으로 확장한 것으로 그룹 크기가 주어 졌을 때 동일한 크기의 집합에 지배당하지 않는 그룹의 집합이다. 본 논문에서는 주어진 개체가 그룹 스카이라인에 포함되기 위한 최소 비용을 찾는 Why-not 그룹 스카이라인 질의를 제안한다. Why-not 그룹 스카이라인 질의는 기본적으로 다차원 공간 안에서 연속적인 공간을 해공간(Solution space)으로 가지기 때문에 시간 복잡도가 크다. 우리는 무한한 해 공간을 유한한 해 공간으로 한정하고 무차별 대입 기법으로 질의 처리 과정을 설명한다. 이 때, 무차별 대입 기법으로 문제를 해결하기 위해서는 현실에서는 사용할 수 없는 정도의 질의 처리 시간이 걸리게 된다. 따라서 데이터에 대한 시간 복잡도의 의존도를 실용적으로 사용할 수 있는 수준까지 낮출 수 있는 알고리즘을 제안한다. 먼저 다중 레이어를 고려한 baseline알고리즘인 KL알고리즘을 제안하여 전체 데이터 개수에 영향을 크게 받지 않는 것을 보이고, Group Element를 고려한 GE 알고리즘을 제안하여 질의 처리 시간이 주어진 그룹의 크기에 영향을 적게 받는 것을 보인다. 더하여 하한을 정의하여 가지치기 기법을 제안한다. 제한적이지만 질의처리 속도를 매우 개선시킬 수 있는 GE+알고리즘을 소개한다. 실험에서는 제안 기법의 가지치기 성능이 실제 문제에 적용할 수 있다는 것을 알 수 있다.
more초록/요약
Skyline is a collection of data objects that are not dominated by any data object when all dimensions are considered on the multidimensional space. Given the group size, a group skyline is a set of groups that are not dominated by any other same sized group. Which extends the component of skyline from an object to a group. In this thesis, we define why-not group skyline query that finds the minimum cost for a query object to be included in the group skyline set. The why-not group Skyline query has a high time complexity because it basically has a continuous space within a multi-dimensional space as a solution space. We explain the whole process of handling this query process with brute force algorithm with reducing the solution space from infinite space to finite space. However, the brute force algorithm takes unacceptable query processing time. Therefore, we proposed algorithms which reduce the dependence of time complexity on data to a practical level. First, we proposed a baseline algorithm that considers multi-layer called KL algorithm which is not easily affected on the number of the total data objects. And then, there is GE algorithm based on Group Element which is proved to be rarely sensitive to the given group size k. Additionally we proposed a pruning technique with lower bound. Furthermore, limited but immensely powerful algorithm, GE+ is also proposed. Experiments show that pruning performance of proposed techniques can be applied to real problems.
more