서지주요정보
정지점의 활용을 극대화한 효율적인 스카이라인 계산법 = Maximized utilization of stop point for efficiently computing the skyline
서명 / 저자 정지점의 활용을 극대화한 효율적인 스카이라인 계산법 = Maximized utilization of stop point for efficiently computing the skyline / 고철우.
저자명 고철우 ; Koh, Chol-Woo
발행사항 [대전 : 한국과학기술원, 2010].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8021839

소장위치/청구기호

학술문화관(문화관) 보존서고

MCS 10039

휴대폰 전송

도서상태

이용가능

대출가능

반납예정일

초록정보

Skyline query filters out a set of interesting points from a large set of data. A point is said to be interesting if it is not dominated by any other point. There has been a growing interest in algorithms for efficiently evaluating skyline queries. However, most of the algorithms require additional data structure in the database server which, in most cases, is not feasible. In this paper we only concentrate in scenarios where additional data structure is not available. Currently, the most efficient algorithm in such circumstance is SaLSa(Sort and Limit Skyline algorithm). SaLSa takes the idea of pre-sorting and limiting the data to compute skyline without having to read the whole data. However, since SaLSa computes the stop point during the progress of the algorithm, the potential of the stop point cannot be fully utilized. In this paper we propose SWT(Skyline with Transformation) which maximizes the potential limiting ability of the stop point, and verify that SWT outperforms SaLSa.

스카이라인 질의는 사용자의 선호도를 고려하여 무수히 많은 데이터로부터 사용자에게 유용한 정보만을 반환한다. 유용한 정보란, 다른 데이터에 의해 지배당하지 않는 데이터로 정의 된다. 스카이라인을 효율적으로 계산하기 위한 많은 방법들이 연구 되었지만, 대부분의 알고리즘은 데이터베이스 서버 내에 별도의 자료구조를 필요로 한다. 하지만 우리가 일반적으로 사용하는 데이터베이스로부터 이러한 조건이 항상 만족되기를 기대할 수는 없다. 본 논문에서는 별도의 자료구조의 사용이 유효하지 않은 상황만을 가정한다. 이와 같은 상황에서 현존하는 최적의 알고리즘으로 Sort and Limit Skyline Algorithm(SaLSa)이 있다. SaLSa는 정렬된 데이터와 정지점의 활용으로 전체 데이터 중 일부만 읽으며 스카이라인을 계산할 수 있다. 하지만 정지점을 중간에 계산하는 SaLSa는 정지점의 기능을 충분히 활용하지 못한다. 본 논문에서는 정지점을 미리 계산하여 정지점의 제거기능을 최대화시킨 효율적인 스카이라인 알고리즘 Skyline with Transformation(SWT)을 제안하고, 실험을 통해 SWT가 SaLSa에 비해 데이터 제거 효과 및 스카이라인 질의 처리 속도가 우수함을 검증한다.

서지기타정보

서지기타정보
청구기호 {MCS 10039
형태사항 iv, 31 p. : 삽도 ; 26 cm
언어 한국어
일반주기 저자명의 영문표기 : Chol-Woo Koh
지도교수의 한글표기 : 이윤준
지도교수의 영문표기 : Yoon-Joon Lee
학위논문 학위논문(석사) - 한국과학기술원 : 전산학과,
서지주기 참고문헌 수록
주제 스카이라인
데이터베이스
스카이라인 질의
스카이라인 대안
skyline
database
skyline query
skyline alternatives
dominance graph
QR CODE qr code