.png){kind=icon}
.png){kind=icon}
Return
Efficient Algorithms for Rank-Regret Minimization
.png){kind=icon}
PRE
AI
DOI：10.1109/TKDE.2024.3363009.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Multi-criteria decision-making usually requires finding a small representative set from the database. A popular method, the regret minimization set (RMS) query, returns a size r subset S of the full dataset $D$D that minimizes the regret-ratio (the difference between the scores of top-1 in S and top-1 in D, for any utility function). RMS is not shift invariant, causing inconsistency in results. Further, the regret-ratio is often a made up number and users may mistake its absolute value. Instead, users do understand the notion of rank. Therefore, in this paper, we consider finding a fixed-size set S to minimize the maximum rank-regret (the rank of top-1 of S in the sorted list of D) over all possible utility functions, called the rank-regret minimization (RRM) problem, which is shift invariant. In 2D space, we design an exact algorithm 2DRRM for RRM. In HD space, we propose an approximate algorithm HDRRM with theoretical guarantees on rank-regret. It combines the ideas of space discretization and clustering. Extensive experiments verify the efficiency and effectiveness of our algorithms. In particular, HDRRM always has the best output quality in experiments.
Keywords:
Automobiles
Databases
Approximation algorithms
Minimization
Clustering algorithms
Logistics
Decision making
Multi-criteria decision-making
rank-regret
regret-ratio
skyline
top-k query
Journal
IF:
10.4
Papers:
6.8K
Citations:
3.2W