  Skyline computation is an essential database operation that has many
applications in multi-criteria decision making scenarios such as recommender
systems. Existing algorithms have focused on checking point domination, which
lack efficiency over large datasets. We propose a grid-based structure that
enables grid cell domination checks. We show that only a small constant number
of cells need to be checked which is independent from the number of data
points. Our structure also enables parallel processing. We thus obtain a highly
efficient parallel skyline algorithm named SkyCell, taking advantage of the
parallelization power of graphics processing units. Experimental results
confirm the effectiveness and efficiency of SkyCell -- it outperforms
state-of-the-art algorithms consistently and by up to over two orders of
magnitude in the computation time.
