RRR: Rank-Regret Representative

Summary: Rank-Regret Representative (RRR): minimal subset ensuring at least one of the top-k items for every possible ranking function (rank-based regret). NP-hard; uses geometric bounds and combinatorial approximations to compute compact, scalable representatives, validated on real datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5611
Venue: SIGMOD
Year: 2019
Pagerank: 4.9173197e-05
Overall Rank: 6,816 | 52.59%
DOI: 10.1145/3299869.3300080

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,597	Designing Fair Ranking Schemes	2019	SIGMOD	0.00011209846
5,024	Towards Distribution-aware Query Answering in Data Markets	2022	VLDB	5.7535043e-05
5,555	On Obtaining Stable Rankings	2019	VLDB	5.4386174e-05
7,002	Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size	2021	SIGMOD	4.8670742e-05
9,246	Happiness Maximizing Sets under Group Fairness Constraints	2023	VLDB	4.3690661e-05
9,775	Interactive Search for One of the Top-k	2021	SIGMOD	4.2856106e-05
10,223	On Fair Epsilon Net and Geometric Hitting Set	2026	VLDB	4.1945683e-05
10,555	Mining the Minoria: Unknown, Under-represented, and Under-performing Minority Groups	2025	VLDB	4.1945683e-05
11,195	rkHit: Representative Query with Uncertain Preference	2023	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
7	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015496097
430	The Onion Technique: Indexing for Linear Optimization Queries	2000	SIGMOD	0.00023463938
914	Finding k-Dominant Skylines in High Dimensional Space	2006	SIGMOD	0.00015387584
1,072	Regret-Minimizing Representative Databases	2010	VLDB	0.00014270817
1,597	Designing Fair Ranking Schemes	2019	SIGMOD	0.00011209846
2,478	Computing k-Regret Minimizing Sets	2014	VLDB	8.6927744e-05
2,615	Interactive Regret Minimization	2012	SIGMOD	8.4473503e-05
2,933	Answering Top-k Queries Using Views	2006	VLDB	7.8679669e-05
3,463	Towards Robust Indexing for Ranked Queries	2006	VLDB	7.069675e-05
5,116	Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative	2017	SIGMOD	5.6830089e-05
5,904	k-Regret Queries with Nonlinear Utilities	2015	VLDB	5.2790141e-05
6,843	Minimizing Average Regret Ratio in Database	2016	SIGMOD	4.909799e-05
8,129	Discovering the Skyline of Web Databases	2016	VLDB	4.5784968e-05
11,883	Query Reranking As A Service	2016	VLDB	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,615	Interactive Regret Minimization	2012	SIGMOD	8.4473503e-05
11,195	rkHit: Representative Query with Uncertain Preference	2023	SIGMOD	4.1945683e-05
7,632	Rank Aggregation with Proportionate Fairness	2022	SIGMOD	4.6915165e-05
5,255	Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality	2018	SIGMOD	5.6013035e-05
5,904	k-Regret Queries with Nonlinear Utilities	2015	VLDB	5.2790141e-05
2,478	Computing k-Regret Minimizing Sets	2014	VLDB	8.6927744e-05
6,843	Minimizing Average Regret Ratio in Database	2016	SIGMOD	4.909799e-05
5,116	Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative	2017	SIGMOD	5.6830089e-05
1,072	Regret-Minimizing Representative Databases	2010	VLDB	0.00014270817
6,834	A Unified Optimization Algorithm For Solving "Regret-Minimizing Representative" Problems	2020	VLDB	4.9117328e-05