Top-k 질의는 릴레이션에서 스코어가 가장 높은(또는 가장 낮은) k개의 튜플을 결과로 찾는다. 이러한 Top-k 질의를 처리하는 대표적인 방법으로 계층 기반 방법이 있다. 계층 기반 방법은 튜플이 가지고 있는 d 개의 속성의 값을 고려하여 각 튜플을 d-차원 공간상의 점 객체로 매핑하고, Top-i가 될 수 있는 객체들로 i번째 계층을 구성한다. 이 방법은 질의 처리시 최대 k개의 계층만 읽음으로써 Top-k 질의 결과를 구할 수 있다. 여기서 계층을 구성하는 방법으로 기존 연구들은 스카이라인, 컨벡스 홀, 또는 컨벡스 스카이라인을 사용하였다. 그러나 스카이라인은 생성시간이 빠른 반면, 계층에 포함되는 객체의 수가 많아서 질의 처리 성능이 나쁘다는 단점이 있다. 컨벡스 홀은 계산 복잡도가 높기 때문에 계층의 생성 시간이 오래 걸린다는 단점이 있다. 컨벡스 스카이라인은 전체 객체에 대한 스카이라인을 기반으로 컨벡스 홀을 계산하기 때문에, 고차원에서 오래 걸린다. 본 논문에서는 전체 객체에 대해 생성된 스카이라인을 여러 개의 영역들로 분할하고, 각 영역에 포함되는 객체들을 기반으로 컨벡스 홀을 계산하여 컨벡스 스카이라인의 생성 시간을 줄인 근사 컨벡스 스카이라인을 제안한다. 실험 결과는 근사 컨벡스 스카이라인이 컨벡스 스카이라인의 색인 구성 시간을 줄였음을 보인다.
A top-k query returns k tuples with the highest (or the lowest) scores from a relation. Layer-based methods are the representative method for processing these top-k queries. Layer-based methods consider d attribute values of the tuples and map them onto a d-dimensional space, and then, they construct i-th layer with the objects that can be the top i. These methods answer the top-k queries by reading at most k layers. Here, to construct the layer, the existing work used the convex hulls, skylines, or convex skylines. However, although the layer computing time using the skyline is fast, the number of objects in a layer can be very large. Furthermore, the convex hull suffers from its slow index building time because the time complexity of computing a layer is high. Also, since convex skylines compute the convex hulls based on the skyline over the all objects, the building time is slow. In this paper, we propose approximate convex skyline that reduces the index building time of the convex skyline by partitioning the skyline over the all objects into multiple regions and computing the convex hulls over the objects contained in each region. Experimental results show that the approximate convex skyline reduces the index building time of the convex skyline.
