数据流中ρ-支配轮廓查询算法

ρ-Dominant Skyline Computation on Data Streams

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

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 skyline 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 skyline algorithm.