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: h1675c07168f3941b
Venue: SIGMOD
Year: 2019
Pagerank: 5.6966108e-05
Overall Rank: 6,721 | 54.83%
DOI: 10.1145/3299869.3300080

Incoming Non-self Citations Over Time

Authors

1. Abolfazl Asudeh (University of Michigan)
2. Azade Nazi (Google; University of Texas)
3. Nan Zhang (Pennsylvania State University)
4. Gautam Das (University of Texas)
5. H. V. Jagadish (University of Michigan)

BibTeX Citation

@inproceedings{asudeh_sigmod19,
        title = {{RRR: Rank-Regret Representative}},
        author = {Asudeh, Abolfazl and Nazi, Azade and Zhang, Nan and Das, Gautam and Jagadish, H. V.},
        series = {{SIGMOD} '19},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3299869.3300080},
        url = {https://dl.acm.org/doi/10.1145/3299869.3300080},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,379	Designing Fair Ranking Schemes	2019	SIGMOD	0.00010859038
5,418	Towards Distribution-aware Query Answering in Data Markets	2022	VLDB	6.1370792e-05
5,611	On Obtaining Stable Rankings	2019	VLDB	6.0657421e-05
6,761	Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size	2021	SIGMOD	5.6873442e-05
9,584	Happiness Maximizing Sets under Group Fairness Constraints	2023	VLDB	5.154741e-05
10,092	Interactive Search for One of the Top-k	2021	SIGMOD	5.0806786e-05
10,706	On Fair Epsilon Net and Geometric Hitting Set	2026	VLDB	4.9769913e-05
11,239	Mining the Minoria: Unknown, Under-represented, and Under-performing Minority Groups	2025	VLDB	4.9769913e-05
11,718	rkHit: Representative Query with Uncertain Preference	2023	SIGMOD	4.9769913e-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
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010679903
342	The Onion Technique: Indexing for Linear Optimization Queries	2000	SIGMOD	0.00020520649
818	Finding k-Dominant Skylines in High Dimensional Space	2006	SIGMOD	0.00013666302
1,087	Regret-Minimizing Representative Databases	2010	VLDB	0.00012092041
1,379	Designing Fair Ranking Schemes	2019	SIGMOD	0.00010859038
2,106	Computing k-Regret Minimizing Sets	2014	VLDB	9.0287481e-05
2,545	Interactive Regret Minimization	2012	SIGMOD	8.3139128e-05
2,561	Answering Top-k Queries Using Views	2006	VLDB	8.2940439e-05
3,070	Towards Robust Indexing for Ranked Queries	2006	VLDB	7.6831067e-05
4,833	Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative	2017	SIGMOD	6.3867086e-05
5,788	k-Regret Queries with Nonlinear Utilities	2015	VLDB	5.9926479e-05
7,034	Minimizing Average Regret Ratio in Database	2016	SIGMOD	5.614437e-05
8,554	Discovering the Skyline of Web Databases	2016	VLDB	5.3146691e-05
12,382	Query Reranking As A Service	2016	VLDB	4.9769913e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,545	Interactive Regret Minimization	2012	SIGMOD
2	11,718	rkHit: Representative Query with Uncertain Preference	2023	SIGMOD
3	7,595	Rank Aggregation with Proportionate Fairness	2022	SIGMOD
4	5,071	Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality	2018	SIGMOD
5	5,788	k-Regret Queries with Nonlinear Utilities	2015	VLDB
6	2,106	Computing k-Regret Minimizing Sets	2014	VLDB
7	7,034	Minimizing Average Regret Ratio in Database	2016	SIGMOD
8	4,833	Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative	2017	SIGMOD
9	1,087	Regret-Minimizing Representative Databases	2010	VLDB
10	6,920	A Unified Optimization Algorithm For Solving “Regret-Minimizing Representative” Problems	2020	VLDB