Find top-k representative skyline points by using grid data structure

Abstract

To analyze a database more intensively, we need some representative records, such as, the cheapest one, the most popular one, the most convenient one and so on. Skyline query and its variant are popular functions to find such representative objects from a numerical database. However, a skyline query often retrieves too many points to analyze intensively especially for high-dimensional dataset. Therefore, we put our focus on selecting top-k points that represents a database. We select the k points so that many points are dominated by the k points. This paper proposes an efficient grid-based algorithm to find such top-k representative skyline points. We conducted a set of experiments to show the effectiveness and the scalability of the propose algorithm.