Abstract
Skyline, also known as Maxima in computational geometry or
Pareto in business management field, is important for many
applications involving multi-criteria decision making. The skyline
of a set of multi-dimensional data points consists of the points
for which no other point exists that is better in at least one
dimension and at least as good in every other dimension. Although
skyline computation and queries have been extensively studied in
both computational geometry and database communities, there are
still many challenges need to be fixed, especially in this big data
era. In this dissertation, we present several efficient and
adaptive skyline computation algorithms. First, we show a faster
output-sensitive skyline computation algorithm which is the
state-of-the-art algorithm from the theoretical aspect. Second,
traditional skyline computation is inadequate to answer queries
that need to analyze not only individual points but also groups of
points. To address this gap, we adapt the original skyline
definition to the novel group-based skyline (G-Skyline), which
represents Pareto optimal groups that are not dominated by other
groups. Third, to facilitate skyline queries, we propose a novel
concept Skyline Diagram, which given a set of points, partitions
the plane into a set of regions, referred to as skyline polyominos.
Similar to kth-order Voronoi Diagram commonly used to facilitate k
nearest neighbor (kNN) queries, any query points in the same
skyline polyomino have the same skyline query results.
Table of Contents
1 Introduction 1
2 Faster Output-sensitive Skyline Computation 5
2.1 Related Work . . . . . . . . . . . . . . . . . . . . . . .
. . . . . 5
2.2 Output-Sensitive Skyline Computation Algorithm . . . . . .
. . 6
2.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . 10
3 Group-based Skyline 11
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . 11
3.2 Related Work . . . . . . . . . . . . . . . . . . . . . . .
. . . . . 17
3.3 G-Skyline Definitions . . . . . . . . . . . . . . . . . .
. . . . . . 20
3.4 Constructing Directed Skyline Graph . . . . . . . . . . .
. . . . 25
3.5 Finding G-Skyline Groups . . . . . . . . . . . . . . . . .
. . . . 29
3.5.1 The Point-Wise Algorithm . . . . . . . . . . . . . . . .
. 30
3.5.2 The Unit Group-Wise Algorithm . . . . . . . . . . . . .
34
3.6 Experiments . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . 38
3.6.1 Experiment Setup . . . . . . . . . . . . . . . . . . . .
. . 38
3.6.2 Case Study . . . . . . . . . . . . . . . . . . . . . . .
. . 40
3.6.3 Computing Skyline Layers . . . . . . . . . . . . . . . .
. 40
3.6.4 G-Skyline Groups in the Synthetic Data . . . . . . . . .
42
3.6.5 G-Skyline Groups in the NBA Data . . . . . . . . . . . .
44
3.7 Extensions . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . 45
3.7.1 AG-Skyline . . . . . . . . . . . . . . . . . . . . . . .
. . 47
3.7.2 PG-Skyline . . . . . . . . . . . . . . . . . . . . . . .
. . 47
3.8 Conclusions . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . 48
4 Skyline Diagram 51
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . 51
4.2 Related Work . . . . . . . . . . . . . . . . . . . . . . .
. . . . . 58
4.3 Preliminaries and Problem Definitions . . . . . . . . . .
. . . . 60
4.4 Skyline Diagram of Quadrant and Global Skyline . . . . . .
. . 63
4.4.1 Baseline Algorithm . . . . . . . . . . . . . . . . . . .
. . 64
4.4.2 Directed Skyline Graph Algorithm . . . . . . . . . . . .
66
4.4.3 Scanning Algorithm . . . . . . . . . . . . . . . . . . .
. . 69
4.4.4 Aggressive Scanning Algorithm . . . . . . . . . . . . .
. 73
4.4.5 Skyline Diagram of Global Skyline . . . . . . . . . . .
. 77
4.5 Skyline Diagram of Dynamic Skyline . . . . . . . . . . . .
. . . 78
4.5.1 Baseline Algorithm . . . . . . . . . . . . . . . . . . .
. . 78
4.5.2 Subset Algorithm . . . . . . . . . . . . . . . . . . . .
. . 81
4.5.3 Scanning Algorithm . . . . . . . . . . . . . . . . . . .
. . 81
4.6 Experiments . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . 83
4.6.1 Experiment Setup . . . . . . . . . . . . . . . . . . . .
. . 84
4.6.2 Skyline Diagram of Quadrant Skyline . . . . . . . . . .
. 85
4.6.3 Skyline Diagram of Global Skyline . . . . . . . . . . .
. 87
4.6.4 Skyline Diagram of Dynamic Skyline . . . . . . . . . . .
88
4.6.5 Performance Improvements through Parallel
Implementation. . . . . 89
4.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . 89
5 Conclusion and Future Directions 91
About this Dissertation
Rights statement
- Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.
School |
|
Department |
|
Degree |
|
Submission |
|
Language |
|
Research Field |
|
关键词 |
|
Committee Chair / Thesis Advisor |
|
Committee Members |
|