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

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

Read Computing the Skyline Query over a k2-tree compact data structure by Rodrigo Torres-Avilés, Gilberto Gutiérrez, Martita Muñoz, Mónica Caniupán (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/plos-pone-0353358.txt.

Description

Rodrigo Torres-Avilés and three colleagues show that a classic database question can be answered without unpacking the data, in this 2026 PLOS ONE computer science paper. A skyline query finds records that no other record beats on every measure at once — the hotels, say, that are each cheapest or best-rated in some unbeatable combination. The team implemented two flavours of the query inside a compact tree structure that stores data in compressed form.

Working directly on the compressed structure saved memory compared with ordinary approaches in their experiments, while still returning exact answers. They back the method with full proofs and benchmarks. Compact querying matters wherever data outgrow the machine that must answer questions about them.

Catalog record

CREATORRodrigo Torres-Avilés, Gilberto Gutiérrez, Martita Muñoz, Mónica Caniupán
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE74068
LICENSECC_BY
RIGHTSCC BY
SOURCEPLOS

Source: https://doi.org/10.1371/journal.pone.0353358

Browse the full library · About the Tower of Babel