Skyline Query over k²-Tree Compact Data Structure

Skyline Query is a type of database query that filters out a set of interesting data points from a potentially large dataset based on multiple criteria. Until now, algorithms which tackle this query work over plain data or indexed data structures, but there does not exist a mechanism to address it in compact data. Nevertheless, this query can be addressed with the points indexed in Compact Data Structures. Specifically, we address two variants of the query in the k<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>-tree compact structure. One is related to a multi-criteria restriction named Constrained Skyline Query and the other counts the number of points dominated by every Skyline point which is called Enumerating Skyline. Our study confirms that the k<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>-tree compact data structure is a suitable structure to directly implement the Skyline Query. The experimentation of our proposal demonstrates a better use of resources than a query over non-indexed sets and can therefore be calculated without uncompressing the data.