An Efficient Algorithm for Skyline Queries in Cloud Computing Environments

摘要

Skyline query processing has re-cently received a lot of attention in database and data mining communities. However, most existing algorithms consider how to efficient-ly process skyline queries from base tables. Obviously, when the data size and the number of skyline queries increase, the time cost of skyline queries will increase exponentially, which will seriously influence the query effi-ciency. Motivated by the above, in this paper, we consider improving the query efficiency via skyline views and propose a cost-based algorithm (abbr. CA) to efficiently select the optimal set of skyline views for storage. The CA algorithm mainly includes two phases:(i) reduce the skyline views selection to the minimum steiner tree problem and obtain the approximate optimal set AOS of skyline views, and (ii) adjust AOS and produce the fi-nal optimal set FOS of skyline views based on the simulated annealing. Moreover, in order to improve the extendibility of the CA algorithm, we implement it based on the map/reduce distributed computation model in cloud com-puting environments. The detailed theoretical analyses and extensive experiments demon-strate that the CA algorithm is both efficient and effective.