Open Access System for Information Sharing

Login Library

 

Thesis
Cited 0 time in webofscience Cited 0 time in scopus
Metadata Downloads

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

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.

qr_code

  • mendeley

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

Views & Downloads

Browse