Grid and angular based partitioning skyline and top-k skyline queries with spark

Skyline queries are used to find interesting tuples from a large data set. They are applied in many practical scenarios, such as multi-objective decision making, real-time web query services, product recommendations, and business data analysis. As the size of data sets and dimension increases, the computation environment needs to switch to distributed systems, where taking full advantage of the parallelism and running efficiently will be of great value. In this paper, we implement grid-based and angular-based partitioning to divide the data space into partitions, so that the skyline queries could be processed in parallel. We propose a method to efficiently prune those that will not contain any skyline tuples in grid based approach. Angular based approach may better balance the workload, the redundant local skyline calculation is avoided and the computing efficiency is significantly improved. Furthermore, in the big data era, it is practically impossible for users to inspect large sets of results, so the top-k treatment is paramount. For size control, we apply the same partitioning paradigm to compute top-k skyline with high ranking as a subset of skyline. The open-source Spark framework solves iterative algorithms using internal memory, and is considered to run programs much faster than MapReduce. The performance study confirms the effectiveness and scalability of proposed algorithms.

Le query Skyline sono utilizzate per trovare tuples interessanti da un set di dati di grandi dimensioni. Sono applicati in molti scenari pratici, come il processo decisionale multi-obiettivo, servizi di query web in tempo reale, raccomandazioni di prodotto e analisi dei dati aziendali. Con l'aumentare delle dimensioni dei set di dati e delle dimensioni, l'ambiente di calcolo deve passare a sistemi distribuiti, dove sfruttare appieno il parallelismo e funzionare in modo efficiente sarà di grande valore. In questo articolo implementiamo partizioni basate su griglia e angolari per dividere lo spazio dati in partizioni, in modo che le query skyline possano essere elaborate in parallelo. Proponiamo un metodo per potare in modo efficiente quelli che non conterranno tuples skyline in approccio grid based. L'approccio basato sull'angolo può bilanciare meglio il carico di lavoro, il calcolo ridondante dello skyline locale è evitato e l'efficienza di calcolo è significativamente migliorata. Inoltre, nell'era dei big data, è praticamente impossibile per gli utenti ispezionare grandi insiemi di risultati, quindi il trattamento top k è fondamentale. Per il controllo delle dimensioni, potremmo usare lo stesso paradigma di partizionamento per calcolare skyline top-k con alto rango come sottoinsieme di skyline. Il framework open source Spark risolve algoritmi iterativi utilizzando memoria interna ed è considerato che esegua programmi molto più velocemente di MapReduce. Lo studio delle prestazioni conferma l'efficacia e la scalabilità degli algoritmi proposti.