Explanations for Skyline Query Results

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

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. Given
a 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 that
a 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.
Original languageEnglish
Title of host publicationInternational Conference on Extending Database Technology (EDBT 2015)
Number of pages12
Publication yearMar 2015
ISBN (print)978-3-89318-067-7
Publication statusPublished - Mar 2015
EventInternational Conference on Extending Database Technology - Brussels, Belgium
Duration: 23 Mar 201527 Mar 2015
Conference number: 18


ConferenceInternational Conference on Extending Database Technology

    Research areas

  • skyline, explanation, user interaction

See relations at Aarhus University Citationformats



ID: 83938735