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

Davide Martinenghi · 2024

Read Computing the Non-Dominated Flexible Skyline in Vertically Distributed Datasets with No Random Access by Davide Martinenghi (2024) 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/arxiv-2412-15468.txt.

Introduction

Davide Martinenghi brings a modern ranking method to data that is split across sites and cannot be freely probed. When records are stored vertically, each site holding different attributes, many classic search algorithms rely on random access: pulling every attribute of a chosen record at once. Where data is streamed, costly, or external, that access may not exist. Martinenghi adapts the non-dominated flexible skyline, a hybrid of top-k and skyline queries, to this sorted-access-only world.

He presents an algorithm for the setting, proves it correct, and shows it is optimal within its class. Experiments on synthetic and real datasets cover a wide range of conditions. The work matters most where privacy keeps data local, such as health care, finance, and sensor networks, since answers can be computed without gathering the raw records together.

Catalog record

CREATORDavide Martinenghi
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-15468

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Computing the Non-Dominated Flexible Skyline in Vertically Distributed Datasets with No Random Access Davide Martinenghi 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 enhance data privacy by processing data locally, reducing the need for data transfer and minimizing exposure to breaches. They also improve scalability, as they can handle vast amounts of data spread across multiple locations without requiring centralized access. Top- k queries have been studied extensively under this lens, and are particularly suitable in applications involving healthcare, finance, and IoT, where data is often sensitive and distributed across various sources. Classical top- k algorithms are based on the availability of two kinds of access to sources: sorted access , i.e., a sequential scan in the internal sort order, one tuple at a time, of the dataset; random access , which provides all the information available at a data source for a tuple whose id is known. However, in scenarios where data retrieval costs are high or data is streamed in real-time or, simply, data are from external sources that only offer sorted access, random access may become impractical or impossible, due to latency issues or data access constraints. Fortunately, a long tradition of algorithms designed for the “no random access” (NRA) scenario exists for classical top- k queries. Yet, these do not cover the recent advances in ranking queries, proposing 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, trying to get 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 1 Introduction In today’s data-centric world, algorithms designed for vertically distributed datasets are vital due to the growing trend of large-scale, decentralized data storage. These algorithms enhance data privacy by processing information locally, thereby reducing the need for data transfers and minimizing the risk of breaches. They also improve scalability by efficiently managing large volumes of data distributed across various locations without relying on centralized access. Top- k queries (the fundamental tool to tackle multi-objective optimization by transforming the problem into a single-objective problem through a scoring function ), have been studied extensively under this lens, and are particularly suitable in applications involving healthcare, finance, and IoT, where data is often sensitive and distributed across various sources. Classical top- k algorithms, such as [ 14 ] , are based on the availability of two kinds of access to sources: sorted access , i.e., a sequential scan in the internal sort order, one tuple at a time, of the dataset; random access , which provides all the information available at a data source for a tuple whose id is known. However, in scenarios where data retrieval costs are high or data is streamed in real-time or, simply, data are from external sources that only offer sorted access, random access may become impractical or impossible, due to latency issues or data access constraints. Fortunately, a long tradition of algorithms designed for the “no random access” (NRA) scenario exists for classical top- k queries [ 16 ] . Yet, these do not cover the recent advances that have proposed hybridizations of top- k queries and skyline queries [ 1 ] (the other common tool for multi-criteria analysis, based on the notion of dominance ), which try to get the best of both worlds. Indeed, although both share the overall goal to identify the best objects in a dataset, the way they work is totally different: top- k queries are preference-aware and control the output size, while skylines are preference-agnostic and have uncontrolled output size. Flexible skylines [ 8 , 10 ] are a popular attempt at reconciling top- k queries and skylines under a unifying perspective, and, in particular, the non-dominated (ND) flexible skyline is a preference-aware generalization of skylines that admits efficient implementations. This paper refers to a further generalization, which introduces the k parameter into skylines (called k -skybands [ 30 ] and consisting of all tuples dominated by less than k tuples), leading to the notion of non- k -dominated flexible skyline ( {\textsc{ND}}_{k} ). r_{1} r_{2} a 3.0 i 1.0 d 4.0 g 1.5 h 5.0 e 2.0 f 6.0 c 3.0 e 6.0 b 6.0 c 7.0 h 7.0 b 8.0 a 8.0 i 8.0 d 9.0 g 9.0 f 9.0 (a) (b) Figure 1: A set of locations ranked by distance to given points of interest. Example 1 . To exemplify the notion of flexible skyline, consider the dataset shown in Figure , showing two ranked lists of locations sorted by their distance from a given point of interest (say, train station and concert hall). The only options that are not dominated by other options in this dataset are a , h , e , i , because no alternative is better than any of them on both distances; this is the skyline of the dataset. In particular, each of these options is top for at least one monotone scoring function; for instance, e is the top option by average distance ( 4 ) to the points of interest, i.e., using function f(x,y)=0.5x+0.5y , where x and y are, respectively, the numeric attributes from r_{1} and r_{2} . Suppose now that we also consider a preference stating that, while we still want to linearly combine the distances, the distance to the train station is more important, i.e., we refer to the set \mathcal{F} of scoring functions of the form f(x,y)=w_{1}x+w_{2}y , where w_{1}>w_{2} . Under this assumption, i and h are no longer ideal, as no scoring function of the stated form will ever rank them as the top solution; the options a and e are the non-dominated flexible skyline ND with respect to set \mathcal{F} . The gray area shown in Figure 1b represents the region of points that can never become top- 1 , in this dataset, for any of the functions in \mathcal{F} ; in particular, i can never beat e and h can never beat a with these functions. The 2-skyband of the dataset includes all the tuples that are dominated by less than 2 tuples (i.e., 0 or 1) and consists of d , c and g , in addition to all the tuples in the skyline ( a , h , e , i ). This set contains all tuples that may be in the result set of any top-2 query using a monotone scoring function. For instance, with f(x,y)=0.5x+0.5y , the top- 2 results are e and i . However, if we consider the set \mathcal{F} , g is now, in a sense, also dominated by c , because no scoring function in \mathcal{F} may rank it better than c , as shown with the dashed line traversing c . The tuples in the 2 -skyband except for g are

Read the complete text