基于高维空间的在线高效子空间Skyline算法——CSky

• 作者: 周傲英 周红福 宫学庆 郑凯
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 轮廓 子空间 渐进算法 在线算法
• 年，卷（期）: 2007,（8）
• 所属期刊栏目: 数据挖掘
• 页码范围: 1409-1417
• 页数: 9页
• 分类号: TP301
• 字数: 8205字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2007.08.023

摘要

Skyline计算是要发现数据集中不被其他点支配的所有点的集合.近来,它在实时在线服务方面的良好应用前景,使其成为数据库研究领域的一个热点.实际应用中,用户通常期望快速、渐进地返回Skyline计算结果,因此文中主要讨论了高维空间子空间Skyline渐进查询问题.据我们所知,现有的Skyline计算方法都不能直接或者通过简单修改来高效解决该种查询问题.BNL(Blocked Nested Loop)算法是一个可用来进行子空间Skyline计算的算法,但是,该方法低效且非渐进.基于此,文中提出了在线高效子空间Skyline算法--CSky(Count the Skyline).该算法充分利用了一个新颖数据结构--InvertS的特征,即通过对目标数据集进行排序,存放最可能为Skyline点的数据于算法优先扫描的位置,这使得CSky算法能高效计算出任意子空间上的Skyline;同时,CSky每次计算子空间Skyline查询时,至多访问一遍数据库;再有,算法扫描一个点时,只需和当前已发现的Skyline点进行比较即能判断该点是否为Skyline点,保证了算法的渐进性.这样,相比BNL,CSky大大减少了计算开销,具有其他基于索引的Skyline算法计算Skyline时的高效,且这种高效适用于所有子空间.理论分析和实验表明,在解决高维空间子空间Skyline查询问题方面,CSky性能大大优于BNL.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	宫学庆	复旦大学计算机科学与工程系	9	224	5.0	9.0
2	周红福	复旦大学计算机科学与工程系	3	37	2.0	3.0
3	周傲英	复旦大学计算机科学与工程系	79	5708	32.0	75.0
4	郑凯	复旦大学计算机科学与工程系	3	36	2.0	3.0