.png){kind=icon}
.png){kind=icon}
Return
Maintaining sliding window skylines on data streams
.png){kind=icon}
OA
AI
DOI：10.1109/TKDE.2006.48.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The skyline of a multidimensional data set contains the best tuples according to any preference function that is monotonic on each dimension. Although skyline computation has received considerable attention in conventional databases, the existing algorithms are inapplicable to stream applications because 1) they assume static data that are stored in the disk ( rather than continuously arriving/expiring), 2) they focus on one-time execution that returns a single skyline ( in contrast to constantly tracking skyline changes), and 3) they aim at reducing the I/O overhead ( as opposed to minimizing the CPU-cost and main-memory consumption). This paper studies skyline computation in stream environments, where query processing takes into account only a sliding window covering the most recent tuples. We propose algorithms that continuously monitor the incoming data and maintain the skyline incrementally. Our techniques utilize several interesting properties of stream skylines to improve space/time efficiency by expunging data from the system as early as possible (i.e., before their expiration). Furthermore, we analyze the asymptotical performance of the proposed solutions, and evaluate their efficiency with extensive experiments.
Keywords:
skyline
stream
database
algorithm
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
10.4
Papers:
6.8K
Citations:
3.2W
Organization
No organization information available