K-Regret Queries Using Multiplicative Utility Functions
Jianzhong Qi, Fei Zuo, Hanan Samet, Jia Cheng Yao
ACM Transactions on Database Systems | Association for Computing Machinery | Published : 2018
The k-regret query aims to return a size-k subset S of a database D such that, for any query user that selects a data object from this size-k subset S rather than from database D, her regret ratio is minimized. The regret ratio here is modeled by the relative difference in the optimality between the locally optimal object in S and the globally optimal object in D. The optimality of a data object in turn is modeled by a utility function of the query user. Unlike traditional top-k queries, the k-regret query does not minimize the regret ratio for a specific utility function. Instead, it considers a family of infinite utility functions F, and aims to find a size-k subset that minimizes the maxi..View full abstract
Related Projects (2)
Awarded by Australian Research Council (ARC)
Awarded by National Science Foundation
This work is supported in part by Australian Research Council (ARC) Discovery Projects DP180102050 and DP180103332 and the National Science Foundation under Grant IIS-13-20791. We thank Dr. Ashwin Lall for sharing the code of Angle, AreaGreedy, and MinWidth.