Computing the Skyline Query over a k2-tree compact data structure

Abstract

This study aims to explore the feasibility of executing Skyline Queries—used to identify optimal data points based on multiple criteria—within compact data structures. While existing algorithms typically operate on plain or indexed datasets, this work investigates how such queries can be efficiently resolved using compact representations. We focus on implementing two Skyline Query variants, Constrained Skyline Query and Enumerating Skyline , within the k 2 -tree compact data structure. Our approach leverages the k 2 -tree’s inherent indexing capabilities to evaluate these queries directly on compressed data, avoiding the need for decompression. The results demonstrate that the k 2 -tree structure effectively supports both types of Skyline Queries. Our experimental evaluation shows improved resource utilization compared to non-indexed methods, confirming that compact data structures can process these queries efficiently without data inflation. This article presents a comprehensive study of implementing skyline queries directly over compact data structures—specifically the k 2 -tree, supported by extensive experimental evaluation and a complete theoretical analysis of the proposed algorithms.