Computing Non-Dominated Flexible Skylines in Vertically Distributed Datasets with No Random Access

Davide Martinenghi ()
Additional contact information
Davide Martinenghi: Dipartimento di Elettronica, Informazione e Bioingegneria, Politecnico di Milano, Piazza Leonardo 32, 20133 Milan, Italy

Data, 2025, vol. 10, issue 5, 1-21

Abstract: In today’s data-driven world, algorithms operating with vertically distributed datasets are crucial due to the increasing prevalence of large-scale, decentralized data storage. These algorithms process data locally, thereby reducing data transfer and exposure to breaches, while at the same time improving scalability thanks to data distribution across multiple sources. Top- k queries are a key tool in vertically distributed scenarios and are widely applied in critical applications involving sensitive data. Classical top- k algorithms typically resort to sorted access to sequentially scan the dataset and to random access to retrieve a tuple by its id. However, the latter kind of access is sometimes too costly to be feasible, and algorithms need to be designed for the so-called “no random access” (NRA) scenario. The latest efforts in this direction do not cover the recent advances in ranking queries, which propose hybridizations of top- k queries (which are preference-aware and control the output size) and skyline queries (which are preference-agnostic and have uncontrolled output size). The non-dominated flexible skyline ( ND ) is one such proposal, which tries to obtain the best of top- k and skyline queries. We introduce an algorithm for computing ND in the NRA scenario, prove its correctness and optimality within its class, and provide an experimental evaluation covering a wide range of cases, with both synthetic and real datasets.

Keywords: skyline; flexible skyline; top- k query; random access (search for similar items in EconPapers)
JEL-codes: C8 C80 C81 C82 C83 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2306-5729/10/5/76/pdf (application/pdf)
https://www.mdpi.com/2306-5729/10/5/76/ (text/html)

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:gam:jdataj:v:10:y:2025:i:5:p:76-:d:1656626

Access Statistics for this article

Data is currently edited by Ms. Cecilia Yang

More articles in Data from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().