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

Rodrigo Torres-Avilés, Gilberto Gutiérrez, Martita Muñoz and Mónica Caniupán

PLOS ONE, 2026, vol. 21, issue 7, 1-30

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 k2-tree compact data structure. Our approach leverages the k2-tree’s inherent indexing capabilities to evaluate these queries directly on compressed data, avoiding the need for decompression. The results demonstrate that the k2-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 k2-tree, supported by extensive experimental evaluation and a complete theoretical analysis of the proposed algorithms.

Date: 2026
References: Add references at CitEc
Citations:

Downloads: (external link)
https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0353358 (text/html)
https://journals.plos.org/plosone/article/file?id= ... 53358&type=printable (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:plo:pone00:0353358

DOI: 10.1371/journal.pone.0353358

Access Statistics for this article

More articles in PLOS ONE from Public Library of Science
Bibliographic data for series maintained by plosone ().