Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative

Summary: Compact regret-ratio set as a maxima for linear preferences, smaller than the convex hull. 2D: optimal linearithmic skyline; higher dims NP-hard; offers linearithmic-time approximation with tunable regret guarantees; experiments confirm efficiency. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h13a0e400fcf62bf4
Venue: SIGMOD
Year: 2017
Pagerank: 6.3867086e-05
Overall Rank: 4,833 | 67.52%
DOI: 10.1145/3035918.3035932

Incoming Non-self Citations Over Time

Authors

1. Abolfazl Asudeh (University of Texas)
2. Azade Nazi (University of Texas)
3. Nan Zhang (George Washington University)
4. Gautam Das (University of Texas)

BibTeX Citation

@inproceedings{asudeh_sigmod17,
        title = {{Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative}},
        author = {Asudeh, Abolfazl and Nazi, Azade and Zhang, Nan and Das, Gautam},
        series = {{SIGMOD} '17},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3035918.3035932},
        url = {https://dl.acm.org/doi/10.1145/3035918.3035932},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,379	Designing Fair Ranking Schemes	2019	SIGMOD	0.00010859038
5,071	Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality	2018	SIGMOD	6.2863925e-05
5,611	On Obtaining Stable Rankings	2019	VLDB	6.0657421e-05
6,721	RRR: Rank-Regret Representative	2019	SIGMOD	5.6966108e-05
6,761	Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size	2021	SIGMOD	5.6873442e-05
6,920	A Unified Optimization Algorithm For Solving “Regret-Minimizing Representative” Problems	2020	VLDB	5.6418435e-05
9,002	Creating Top Ranking Options in the Continuous Option and Preference Space	2019	VLDB	5.23944e-05
9,584	Happiness Maximizing Sets under Group Fairness Constraints	2023	VLDB	5.154741e-05
10,090	Minimum Coresets for Maxima Representation of Multidimensional Data	2021	PODS	5.0806786e-05
10,091	On m-Impact Regions and Standing Top-k Influence Problems	2021	SIGMOD	5.0806786e-05
11,718	rkHit: Representative Query with Uncertain Preference	2023	SIGMOD	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 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
2,106	Computing k-Regret Minimizing Sets	2014	VLDB	9.0287481e-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
5,788	k-Regret Queries with Nonlinear Utilities	2015	VLDB	5.9926479e-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	7,456	Strongly Truthful Interactive Regret Minimization	2019	SIGMOD
2	5,788	k-Regret Queries with Nonlinear Utilities	2015	VLDB
3	2,545	Interactive Regret Minimization	2012	SIGMOD
4	6,721	RRR: Rank-Regret Representative	2019	SIGMOD
5	1,214	Maximal Vector Computation in Large Data Sets	2005	VLDB
6	5,071	Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality	2018	SIGMOD
7	7,034	Minimizing Average Regret Ratio in Database	2016	SIGMOD
8	1,087	Regret-Minimizing Representative Databases	2010	VLDB
9	2,106	Computing k-Regret Minimizing Sets	2014	VLDB
10	6,920	A Unified Optimization Algorithm For Solving “Regret-Minimizing Representative” Problems	2020	VLDB