An Efficient Method for Processing Skyline Queries

Skyline query processing has recently received a lot of attention in database community. This is mainly due to the importance of skyline results in many applications, such as multi-criteria decision making, data mining, and user-preference queries. Given a set of k-dimensional objects, the skyline query finds the objects that are not dominated by others. When users issue multiple different dimensional-space skyline quereis simultaneously, all the existing works obtain the results of these skyline queries from the original relational table from scratch. Clearly, the existing approaches are extremely inefficient as the cardinality of the original relational table and the number of skyline queries increase. Motivated by the above fact, an efficient method, called EAPSQ (efficient algorithm for processing skyline queries), is proposed to return m issued different dimensional-space skyline quereis SQ\-1,…,SQ\-m using n prestoring skyline sets PR\-1,…,PR\-n. The PAPSQ algorithm adequately considers the characteristics of the storage mechanism of prestoring skyline sets, and adopts the concept of contribution margin in economics. Thus it can efficiently achieve the optimal state for distribution of m skyline queries between n prestoring skyline sets, which can markedly improve the performance for processing skyline queries. Moreover, detailed theoretical analyses and extensive experiments demonstrate that our algorithm is both efficient and effective.