Computing the Skyline Query over a k2-tree compact data structure
PLOS One · 17.07.2026 · 21 (7) · e0353358
DOI: 10.1371/journal.pone.0353358 ↗Kurz gefasst
Fachartikel in der Zeitschrift PLOS One, online erschienen am 17.07.2026. Verfasst von Rodrigo Torres-Avilés und 3 weiteren Autor:innen. Beteiligte Einrichtung: Dpto. de Sistemas de Información, Universidad del Bío-Bío, Concepción, Chile. Die Arbeit nennt 30 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Agencia Nacional de Investigación y Desarrollo.
Abstract (Originalsprache)
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.
Autor:innen und Institutionen
- Dpto. de Sistemas de Información, Universidad del Bío-Bío, Concepción, Chile.
- Dpto. Cs. de la Computación y Tec. de Inf., Universidad del Bío-Bío, Chillán, Chile.
ORCID-Profile: Mónica Caniupán
Förderung
- Agencia Nacional de Investigación y Desarrollo
Zitieren
APA
Torres-Avilés, R., Gutiérrez, G., Muñoz, M., & Caniupán, M. (2026). Computing the Skyline Query over a k2-tree compact data structure. PLOS One, 21(7), e0353358. https://doi.org/10.1371/journal.pone.0353358
Vancouver
Torres-Avilés R, Gutiérrez G, Muñoz M, Caniupán M. Computing the Skyline Query over a k2-tree compact data structure. PLOS One. 2026;21(7):e0353358. doi:10.1371/journal.pone.0353358
BibTeX
@article{TorresAvils2026,
author = {Torres-Avilés, Rodrigo and Gutiérrez, Gilberto and Muñoz, Martita and Caniupán, Mónica},
title = {Computing the Skyline Query over a k2-tree compact data structure},
journal = {PLOS One},
year = {2026},
volume = {21},
number = {7},
pages = {e0353358},
doi = {10.1371/journal.pone.0353358}
}
EUVIMED