Approximate Convex Skyline: A Novel Layer List Construction Method to Answer Top-k Queries
Ki‐Eun Lee, Jun-Seok Heo, Young‐Ho Park · 2011
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.