DBScholar

Back to papers

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.3897334e-05
Overall Rank
4,831 | 67.53%
DOI
10.1145/3035918.3035932

Incoming Non-self Citations Over Time

Authors

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.0001086418
5,068 Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality 2018 SIGMOD 6.2893698e-05
5,610 On Obtaining Stable Rankings 2019 VLDB 6.0686149e-05
6,716 RRR: Rank-Regret Representative 2019 SIGMOD 5.6993087e-05
6,756 Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size 2021 SIGMOD 5.6900378e-05
6,918 A Unified Optimization Algorithm For Solving “Regret-Minimizing Representative” Problems 2020 VLDB 5.6445155e-05
8,993 Creating Top Ranking Options in the Continuous Option and Preference Space 2019 VLDB 5.2419215e-05
9,576 Happiness Maximizing Sets under Group Fairness Constraints 2023 VLDB 5.1571823e-05
10,085 Minimum Coresets for Maxima Representation of Multidimensional Data 2021 PODS 5.0830849e-05
10,086 On m-Impact Regions and Standing Top-k Influence Problems 2021 SIGMOD 5.0830849e-05
11,712 rkHit: Representative Query with Uncertain Preference 2023 SIGMOD 4.9793485e-05
Previous Page 1 / 1 Next

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.0010679641
342 The Onion Technique: Indexing for Linear Optimization Queries 2000 SIGMOD 0.00020530255
817 Finding k-Dominant Skylines in High Dimensional Space 2006 SIGMOD 0.00013672764
1,087 Regret-Minimizing Representative Databases 2010 VLDB 0.00012097722
2,105 Computing k-Regret Minimizing Sets 2014 VLDB 9.0330207e-05
2,561 Answering Top-k Queries Using Views 2006 VLDB 8.2977193e-05
3,068 Towards Robust Indexing for Ranked Queries 2006 VLDB 7.6867401e-05
5,786 k-Regret Queries with Nonlinear Utilities 2015 VLDB 5.9954861e-05
8,547 Discovering the Skyline of Web Databases 2016 VLDB 5.3171862e-05
12,376 Query Reranking As A Service 2016 VLDB 4.9793485e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 7,452 Strongly Truthful Interactive Regret Minimization 2019 SIGMOD
2 5,786 k-Regret Queries with Nonlinear Utilities 2015 VLDB
3 2,545 Interactive Regret Minimization 2012 SIGMOD
4 6,716 RRR: Rank-Regret Representative 2019 SIGMOD
5 1,213 Maximal Vector Computation in Large Data Sets 2005 VLDB
6 5,068 Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality 2018 SIGMOD
7 7,032 Minimizing Average Regret Ratio in Database 2016 SIGMOD
8 1,087 Regret-Minimizing Representative Databases 2010 VLDB
9 2,105 Computing k-Regret Minimizing Sets 2014 VLDB
10 6,918 A Unified Optimization Algorithm For Solving “Regret-Minimizing Representative” Problems 2020 VLDB