Explanations for Skyline Query Results

TY - GEN

T1 - Explanations for Skyline Query Results

AU - Chester, Sean

AU - Assent, Ira

N1 - Conference code: 18

PY - 2015/3

Y1 - 2015/3

N2 - Skyline queries are a well-studied problem for multidimensional data, wherein points are returned to the user iff no other point is preferable across all attributes. This leaves only the points most likely to appeal to an arbitrary user.However, some dominated points may still be interesting, and the skyline offers little support for helping the user understand why some interesting points are omitted from the results. In this paper, we introduce the Sky-not query. Givena query point p, a dataset S, and constraints with bounding corners qL and qU, the Sky-not query returns the alternative constraints qL' closest to qL for which p is in the skyline. This equips the user with an understanding of not just thata point was dominated, but also how severely. He can then assess himself whether the point is competitive.We first propose theoretical results that show how to drastically reduce the input processed by a Sky-not query, independent of any algorithm. We then offer a skyline-like and an efficient recursive algorithm for solving Sky-not queries, which we evaluate in an extensive experimental evaluation.

AB - Skyline queries are a well-studied problem for multidimensional data, wherein points are returned to the user iff no other point is preferable across all attributes. This leaves only the points most likely to appeal to an arbitrary user.However, some dominated points may still be interesting, and the skyline offers little support for helping the user understand why some interesting points are omitted from the results. In this paper, we introduce the Sky-not query. Givena query point p, a dataset S, and constraints with bounding corners qL and qU, the Sky-not query returns the alternative constraints qL' closest to qL for which p is in the skyline. This equips the user with an understanding of not just thata point was dominated, but also how severely. He can then assess himself whether the point is competitive.We first propose theoretical results that show how to drastically reduce the input processed by a Sky-not query, independent of any algorithm. We then offer a skyline-like and an efficient recursive algorithm for solving Sky-not queries, which we evaluate in an extensive experimental evaluation.

KW - skyline

KW - explanation

KW - user interaction

U2 - 10.5441/002/edbt.2015.31

DO - 10.5441/002/edbt.2015.31

M3 - Article in proceedings

SN - 978-3-89318-067-7

SP - 349

EP - 360

BT - International Conference on Extending Database Technology (EDBT 2015)

PB - openproceedings.org

T2 - International Conference on Extending Database Technology

Y2 - 23 March 2015 through 27 March 2015

ER -