【作者】 廖再飞； 罗雄飞； 吕新杰； 李新； 刘伟； 王宏安；

【Author】 Liao Zaifei~(1,2),Luo Xiongfei~(1,2),Lü Xinjie~(1,2),Li Xin~3,Liu Wei~1,and Wang Hongan~1 1(Institute of Software.Chinese Academy of Science,Beijing 100190) 2(Graduate University of Chinese Academy of Sciences,Beijing 100049) 3(School of Computer Science and Technology,Shandong University,Jinan 250101)

【机构】 中国科学院软件研究所； 中国科学院研究生院； 山东大学计算机科学与技术学院；

【摘要】 skyline查询是数据挖掘一个重要的研究方向,在基于数据的决策支持等应用中有着重要的作用.由于现实应用中存在着大量的不完整数据流,但大多数现有的skyline查询算法都依赖于如下的假设:1)任意数据点的所有维度值都是已知的;2)数据集是稳定、有界的并且可以随意访问.此外,随着数据维度的增加,skyline数据点的个数会变得过多,因此引入了k-支配skyline的概念,但是不完整数据的k-支配关系并不具有传递性,现有的skyline查询算法都无法适用.基于这些问题,考虑到数据流高维、无界、顺序性的特点,并且在某些维度上可能具有缺失值的特性,提出了一种新的基于滑动窗口的不完整数据流的k-支配skyline查询算法,实验结果表明,算法不仅可以支持不完整数据流上的k-支配skyline计算,并能够保证效率和性能.更多还原

【Abstract】 Skyline query is an important research area of data mining and plays an important role in the applications that rely on data analysis such as decision-making.The practical applications output a great deal of incomplete data stream,while most of the existing skyline query algorithms rely on the following assumptions:1) All dimensions are available for all data points;2) The data set is persistent,bounded and can be accessed freely.Moreover,as the number of dimensions increases,the possibility of one point dominating another point will become lower.As such,the number of skyline points will become too large to offer any interesting insights.So the authors refer to the k-dominant skyline relation in this paper,but the k-dominant relation of incomplete data is not transitive and the existing skyline algorithms cannot be adapted.A novel k-dominant skyline query algorithm over sliding window is presented for high dimensional,unbounded and ordered incomplete data stream. The experiments demonstrate that the algorithm can support k-dominant skyline query for incomplete data stream over sliding window with efficiency and performance guarantees.更多还原