Maintaining sliding window skylines on data streams
- 30 January 2006
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 18 (3), 377-391
- https://doi.org/10.1109/tkde.2006.48
Abstract
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
This publication has 25 references indexed in Scilit:
- Skyline Cardinality for Relational ProcessingLecture Notes in Computer Science, 2004
- Memory-Limited Execution of Windowed Stream JoinsPublished by Elsevier BV ,2004
- Efficient approximation of correlated sums on data streamsIEEE Transactions on Knowledge and Data Engineering, 2003
- Processing Sliding Window Multi-Joins in Continuous Queries over Data StreamsPublished by Elsevier BV ,2003
- Optimizing multidimensional index trees for main memory accessPublished by Association for Computing Machinery (ACM) ,2001
- On computing correlated aggregates over continual data streamsACM SIGMOD Record, 2001
- Distance browsing in spatial databasesACM Transactions on Database Systems, 1999
- Geometric range searching and its relativesPublished by American Mathematical Society (AMS) ,1999
- A Functional Approach to Data Structures and Its Use in Multidimensional SearchingSIAM Journal on Computing, 1988
- On Finding the Maxima of a Set of VectorsJournal of the ACM, 1975