Journal article

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