Grid Index Based Algorithm for Continuous Skyline Computation
Li Si Ai · Chinese Journal of Computers · 2008
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.