Abstract: Skyline query on data stream can't directly compute ρ-dominant skyline query, and traditional ρ-dominant skyline query can’t meet the real-time need when data are updated frequently. So this paper proposes ρ-dominant skyline query algorithm on data stream. Firstly, the definitions of full-dominance, ρ-dominance and ρ-dominant skyline are introduced, and the definition of ρ-dominant skyline on data stream is proposed. Next, a data filtering method based on time sequence dominance is proposed by thoroughly analyzing properties about ρ-dominant sky-line on data stream, and an algorithm, called ρ-dominant skyline query over sliding window (DSSW), is developed to increase the efficiency of skyline computing on data stream. Finally, extensive experiments show that the DSSW algorithm has obvious advantages in response time and storage space compared with traditional ρ-dominant sky- line algorithm.

Key words:  ρ-dominant relationship;ρ-dominant skyline, data stream, sliding window

摘要： 数据流上的轮廓查询算法不能直接处理ρ-支配轮廓查询，而传统的ρ-支配轮廓查询无法在数据更新频繁时满足查询处理的实时性需求。因此，提出了数据流上的ρ-支配轮廓查询算法。首先，系统地介绍了完全支配、ρ-支配和ρ-支配轮廓的定义，进而提出了数据流上ρ-支配轮廓的定义。然后，通过深入分析数据流上的ρ-支配轮廓的性质，得出基于时序支配的数据过滤方法，并提出了基于滑动窗口的ρ-支配轮廓查询算法（ρ-dominant skyline query over sliding window，DSSW），提高了数据流上的ρ-支配轮廓计算的效率。最后，通过大量的实验证明，DSSW算法相比较于传统的ρ-支配轮廓查询算法，在响应时间及存储空间上均有明显优势。

关键词: &rho, -支配关系；&rho, -支配轮廓；数据流；滑动窗口