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/
Cao, Wei ;
Li, Jian ;
Wang, Haitao ;
Wang, Kangning ;
Wang, Ruosong ;
Chi-Wing Wong, Raymond ;
Zhan, Wei
k-Regret Minimizing Set: Efficient Algorithms and Hardness
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 |