Parallel Implementations of the Skyline Query using PySpark

The Skyline operator is an extension of the SQL language which returns a set of interesting points from a given dataset, first proposed in 2001. Since then, its high time complexity and the prevalence of the algorithm have made it interesting to explore parallel solutions which compute the skyline of a dataset in the least time possible. Many different implementations have been suggested mostly in the Map-Reduce framework, but few of these solutions have been brought in the Spark framework. As such, we will bring some of the solutions to PySpark and propose different optimizations which can be carried out, that significantly reduce the query’s time in big datasets, with the most effective being the “Representative filtering” method.

La query Skyline è un’estensione del linguaggio SQL il quale restituisce un set di punti interessanti da un mole di dati, proposto per la prima volta nel 2001. L’alta complessità temporale dell’algoritmo ha reso interessante la ricerca di algoritmi che calcolano in parallelo lo Skyline nel minor tempo possibile. Diverse implementazioni paralleli sono state suggerite utilizzando il framework Map-Reduce, ma non è stato quasi mai esplorato l’utilizzo del framework Spark. Noi abbiamo portato diverse soluzioni su PySpark per paragonarli con i diversi metodi di ottimizzazione che si possono usare per ridurre il tempo d’esecuzione dell’algoritmo, tra i quali quello più importante chiamato “Representative filtering”.