(Author names are in alphabetical order.)
From a theoretical point of view, we develop a streaming algorithm that computes skyline in about $\log n$ passes and $m$ space where $n$ is the number of points and $m$ is the size of the skyline. We also extend it to fixed-window and distributed versions. Our experiment shows that our algorithm is comparable to other algorithms on in the average case and significantly faster even when the datasets are perturbed by just sorting.
We consider external algorithms for skyline computation without