On efficient decision making : strategies and heuristics for computing Skyline with parallel algorithms

Skyline queries aim to find interesting points in large Datasets. This operator allows one to deal with problems of optimizing different criteria simultaneously, so many practical scenarios can take significant advantages from Skyline computation: some examples are data visualization, graph analysis and product recommendations. The first approaches were proposed in the early 2000s, but as datasets have grown larger, parallel algorithms in distributed environments have become necessary. Many of these algorithms have been implemented in MapReduce, but this work compares their performance with algorithms implemented in PySpark, which is an efficient framework for processing Big Data. Two partitioning techniques, Grid and Angular partitioning, are proposed to take advantage of parallel programming, and their advantages and disadvantages are evaluated. To further optimize the process, an efficient way to fully parallelize the algorithm is implemented and a new heuristic to reduce the number of dominance tests between points is presented. Experiments are conducted in different situations, such as different dataset distributions and increasing dataset size, and the pros and cons of each algorithm are analyzed.

Le query Skyline hanno l’obiettivo di trovare punti interessanti in grandi Dataset. Questo operatore permette di affrontare problemi di ottimizzazione simultanea secondo diversi criteri, tanti scenari pratici possono trarre vantaggi significativi dal calcolo dello Skyline: alcuni esempi sono la visualizzazione dei dati, l’analisi dei grafi e la raccomandazione dei prodotti. I primi approcci risalgono agli inizi degli anni 2000, poi quando i dataset hanno iniziato a crescere e diventare più grandi, gli algoritmi paralleli in ambienti distribuiti sono diventati necessari. Molti di questi algoritmi sono stati implementati in MapReduce, questa tesi ne confronta le prestazioni rispetto a quelle degli stessi algoritmi implementati in PySpark, uno strumento efficiente per lavorare con i Big Data. Per sfruttare a pieno i benefici della programmazione parallela, sono proposte due tecniche di partizionamento, quella a griglia e quella angolare, ne vengono quindi valutati vantaggi e svantaggi. Per ottimizzare ulteriormente il processo, sono presentati un modo efficiente per rendere completamente parallelo l’algoritmo e un’euristica per ridurre il numero di test di dominazione tra punti. Per analizzare i pro e i contro di ciascun algoritmo, sono stati condotti esperimenti in situazioni differenti, come diverse distribuzioni dei punti dei dataset o dataset di diverse cardinalità.