Diversity and Freshness-Aware Regret Minimizing Set Queries

Multi-criteria decision-making often involves selecting a small representative set from a database. A recently proposed method is the regret minimization set (RMS) queries. It aims to rectify the shortcomings of needing a utility function in top-k queries and the overly large result size of skyline queries. However, the existing definition of RMS only ensures one result under any utility function, and do not consider the diversity and freshness of the returned results. In this paper, we define a strong regret set, which guarantees the utility value error of k data points under any utility function. Given this new definition, we propose two problems, namely the Minimum Size problem and the Max-sum Diversity and Freshness problem. Both proposed problems have been proven to be NP-hard. Correspondingly, we devise approximation algorithms for them, and analyze algorithms’ time complexities and the approximation ratios of the solutions obtained.