메트릭 공간에서 스카이라인을 계산하는 기하 알고리즘
Skyline Queries in Metric Space
- 주제(키워드) Skyline Queries
- 발행기관 POSTECH 대학원
- 지도교수 안희갑
- 발행년도 2010
- 학위수여년월 2010. 2
- 학위명 석사
- 학과 및 전공 일반대학원 컴퓨터공학과
- 세부전공 컴퓨터 이론 전공
- 실제URI http://www.dcollection.net/handler/postech/000000546439
- 본문언어 영어
- 저작권 포항공과대학교 논문은 저작권에 의해 보호받습니다.
초록/요약
Life is a series of selections. In many situations in our lives, we have to choose among a number of candidates. We propose algorithms to select ‘good’ candidates and skyline queries are a method to choose them. In this thesis we focus on finding skylines in metric space. We denote by P the set of data points, Q the set of query points and S the set of skyline points. The goal of the problem is to retrieve all the skyline points from P with respect to Q. First we propose an algorithm to compute all skylines in general metric space which takes O(|P||Q|(|S|D+log |P|)) time with preprocessing and O(|P|) space with preprocessed structure space. We can also do it in O(|P||Q|(D + |S| + log |P|)) time with preprocessing time and O(|P||Q|) space with preprocessed structure space where O(D) is time complexity to compute a travel time between two points. For L1, L2 and city metric space, we show algorithms that use properties of the metric space. In L1 metric space, we can compute all skylines in O(|P| log |P|) time. It uses O(|P|) space. In L2 metric space, it takes O(|P|(|S|log |CH(Q)| + log |P|)) time and O(|P|) space where CH(Q) is the convex hull of Q . For the city metric, we introduce an algorithm that takes O(|P||Q| log (min{|M|, |P|})+|M||Q| log |M|+|P| log |P|+|S||M|(log |P|+log |M|)) time and O(|P| log |P|/ log log |P|+|M||Q|) space.
more목차
1 Introduction 1
1.1 Related work 4
2 Preliminaries 6
2.1 Notations and Problem Definition 6
2.2 DIstances and Metrics 9
2.2.1 CIty Metric 10
2.3 Geometric Concepts 12
2.3.1 Convex hull 12
2.3.2 Voronoi Diagram and Delaunay Graph 13
2.3.3 Segment Dragging Queries 14
2.3.4 Orthogonal Range Queries 15
3 Skyline Queries in General Metric Space 17
3.1 Algorithm 17
4 Skyline Queries in L2 Metric 20
4.1 Problems of Recent Work 20
4.2 Exact Algorithm 22
4.2.1 Efficient Dominance test 22
4.2.2 Algorithm 24
4.3 Finding a Subset of Skyline Efficiently 25
4.3.1 Algorithm 24
4.4 Implementation 29
4.4.1 Voronoi Diagram 29
4.4.2 Convex Hulls 30
4.4.3 VS2 31
4.4.4 EnhancedSkylineL2(ES) 32
4.5 Experiments 32
4.5.1 Experiment Settings 33
4.5.2 Efficiency 35
4.6 Discussion 38
5 Skyline Queries in L1 Metric 39
5.1 Intersection of L1 circles 40
5.2 Algorithm 42
5.2.1 Degenerate Case 43
5.3 Discussion 45
6 Skyline Queries in City Metric 46
6.1 Basic Idea 46
6.2 Computing the Shortest Path Map 47
6.3 Union of Circles in the City Metric 49
6.4 Computing Data Points in Dominated Region 50
6.5 Algorithm 51
6.6 Using Algorithm for General Metric Space 53
7 Conclusions 55