Computation of the Flexible Skylines in a distributed environment

Skyline queries are a way of finding interesting data within a large dataset by considering attributes all at the same level. Flexible skylines, on the other hand, are methods of finding interesting data by applying constraints on the attributes, thereby also reducing the amount of data returned. The computation of these skylines can become very time-consuming in the case of very large datasets. In this thesis, we will implement parallel computation algorithms for these datasets, trying to reduce the execution time as much as possible. We will introduce several algorithms for parallel computation taken from the literature applied to skyline computation and also adapt them to the computation of the Flexible Skyline ND and PO operators. We will try to introduce improvements to these algorithms with an initial filtering phase aimed at decreasing the dataset size before performing the parallel phase, and once it is established that the sequential part is the most expensive, we will propose an all parallel algorithm in which we will eliminate it totally. To carry out the parallelization of these algorithms, we will use the PySpark framework and see in detail how these algorithms behave by changing the size of the dataset and the dimensions.

Le Skyline query sono un modo per trovare dati interessanti all’interno di un dataset di grandi dimensioni che considerano gli attributi tutti allo stesso livello. Le Flexible Skyline invece, sono dei metodi per trovare dati interessanti applicando dei vincoli sugli attributi, riducendone cosi anche la quantità di dati restituiti. Il calcolo di queste Skyline può diventare molto dispendioso nel caso di dataset di grandi dimensioni. In questa tesi andremo ad implementare algoritmi paralleli per il calcolo di questi set di dati cercando di diminuirne il tempo di esecuzione quanto più possibile. Introdurremo diversi algoritmi per il calcolo parallelo presi dalla letteratura applicati al calcolo delle Skyline e li adatteremo anche al calcolo degli operatori Flexible Skyline ND e PO. Cercheremo di introdurre miglioramenti a questi algoritmi con una fase di filtraggio iniziale volta a diminuire la grandezza del dataset prima di effettuare la fase parallela e una volta assodato che la parte sequenziale è la più dispendiosa, proporremo un algoritmo tutto in parallelo in cui la elimineremo del tutto. Per effettuare la parallelizzazione di questi algoritmi utilizzeremo il framework PySpark e vedremo nel dettaglio come si comportano questi algoritmi cambiandone la grandezza del dataset e le dimensioni.