Database Paper Browser

Back to papers

Regret-Minimizing Representative Databases

Summary: Introduces k-regret queries that output k representative tuples for multi-criteria decision making without user-provided utility functions. Proves a maximum regret ratio bound independent of database size and offers linear-time algorithms compatible with skyline, validated on real and synthetic data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
10154
Venue
VLDB
Year
2010
Pagerank
0.00014270817
Overall Rank
1,072 | 92.55%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 26 of 26 citing papers.

Rank Citing Paper Year Venue Pagerank
1,597 Designing Fair Ranking Schemes 2019 SIGMOD 0.00011209846
2,478 Computing k-Regret Minimizing Sets 2014 VLDB 8.6927744e-05
2,615 Interactive Regret Minimization 2012 SIGMOD 8.4473503e-05
5,116 Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative 2017 SIGMOD 5.6830089e-05
5,255 Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality 2018 SIGMOD 5.6013035e-05
5,555 On Obtaining Stable Rankings 2019 VLDB 5.4386174e-05
5,904 k-Regret Queries with Nonlinear Utilities 2015 VLDB 5.2790141e-05
6,387 Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings 2018 VLDB 5.0851965e-05
6,391 k-Hit Query: Top-k Query with Probabilistic Utility Function 2015 SIGMOD 5.0842079e-05
6,816 RRR: Rank-Regret Representative 2019 SIGMOD 4.9173197e-05
6,834 A Unified Optimization Algorithm For Solving "Regret-Minimizing Representative" Problems 2020 VLDB 4.9117328e-05
6,843 Minimizing Average Regret Ratio in Database 2016 SIGMOD 4.909799e-05
6,909 FindYourFavorite: An Interactive System for Finding the User's Favorite Tuple in the Database 2019 SIGMOD 4.8925595e-05
7,002 Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size 2021 SIGMOD 4.8670742e-05
7,559 Strongly Truthful Interactive Regret Minimization 2019 SIGMOD 4.7107487e-05
8,715 Data Driven Approximation with Bounded Resources 2017 VLDB 4.4619052e-05
8,877 Creating Top Ranking Options in the Continuous Option and Preference Space 2019 VLDB 4.4302563e-05
9,246 Happiness Maximizing Sets under Group Fairness Constraints 2023 VLDB 4.3690661e-05
9,772 Minimum Coresets for Maxima Representation of Multidimensional Data 2021 PODS 4.2856106e-05
9,774 On m-Impact Regions and Standing Top-k Influence Problems 2021 SIGMOD 4.2856106e-05
9,775 Interactive Search for One of the Top-k 2021 SIGMOD 4.2856106e-05
10,223 On Fair Epsilon Net and Geometric Hitting Set 2026 VLDB 4.1945683e-05
10,986 Directional Queries: Making Top-k Queries More Effective in Discovering Relevant Results 2024 SIGMOD 4.1945683e-05
11,040 Robust Best Point Selection under Unreliable User Feedback 2024 VLDB 4.1945683e-05
11,195 rkHit: Representative Query with Uncertain Preference 2023 SIGMOD 4.1945683e-05
11,378 Interactive Mining with Ordered and Unordered Attributes 2022 VLDB 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
430 The Onion Technique: Indexing for Linear Optimization Queries 2000 SIGMOD 0.00023463938
465 PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries 2001 SIGMOD 0.00022455702
914 Finding k-Dominant Skylines in High Dimensional Space 2006 SIGMOD 0.00015387584
1,998 Discovering Relative Importance of Skyline Attributes 2009 VLDB 9.824482e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,346 Multi-objective Query Processing for Database Systems 2004 VLDB 8.9919258e-05
2,478 Computing k-Regret Minimizing Sets 2014 VLDB 8.6927744e-05
6,816 RRR: Rank-Regret Representative 2019 SIGMOD 4.9173197e-05
7,559 Strongly Truthful Interactive Regret Minimization 2019 SIGMOD 4.7107487e-05
6,834 A Unified Optimization Algorithm For Solving "Regret-Minimizing Representative" Problems 2020 VLDB 4.9117328e-05
5,116 Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative 2017 SIGMOD 5.6830089e-05
2,615 Interactive Regret Minimization 2012 SIGMOD 8.4473503e-05
5,904 k-Regret Queries with Nonlinear Utilities 2015 VLDB 5.2790141e-05
5,255 Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality 2018 SIGMOD 5.6013035e-05
6,843 Minimizing Average Regret Ratio in Database 2016 SIGMOD 4.909799e-05