Efficient Algorithms for Rank-Regret Minimization

Xingxing Xiao

doi:10.1109/TKDE.2024.3363009

Efficient Algorithms for Rank-Regret Minimization

2024-08-01

0

PRE

AI

DOI：10.1109/TKDE.2024.3363009

原文链接

原文求助

摘要

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.

Keyword:

Automobiles

Databases

Approximation algorithms

Minimization

Clustering algorithms

Logistics

Decision making

Multi-criteria decision-making

rank-regret

regret-ratio

skyline

top-k query

Efficient Algorithms for Rank-Regret Minimization

摘要

期刊

机构