# Sampling Based Approximate Skyline Calculation on Big Data

arXiv: https://arxiv.org/abs/2008.05103 · HTML: https://mlsanity.com/paper/2008.05103/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Aug 2020.

## Built on by (most cited first, 1 of 1)

- [Rank-Regret Minimization](https://mlsanity.com/paper/2111.08563/) (2021)

## Abstract (arXiv)

The existing algorithms for processing skyline queries cannot adapt to big data. This paper proposes two approximate skyline algorithms based on sampling. The first algorithm obtains a fixed size sample and computes the approximate skyline on the sample. The error of the first algorithm is relatively small in most cases, and is almost independent of the input relation size. The second algorithm returns an (ε,δ)-approximation for the exact skyline. The size of sample required by the second algorithm can be regarded as a constant relative to the input relation size, so is the running time. Experiments verify the error analysis of the first algorithm and show that the second algorithm is much faster than the existing skyline algorithms.