서지주요정보
I/O-efficient planar range skyline = 외장형 메모리상에서 범위내 극대점을 효율적으로 구해주는 선형 자료 구조
서명 / 저자 I/O-efficient planar range skyline = 외장형 메모리상에서 범위내 극대점을 효율적으로 구해주는 선형 자료 구조 / Jeong-Hun Yoon.
저자명 Yoon, Jeong-Hun ; 윤정훈
발행사항 [대전 : 한국과학기술원, 2013].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8025669

소장위치/청구기호

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

MWST 13002

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

In the planar range skyline reporting problem, the goal is to store a set P of n 2D points in a structure such that, given a query rectangle Q = [α_1, α_2] × [β_1, β_2] the maxima (a.k.a. skyline) of P∩Q can be reported efficiently. The query is 3-sided if an edge of Q is grounded, giving rise to two variants: top-open queries (β_2 = ∞) and left-open queries (α_1 = -∞). This paper presents results in external memory under the O(n/B) space budget (B is the block size), specifically: - We give structures that answer top-open queries in O(log_B n + k/B), O(loglog_B U + k/B), and O(1 +k/B) I/Os when the universe is R^2, a U×U grid, and rank space [O(n)]^2, respectively (where k is the number of reported points). The query complexity is optimal in all cases. - We show that the left-open case is harder, such that any linear-size structure must incur Ω((n/B)^ε + k/B) I/Os to answer a query. In fact, this case turns out to be just as difficult as the general 4-sided queries, for which we provide a static structure with the optimal query cost O((n/B)^ε + k/B).

평면상의 범위내 극대점을 구해주는 문제에서의 목표는, 2차원 공간의 점(데이터)의 집합 P와 사각형 질의(rectangle query) Q = [α_1, α_2] × [β_1, β_2] 가 주어졌을 때 P∩Q 의 극대점(스카이라인)을 효율적으로 구해줄 수 있는 자료구조를 만드는 것이다. 만약 Q의 변(edge) 하나가 없다면 우리는 그것을 3-방향 질의라고 한다. 이 경우에는 크게 두 가지의 질의의 종류로 나누어진다. 첫 번째는 윗 방향 열림 질의 Q = [α_1, α_2] × [β_1, ∞] 이고 두 번째는 왼쪽 방향 열림 질의 이다. Q = [-∞, α_2] × [β_1, β_2]. 윗 방향 열림 질의와 오른 방향 열림 질의는 서로 대응되며, 왼쪽 방향 열림 질의와 아랫 방향 열림 질의 또한 대응된다. 이 논문에서는 윗 방향 열림 질의에 대하여 최적의 질의 응답시간을 제공해주는 선형 자료 구조를 제안할 것이다. 이 결과는 외부 메모리상에서의 I/O 입출력에 대한 것이며, 자료 구조는 정적(static) 자료 구조이다. 또한 더불어 임의의 선형 자료 구조에서의 사각형 질의 응답시간에 대한 최악의 경계를 제안할 것이다. - 데이터 집합 P 가 정적 자료 구조라고 가정하자. 데이터 포인트들의 도메인이 R^2, U×U 그리드, 순위 공간 (rank space, [O(n)]^2) 일 때 윗 방향 열림 질의에 대하여 각각 O(log_B n +k/B ), O(log log_B U +k/B ) 그리고 O(1 +k/B ) I/Os 로 대답할 수 있는 선형 선형 자료 구조를 제안할 것이다. 각각의 질의 응답시간은 모든 경우에 대해서 최적이다. - 왼쪽 방향 열림 질의는 더 어렵다. 왼쪽 방향 열림 질의에 대하여 임의의 선형 자료 구조는 Ω((n/B)^ε+k/B) I/Os를 질의 응답시간에 대한 최악의 경계로 가지고 있다. 또한 선형 자료 구조는 일반적인 사각형 질의에 대하여 O((n/B)^ε+k/B) 를 최적 응답 질의 시간으로 가지게 된다.

서지기타정보

서지기타정보
청구기호 {MWST 13002
형태사항 iv, 32 p. : 삽도 ; 30 cm
언어 영어
일반주기 저자명의 한글표기 : 윤정훈
지도교수의 영문표기 : Yufei Tao
지도교수의 한글표기 : 유페이
공동지도교수의 영문표기 : Sung-Hyon Myaeng
공동지도교수의 한글표기 : 맹성현
수록잡지명 : "I/O-Efficient Planar Range Skyline and Attrition Priority Queues". Proceedings of the 32nd symposium on Principles of database systems, pp. 103-114(2013)
학위논문 학위논문(석사) - 한국과학기술원 : 웹사이언스공학전공,
서지주기 References : p. 26-29
주제 skyline
maxima
range skyline
external memory
efficient
극대점
외장형메모리
스카이라인
효율성
QR CODE qr code