Please use this identifier to cite or link to this item:
Title: Efficient updates for continuous skyline computations
Authors: Hsueh, Y.-L.
Zimmermann, R. 
Ku, W.-S.
Issue Date: 2008
Citation: Hsueh, Y.-L.,Zimmermann, R.,Ku, W.-S. (2008). Efficient updates for continuous skyline computations. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 5181 LNCS : 419-433. ScholarBank@NUS Repository.
Abstract: We address the problem of maintaining continuous skyline queries efficiently over dynamic objects with d dimensions. Skyline queries are an important new search capability for multi-dimensional databases. In contrast to most of the prior work, we focus on the unresolved issue of frequent data object updates. In this paper we propose the ESC algorithm, an Efficient update approach for Skyline Computations, which creates a pre-computed second skyline set that facilitates an efficient and incremental skyline update strategy and results in a quicker response time. With the knowledge of the second skyline set, ESC enables (1) to efficiently find the substitute skyline points from the second skyline set only when removing or updating a skyline point (which we call a first skyline point) and (2) to delegate the most time-consuming skyline update computation to another independent procedure, which is executed after the complete updated query result is reported. We leverage the basic idea of the traditional BBS skyline algorithm for our novel design of a two-threaded approach. The first skyline can be replenished quickly from a small set of second skylines - hence enabling a fast query response time - while de-coupling the computationally complex maintenance of the second skyline. Furthermore, we propose the Approximate Exclusive Data Region algorithm (AEDR) to reduce the computational complexity of determining a candidate set for second skyline updates. In this paper, we evaluate the ESC algorithm through rigorous simulations and compare it with existing techniques. We present experimental results to demonstrate the performance and utility of our novel approach. © 2008 Springer-Verlag Berlin Heidelberg.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISBN: 3540856536
ISSN: 03029743
DOI: 10.1007/978-3-540-85654-2_38
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Dec 17, 2018

Page view(s)

checked on Dec 15, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.