Sepanta Zeighami
Raymond Chi-Wing Wong
ABSTRACT
We propose "average regret ratio" as a metric to measure users' satisfaction after a user sees k selected points of a database, instead of all of the points in the database. We introduce the average regret ratio as another means of multi-criteria decision making. Unlike the original k-regret operator that uses the maximum regret ratio, the average regret ratio takes into account the satisfaction of a general user. While assuming the existence of some utility functions for the users, in contrast to the top-k query, it does not require a user to input his or her utility function but instead depends on the probability distribution of the utility functions. We prove that the average regret ratio is a supermodular function and provide a polynomial-time approximation algorithm to find the average regret ratio minimizing set for a database.
- S. Borzsony, D. Kossmann, and K. Stocker. The skyline operator. ICDE, 2001. Google Scholar
Digital Library
- V. P. Il'ev. An approximation guarantee of the greedy descent algorithm for minimizing a supermodular set function. Discrete Applied Mathematics, 114 (1--3): 131--146, October 2001.Google ScholarCross Ref
- X. Lin, Y. Yuan, Q. Zhang, and Y. Zhang. Selecting stars: The k most representative skyline operator. phICDE, 2007.Google Scholar
- D. Nanongkai, A. D. Sarma, A. Lall, R. J. Lipton, and J. Xu. Regret-minimizing representative databases. phVLDB, 2010. Google ScholarDigital Library
Index Terms
- Minimizing Average Regret Ratio in Database
Recommendations
Regret-minimizing representative databases
We propose the k-representative regret minimization query (k-regret) as an operation to support multi-criteria decision making. Like top-k, the k-regret query assumes that users have some utility or scoring functions; however, it never asks the users to ...
Regret to the best vs. regret to the average
We study online regret minimization algorithms in an experts setting. In this setting, the algorithm chooses a distribution over experts at each time step and receives a gain that is a weighted average of the experts' instantaneous gains. We consider a ...
Regret to the best vs. regret to the average
COLT'07: Proceedings of the 20th annual conference on Learning theoryWe study online regret minimization algorithms in a bicriteria setting, examining not only the standard notion of regret to the best expert, but also the regret to the average of all experts, the regret to any fixed mixture of experts, and the regret to ...
Comments