Understanding the meaning of a shifted sky a gene

Authors: Zhenjie Zhang Hua Lu Beng Chin Ooi Anthony K H Tung

Publish Date: 2009/06/03

Volume: 19, Issue: 2, Pages: 181-201

PDF Link

Abstract

Skyline queries are often used on data sets in multidimensional space for many decisionmaking applications Traditionally an object p is said to dominate another object q if for all dimensions it is no worse than q and is better on at least one dimension Therefore the skyline of a data set consists of all objects not dominated by any other object To better cater to application requirements such as controlling the size of the skyline or handling data sets that are not wellstructured various works have been proposed to extend the definition of skyline based on variants of the dominance relationship In view of the proliferation of variants in this paper a generalized framework is proposed to guide the extension of skyline query from conventional definition to different variants Our framework explicitly and carefully examines the various properties that should be preserved in a variant of the dominance relationship so that 1 maintaining original advantages while extending adaptivity to application semantics and 2 keeping computational complexity almost unaffected We prove that traditional dominance is the only relationship satisfying all desirable properties and present some new dominance relationships by relaxing some of the properties These relationships are general enough for us to design new topk skyline queries that return robust results of a controllable size We analyze the existing skyline algorithms based on their minimum requirements on dominance properties We also extend our analysis to data sets with missing values and present extensive experimental results on the combinations of new dominance relationships and skyline algorithms

Keywords: