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

来源：计算机科学与探索杂志2017年第7期北京时间：

作者：王之琼，霸建民，黄达，信俊昌

单位：1. 东北大学 中荷生物医学与信息工程学院，沈阳 1108192. 东北大学 计算机科学与工程学院，沈阳 110819

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

关键词：ρ,-支配关系；ρ,-支配轮廓；数据流；滑动窗口