Skyline View: Efficient Distributed Subspace Skyline Computation

Abstract. Skyline queries have gained much attention as alternative query semantics with pros (e.g.low query formulation overhead) and cons (e.g.large control over result size). To overcome the cons, subspace skyline queries have been recently studied, where users iteratively specify rele-vant feature subspaces on search space. However, existing works mainly focuss on centralized databases. This paper aims to extend subspace sky-line computation to distributed environments such as the Web, where the most important issue is to minimize the cost of accessing vertically dis-tributed objects. Toward this goal, we exploit prior skylines that have overlapped subspaces to the given subspace. In particular, we develop algorithms for three scenarios – when the subspace of prior skylines is superspace, subspace, or the rest. Our experimental results validate that our proposed algorithm shows significantly better performance than the state-of-the-art algorithms.