Chinese Journal of Computers   Full Text
Title	Grid Index Based Algorithm for Continuous Skyline Computation
Authors	TIAN Li ZOU Peng LI Ai-Ping JIA Yan
Address	(School of Computer, National University of Defense Technology, Changsha 410073)
Year	2008
Issue	No.6(998—1012)
Abstract &   Background	Abstract 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. Keywords continuous Skyline computation; data stream; grid indexed data structure Background Skyline and other directly related problems, such as multi-objective optimization and maximum vectors, can be found in a wide spectrum of optimization applications are and have been extensively studied. Recently a new class of data-intensive applications which is modeled as data stream has been widely researched. We consider continuous-query based applications and address the problem of continuous Skyline computation on streams with random additions and deletions, which is quite different from the sliding window streams scene and moving objects environment. A straightforward method called BCSC and a novel grid indexed based algorithm called GICSC are presented in this paper, which are designed specially for the high dynamic scenario and proved to be efficient and powerful. This work is supported by the National High-Tech Research and Development Plan of China ("863" plan) under Grant Nos.2006AA01Z451, 2007AA01Z474.