基于网格索引的连续Skyline计算方法

考虑按任意顺序随机增删的数据流场景下连续Skyline计算问题,首先基于已有工作提出了一个基本算法BCSC;然后基于"影响区域"的观察,提出了一个基于网格索引数据结构的算法GICSC,其基本思想为:(1)将数据空间划分为若干大小相等的网格,采用网格索引方法对数据点进行组织和管理;(2)用网格将数据空间表示为自由区域和影响区域两部分,发生在自由区域中的数据变化可以从理论上保证不影响计算结果,因此仅需对落于影响区域的数据增删进行运算,从而降低数据规模;(3)算法的计算模块通过逐步扩展的方法,无需遍历全部数据便可获得初始的Skyline集合及影响区域,维护模块通过类似方法计算数据变化对Skyline集合的影响,同时动态更新影响区域的大小.由于没有对数据流特性进行假设限制,因此BCSC和GICSC算法具有更广泛的适应性.理论分析和实验结果均验证了上述方法的有效性.

Grid Index Based Algorithm for Continuous Skyline Computation

This paper addresses the problem of continuous Skyline computation on streams with random additions and deletions.A straightforward method called BCSC(Basic Continuous Skyline Computation algorithm) is firstly raised,then a Grid Index based Continuous Skyline Computation algorithm(GICSC) is presented based on the observation of influence region.The main idea of GICSC is as follows:(1)The work space is divided into lots of regular grids,and the valid data points are indexed and managed by this grid structure;(2)Some grids are organized as the influence region,while the rest compose of the free region.GICSC achieves low running time by handling data additions/deletions only from points that fall in the influence region,while data changes in the free region are omitted with correctness guarantee.(3)The computation module adopts a smart method to obtain the initial Skyline set and influence region without having to process all the data points;after that the maintenance module computes the change of Skyline and maintains the influence region dynamically when data changes.Since there is no assumption limitation of stream characters,the BCSC and GICSC algorithms are more adaptive.Analytical and experimental evidences show the efficiency of proposed approaches.