위치 제약 조건을 고려한 효율적인 스카이라인 계산 = Efficient Computation of a Skyline under Location Restrictions

국문 초록 (Abstract)

다차원 데이터 집합에서 서로 지배되지 않는 데이터로 구성된 부분 집합을 스카이라인이라고 한다. 스카이라인 계산은 다차원 데이터를 대상으로 한 의사결정에 유용한 연산이다. 그러나 스카이라인이 지나치게 큰 경우 이를 의사결정에 활용하기 어려울 수 있다. 본 연구에서는 사용자가 제시하는 원점의 이동, 원점으로부터의 각도와 거리 정보를 반영하여 스카이라인의 일부를 효율적으로 구하는 방법을 모색하였다. 제안한 알고리즘은 스카이라인에 속하지 않는 데이터를 신속하게 제거해가며, 사용자의 요구를 점진적으로 반영할 수 있다는 특징을 갖는다. 알고리즘의 효율성은 실험을 통해 검증하였다.

다국어 초록 (Multilingual Abstract)

The skyline of a multi-dimensional data set is a subset that consists of the data that are not dominated by other members of the set. Skyline computation can be very useful for decision making for multi-dimensional data set. However, in case that the skyline is very large, it may not be much useful for decision making. In this paper, we propose an algorithm for computing a part of the skyline considering location restrictions that the user provides, such as origin movement, degree ranges and/or distances from the origin. The algorithm eliminates noncandidate data rapidly, and returns in order the skyline points that satisfy the user's requests. We show that the algorithm is efficient by experiments.

참고문헌 (Reference)

1 S. Borzsonyi, "The Skyline operator" 421-430, 2001

2 J. Chomicki, "Skyline with Presorting" 717-719, 2003

3 I. Bartolini, "SaLSa: Computing the Skyline without Scanning the Whole Sky" 405-414, 2006

4 Yufei Tao, "Progressive skyline computation in database systems" Association for Computing Machinary, Inc. 30 (30): 41-82, 200503

5 T. Xia, "On Skylining with Flexible Dominance Relation" 1397-1399, 2008

6 P. Godfrey, "Maximal vector computation in large data sets" 229-240, 2005

7 A. Siddique, "K-Dominant Skyline Computation by Using Sort-Filtering Method" PAKDD 2009 839-848, 2009

8 K.-L. Tan, "Effient Progressive Skyline Computation" 301-310, 2001

9 E. Dellis, "Efficient Computation of Reverse Skyline Queries" 291-302, 2007

10 F. P. Preparata, "Computational Geometry - An Introduction" Springer 1985