We consider the problem of locating the best points in large multidimensional datasets. The goal is to efficiently generate all the points that meet a multi-objective query on data distributed in Vertically Partitioned Tables (VPTs). To compute the skyline on large VPTs, costly joins and comparisons may need to be executed, negatively impacting on the query execution time. We propose a new algorithm named FOPA (Final Object Pruning Algorithm) which is able to efficiently produce the whole set of skyline points and scales up to large datasets. FOPA relies on ordered VPTs, information on the values seen so far, and indices on the VPTs, to prune the space of dominated points and identify the skyline for large datasets in less time than state-of-the-art approaches. Empirically, we study the performance and scalability of FOPA in synthetic data and compare FOPA with existing approaches; our results suggest that FOPA outperforms existing solutions by up to two orders of magnitude.
展开▼
