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

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

- Authors
- 손완빈

- Date Issued
- 2010

- Publisher
- 포항공과대학교

- Abstract
- 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

)) 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 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(

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.

- URI
- http://postech.dcollection.net/jsp/common/DcLoOrgPer.jsp?sItemId=000000546439

http://oasis.postech.ac.kr/handle/2014.oak/572

- Article Type
- Thesis

- Files in This Item:
- There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.