메트릭 공간에서 스카이라인을 계산하는 기하 알고리즘

Abstract

Life is a series of selections. In many situations in our lives, we have tochoose 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

)) time with preprocessing and O(

) space with preprocessed structure space. We can also do it in O(

(D +

+ log

)) time with preprocessing time and O(

) space with preprocessedstructure 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(

log

) time. It uses O(

) space. In L2 metric space, it takes O(

CH(Q)

)) time and O(

) space where CH(Q) is the convex hull of Q . For the city metric, we introduce an algorithm that takes O(

log(min{

M

,

})+

+

(log

+log

/ log log

) space.