License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2019.10
URN: urn:nbn:de:0030-drops-103125
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10312/
Go to the corresponding LIPIcs Volume Portal

Kumar, Nirman ; Raichel, Benjamin ; Sintos, Stavros ; Van Buskirk, Gregory

Approximating Distance Measures for the Skyline

pdf-format:
LIPIcs-ICDT-2019-10.pdf (0.7 MB)

Abstract

In multi-parameter decision making, data is usually modeled as a set of points whose dimension is the number of parameters, and the skyline or Pareto points represent the possible optimal solutions for various optimization problems. The structure and computation of such points have been well studied, particularly in the database community. As the skyline can be quite large in high dimensions, one often seeks a compact summary. In particular, for a given integer parameter k, a subset of k points is desired which best approximates the skyline under some measure. Various measures have been proposed, but they mostly treat the skyline as a discrete object. By viewing the skyline as a continuous geometric hull, we propose a new measure that evaluates the quality of a subset by the Hausdorff distance of its hull to the full hull. We argue that in many ways our measure more naturally captures what it means to approximate the skyline.
For our new geometric skyline approximation measure, we provide a plethora of results. Specifically, we provide (1) a near linear time exact algorithm in two dimensions, (2) APX-hardness results for dimensions three and higher, (3) approximation algorithms for related variants of our problem, and (4) a practical and efficient heuristic which uses our geometric insights into the problem, as well as various experimental results to show the efficacy of our approach.

BibTeX - Entry

@InProceedings{kumar_et_al:LIPIcs:2019:10312,
  author =	{Nirman Kumar and Benjamin Raichel and Stavros Sintos and Gregory Van Buskirk},
  title =	{{Approximating Distance Measures for the Skyline}},
  booktitle =	{22nd International Conference on Database Theory (ICDT 2019)},
  pages =	{10:1--10:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-101-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{127},
  editor =	{Pablo Barcelo and Marco Calautti},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10312},
  doi =		{10.4230/LIPIcs.ICDT.2019.10},
  annote =	{Keywords: Skyline, Pareto optimal, Approximation, Hardness, Multi-criteria decision making}
}

Keywords: Skyline, Pareto optimal, Approximation, Hardness, Multi-criteria decision making
Collection: 22nd International Conference on Database Theory (ICDT 2019)
Issue Date: 2019
Date of publication: 19.03.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI