“Skyline Queries with Noisy Comparisons” by Benoît Groz and Tova Milo has been accepted for publication in ACM PODS 2015.
Abstract: We study in this paper the computation of skyline queries – a popular tool for multicriteria data analysis – in
the presence of noisy input. Motivated by crowdsourcing applications, we focus on a computation model where the input data items can only be compared through noisy comparisons and present the first algorithms for skyline evaluation in this context.
Specifically, we aim at minimizing the number of comparisons required for computing or verifying a candidate skyline, while returning the correct answer with high probability.
We design output-sensitive algorithms, namely algorithms that take advantage of the potentially small size of the skyline, and analyze the delay (number of comparison rounds) of our solutions.
We also consider the problem of predicting the most likely skyline given some partial information in the form of noisy comparisons, and show that optimal prediction is computationally intractable.
