高速流环境下近似连续k代表轮廓查询算法

作     者：朱睿 宋栿尧 王斌 杨晓春 张安珍 夏秀峰 ZHU Rui;SONG Fu-Yao;WANG Bin;YANG Xiao-Chun;ZHANG An-Zhen;XIA Xiu-Feng

作者机构：沈阳航空航天大学计算机学院辽宁沈阳110136 东北大学计算机科学与工程学院辽宁沈阳110169 

出 版 物：《软件学报》 (Journal of Software)

年 卷 期：2023年第34卷第3期

页      面：1425-1450页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 081202[工学-计算机软件与理论] 

基　　金：国家自然科学基金(62102271,62072088,61991404) 国家重点研发计划(2020YFB1707901) 沈阳市创新人才项目(RC200439)。 

主　　题：轮廓查询 k代表轮廓查询 滑动窗口 分片 高速流 

摘      要：k代表轮廓查询是从传统轮廓查询中衍生出来的一类查询.给定多维数据集合D,轮廓查询从D中找到所有不被其他对象支配的对象,将其返回给用户,便于用户结合自身偏好选择高质量对象.然而,轮廓对象规模通常较大,用户需要从大量数据中进行选择,导致选择速度和质量无法得到保证.与传统轮廓查询相比,k代表轮廓查询从所有轮廓对象中选择“代表性最强的k个对象返回给用户,有效地解决了传统轮廓查询存在的这一问题.给定滑动窗口W和连续查询q,q监听窗口中的数据.当窗口滑动时,查询q返回窗口中,组合支配面积最大的k个对象.现有算法的核心思想是:实时监测当前窗口中的轮廓对象集合,当轮廓对象集合更新时,算法更新k代表轮廓.然而,实时监测窗口中,轮廓集合的计算代价通常较大.此外,当轮廓集合规模较大时,从中选择k代表轮廓的计算代价是同样巨大的,导致已有算法无法在高速流环境下使用.针对上述问题,提出了ρ-近似k代表轮廓查询.为了支持该查询,提出了查询处理框架PAKRS(predict-based approximate k representative skyline).首先,PAKRS利用高速流的特性对当前窗口进行划分,根据划分结果构建未来窗口预测结果集,用其预测新流入窗口数据成为轮廓对象的最早时间.其次,提出了索引ρ-GRID.它帮助PAKRS在2维和d维(d2)环境下,分别以O(k/s+k/m)和O(2Ld/m+2Ld/s)的增量维护代价下筛选近似k代表轮廓,L是一个小于k的正整数.由理论分析证明可知,PAKRS的计算复杂度小于前人所提的算法计算复杂度.最后,通过大量实验对所提算法性能进行评估.结果表明,PAKRS的运行时间是PBA(prefix-based algorithm)算法的1/4、GA(greedy algorithm)算法的1/6、ε-GA(ε-constraint greedy algorithm)算法的1/3.