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.2017.11
URN: urn:nbn:de:0030-drops-70569
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7056/
Go to the corresponding LIPIcs Volume Portal

Cao, Wei ; Li, Jian ; Wang, Haitao ; Wang, Kangning ; Wang, Ruosong ; Chi-Wing Wong, Raymond ; Zhan, Wei

k-Regret Minimizing Set: Efficient Algorithms and Hardness

pdf-format:
LIPIcs-ICDT-2017-11.pdf (0.7 MB)

Abstract

We study the k-regret minimizing query (k-RMS), which is a useful operator for supporting multi-criteria decision-making. Given two integers k and r, a k-RMS returns r tuples from the database which minimize the k-regret ratio, defined as one minus the worst ratio between the k-th maximum utility score among all tuples in the database and the maximum utility score of the r tuples returned. A solution set contains only r tuples, enjoying the benefits of both top-k queries and skyline queries. Proposed in 2012, the query has been studied extensively in recent years. In this paper, we advance the theory and the practice of k-RMS in the following aspects. First, we develop efficient algorithms for k-RMS (and its decision version) when the dimensionality is 2. The running time of our algorithms outperforms those of previous ones. Second, we show that k-RMS is NP-hard even when the dimensionality is 3. This provides a complete characterization of the complexity of k-RMS, and answers an open question in previous studies. In addition, we present approximation algorithms for the problem when the dimensionality is 3 or larger.

BibTeX - Entry

@InProceedings{cao_et_al:LIPIcs:2017:7056,
  author =	{Wei Cao and Jian Li and Haitao Wang and Kangning Wang and Ruosong Wang and Raymond Chi-Wing Wong and Wei Zhan},
  title =	{{k-Regret Minimizing Set: Efficient Algorithms and Hardness}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  pages =	{11:1--11:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Michael Benedikt and Giorgio Orsi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7056},
  URN =		{urn:nbn:de:0030-drops-70569},
  doi =		{10.4230/LIPIcs.ICDT.2017.11},
  annote =	{Keywords: multi-criteria decision-making, regret minimizing set, top-k query}
}

Keywords: multi-criteria decision-making, regret minimizing set, top-k query
Collection: 20th International Conference on Database Theory (ICDT 2017)
Issue Date: 2017
Date of publication: 17.03.2017

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