Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

4-2010

Abstract

We address the problem of skyline query processing for a count-based window of continuous streaming data that involves both totally- and partially-ordered attribute domains. In this problem, a fixed-size buffer of the N most recent tuples is dynamically maintained and the key challenge is how to efficiently maintain the skyline of the sliding window of N tuples as new tuples arrive and old tuples expire. We identify the limitations of the state-of-the-art approach STARS, and propose two new approaches, STARS+ and SkyGrid, to address its drawbacks. STARS+ is an enhancement of STARS with three new optimization techniques, while SkyGrid is a simplification STARS that eliminates a key data structure used in STARS. While both new approaches outperform STARS significantly, the surprising result is that the best approach turns out to be the simplest approach, SkyGrid.

Keywords

N-tuples, New approaches, Optimization techniques, Ordered domains, Sliding Window, State-of-the-art approach, Streaming data

Discipline

Databases and Information Systems

Research Areas

Data Science and Engineering

Publication

Database systems for advanced applications: 15th international conference, DASFAA 2010, Tsukuba, Japan, April 1-4: Proceedings

Volume

5981

First Page

322

Last Page

336

ISBN

9783642120251

Identifier

10.1007/978-3-642-12026-8_26

Publisher

Springer

City or Country

Cham

Additional URL

https://doi.org/10.1007/978-3-642-12026-8_26

Download

Share

COinS