动态空间集下的轮廓更新算法  

Skyline Updating Algorithm in Dynamic Space Set

作　　者：董雷刚[1] 崔晓微[1] 

机构地区：[1]燕山大学信息科学与工程学院,秦皇岛066004

出　　处：《计算机工程》2009年第22期82-83,87,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(60773100);国家"十一五"科技支撑计划基金资助项目(2006BAK05B02)

摘　　要：现有的轮廓查询算法都是针对静态空间集设计的,不适用于空间集变化的情况。针对上述问题,提出动态空间集下的轮廓更新算法。当空间集发生变化导致现有轮廓失效时,无须重新计算所有数据点,只需在共享策略的基础上对部分数据点进行判断,即可快速完成轮廓的更新。理论分析和实验结果证明,该算法可有效减少冗余操作,保证结果的正确性和完整性。The existent skyline query algorithms are designed for static space sets, so they are not suitable for dynamic space sets. Aiming at such problem, this paper proposes a skyline updating algorithm in dynamic space set. When the change of space size leads to the existent skyline invalid, the algorithm can quickly finish updating the skyline by testing partial points based on sharing strategy without computing all the points again. Theoretical analysis and experimental result show that the algorithm can decrease repeat work effectively, and ensure the validity and integrality of query results.

关 键 词：轮廓 动态空间集 共享策略 轮廓更新 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]