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
5360
Venue
SIGMOD
Year
2017
Pagerank
6.5362946e-05
Overall Rank
4,727 | 67.57%
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,597 Designing Fair Ranking Schemes 2019 SIGMOD 0.00010246472
4,939 Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality 2018 SIGMOD 6.4336325e-05
5,465 On Obtaining Stable Rankings 2019 VLDB 6.2075408e-05
6,592 RRR: Rank-Regret Representative 2019 SIGMOD 5.830041e-05
6,636 Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size 2021 SIGMOD 5.8172769e-05
6,786 A Unified Optimization Algorithm For Solving “Regret-Minimizing Representative” Problems 2020 VLDB 5.7740702e-05
8,825 Creating Top Ranking Options in the Continuous Option and Preference Space 2019 VLDB 5.3616725e-05
9,393 Happiness Maximizing Sets under Group Fairness Constraints 2023 VLDB 5.2755515e-05
9,899 Minimum Coresets for Maxima Representation of Multidimensional Data 2021 PODS 5.1997534e-05
9,900 On m-Impact Regions and Standing Top-k Influence Problems 2021 SIGMOD 5.1997534e-05
11,397 rkHit: Representative Query with Uncertain Preference 2023 SIGMOD 5.093636e-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.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
2,063 Computing k-Regret Minimizing Sets 2014 VLDB 9.2399169e-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
5,654 k-Regret Queries with Nonlinear Utilities 2015 VLDB 6.1330869e-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
Previous Page 1 / 1 Next

Semantically Similar Papers

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