Geometric Algorithms for Geospatial Data: Skyline and Top-k Queries

Abstract

The amount of data collected by various devices and applications has significantly increased over the last years. There is no reason to believe that this trend will change in the near future. In the face of ever increasing amount of data, the task of efficiently receiving information of high relevance with respect to a given query and separating that data from irrelevant information becomes more and more important. Especially we focus on computing a useful subset of geospatial data. Because of wide use of GPS devices, the number of geospatial data and spatial query requests is increasing rapidly. So, the efficient access to the spatial data becomes more significant. GIS is a good example of application that aims to support efficient access to massive geospatial datasets. In this thesis, we are given two point sets: a set P of n data points and a set Q of m query points in the L1 plane. Our goal is to find a useful subset of P with respect to Q by considering distances between them. We consider three approaches to find a “useful subset”: Manhattan Spatial Skyline Queries, Top-k Queries in the L1 plane, and Top-k Manhattan Spatial Skyline Queries.

지리공간자료는 지구상의 객체들을 기반으로 한 기하 자료이다. 오랜 기간 동안 지리공간자료와 관련된 문제에서는 정확도가 주요 이슈였으나 최근에는 자료의 크기가 더 큰 이슈가 되고 있다. 최근 다루어야 하는 자료의 양은 급격하게 증가하고 있으며 이러한 트렌드는 앞으로도 계속될 것으로 보인다.본 학위 논문에서는 방대한 지리공간자료에서 사용자의 질의와 높은 연관 관계를 가지는 유용한 부분집합을 계산하는 기하 알고리즘에 대해 다루었다. GPS 장비와 스마트폰의 보급으로 자료의 양과 질의의 수가 급격하게 증가하고 있기 때문에 이러한 부분집합 계산의 필요성이 점차 커지고 있다. 구체적으로는 평면상에 점 집합으로 주어진 자료에서 마찬가지로 점 집합으로 주어진 쿼리에 대해 유용한 부분집합을 뽑는 여러 방법들에 대해 연구하였다. 본 학위 논문에서는 이를 위한 방법으로 스카이라인 질의와 Top-k 질의에 대해 연구하고 이를 해결하기 위한 효율적인 기하 알고리즘을 제시하였다. 스카이라인 질의와 Top-k 질의는 자료에서 유용한 부분집합을 뽑기 위한 대표적인 방법들로 알려져 있다.