k-Regret Minimizing Set: Efficient Algorithms and Hardness
k-Regret Minimizing Set: Efficient Algorithms and Hardness
复制标题
DOI：
10.4230/lipics.icdt.2017.11
复制
发表时间：
2017
期刊：
影响因子：
1.1
通讯作者：
Wei Cao;J. Li;Haitao Wang;Kangning Wang;Ruosong Wang;R. C. Wong;Wei Zhan
中科院分区：
文献类型：
--
作者：
Wei Cao;J. Li;Haitao Wang;Kangning Wang;Ruosong Wang;R. C. Wong;Wei Zhan
我们研究了k-后悔最小化查询（k-RMS），这是一个有用的运营商，支持多准则决策。给定两个整数k和r，k-RMS从数据库中返回r个元组，使k后悔率最小化，k后悔率定义为1减去数据库中所有元组中第k个最大效用分数与返回的r个元组的最大效用分数之间的最差比率。解决方案集只包含r元组，享受top-k查询和skyline查询的好处。该查询于2012年提出，近年来得到了广泛的研究。本文从以下几个方面对k-RMS的理论和实践进行了研究。首先，当维数为2时，我们为k-RMS（及其决策版本）开发了有效的算法。我们的算法的运行时间优于以前的。其次，我们证明了即使当维数为3时，k-RMS也是NP-难的。这提供了一个完整的表征的复杂性k-RMS，并回答了一个悬而未决的问题，在以前的研究。此外，我们提出了近似算法的问题时，维数为3或更大。
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.