2008 | OriginalPaper | Buchkapitel
Efficient Updates for Continuous Skyline Computations
verfasst von : Yu-Ling Hsueh, Roger Zimmermann, Wei-Shinn Ku
Erschienen in: Database and Expert Systems Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
E
fficient update approach for
S
kyline
C
omputations, 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.