一种ρ-支配轮廓查询的高效处理算法

近年来,作为重要的多目标决策手段的轮廓查询逐渐得到学术界的重视,相继提出了基于不同支配关系的多种轮廓变体查询.首先,通过对实际应用需求进行分析,提出了基于元组对应数值间比例值大小的ρ-支配关系的定义,进而提出了ρ-支配轮廓查询的概念.其次,对ρ-支配轮廓的基本性质进行了细致而深入的分析,在此基础上,提出了基于分支定界的ρ-支配轮廓查询算法(Branch and Boundρ-Dominant Skyline Algorithm,BBDS),避免了对R-树索引的多次访问,从而提高了ρ-支配轮廓查询的执行效率.最后,通过大量的仿真实验对ρ-支配轮廓查询的语义进行分析,并对BBDS算法的性能进行验证.实验结果表明,ρ-支配轮廓查询是轮廓查询语义的扩展和补充,而提出的BBDS算法则是求解ρ-支配轮廓查询的高效算法.

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

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