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: 5673
Venue: SIGMOD
Year: 2019
Pagerank: 5.830041e-05
Overall Rank: 6,592 | 54.78%
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,597	Designing Fair Ranking Schemes	2019	SIGMOD	0.00010246472
5,300	Towards Distribution-aware Query Answering in Data Markets	2022	VLDB	6.2751506e-05
5,465	On Obtaining Stable Rankings	2019	VLDB	6.2075408e-05
6,636	Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size	2021	SIGMOD	5.8172769e-05
9,393	Happiness Maximizing Sets under Group Fairness Constraints	2023	VLDB	5.2755515e-05
9,901	Interactive Search for One of the Top-k	2021	SIGMOD	5.1997534e-05
10,511	On Fair Epsilon Net and Geometric Hitting Set	2026	VLDB	5.093636e-05
10,823	Mining the Minoria: Unknown, Under-represented, and Under-performing Minority Groups	2025	VLDB	5.093636e-05
11,397	rkHit: Representative Query with Uncertain Preference	2023	SIGMOD	5.093636e-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.0010828372
333	The Onion Technique: Indexing for Linear Optimization Queries	2000	SIGMOD	0.0002089582
792	Finding k-Dominant Skylines in High Dimensional Space	2006	SIGMOD	0.00013979615
1,072	Regret-Minimizing Representative Databases	2010	VLDB	0.0001230281
1,597	Designing Fair Ranking Schemes	2019	SIGMOD	0.00010246472
2,063	Computing k-Regret Minimizing Sets	2014	VLDB	9.2399169e-05
2,491	Interactive Regret Minimization	2012	SIGMOD	8.5086491e-05
2,525	Answering Top-k Queries Using Views	2006	VLDB	8.4653166e-05
3,007	Towards Robust Indexing for Ranked Queries	2006	VLDB	7.8583548e-05
4,727	Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative	2017	SIGMOD	6.5362946e-05
5,654	k-Regret Queries with Nonlinear Utilities	2015	VLDB	6.1330869e-05
6,886	Minimizing Average Regret Ratio in Database	2016	SIGMOD	5.7460174e-05
8,378	Discovering the Skyline of Web Databases	2016	VLDB	5.4387677e-05
12,083	Query Reranking As A Service	2016	VLDB	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,491	Interactive Regret Minimization	2012	SIGMOD
2	11,397	rkHit: Representative Query with Uncertain Preference	2023	SIGMOD
3	7,449	Rank Aggregation with Proportionate Fairness	2022	SIGMOD
4	4,939	Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality	2018	SIGMOD
5	5,654	k-Regret Queries with Nonlinear Utilities	2015	VLDB
6	2,063	Computing k-Regret Minimizing Sets	2014	VLDB
7	6,886	Minimizing Average Regret Ratio in Database	2016	SIGMOD
8	4,727	Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative	2017	SIGMOD
9	1,072	Regret-Minimizing Representative Databases	2010	VLDB
10	6,786	A Unified Optimization Algorithm For Solving “Regret-Minimizing Representative” Problems	2020	VLDB