2007 | OriginalPaper | Buchkapitel
Continuous Skyline Tracking on Update Data Streams
verfasst von : Li Tian, Le Wang, AiPing Li, Peng Zou, Yan Jia
Erschienen in: Advances in Web and Network Technologies, and Information Management
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 consider the continuous skyline computation in a new scenario named as
update stream
, where the
First-In-First-Out
rule (which is the basic character in sliding window model) does not hold, causing the existing algorithms inapplicable. An algorithm called
BUSM
is developed and analyzed, which can continuous compute the change of skyline caused by update messages; then a progressive algorithm
GUSM
based on a novel grid-indexed data structure is proposed, which makes use of the character that deletion and addition operation appears simultaneously in update streams, and represents the influence region by grids for early elimination. Analytical analysis and experimental evidences show the efficiency of proposed approaches.