Regret-Minimizing Representative Databases

Summary: Introduces k-regret queries: selecting k tuples without eliciting utility functions, while minimizing worst-case regret relative to the full database. For linear utilities, proves database-size-independent bounds and gives practical linear-time, skyline-based algorithms. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: hc82affef8dd14a79
Venue: VLDB
Year: 2010
Pagerank: 0.00012097722
Overall Rank: 1,087 | 92.70%
DOI: 10.14778/1920841.1920983

Incoming Non-self Citations Over Time

Authors

1. Danupon Nanongkai (Georgia Institute of Technology)
2. Atish Das Sarma (Georgia Institute of Technology)
3. Ashwin Lall (Georgia Institute of Technology)
4. Richard J. Lipton (Georgia Institute of Technology)
5. Jun Xu (Georgia Institute of Technology)

BibTeX Citation

@article{nanongkai_vldb10,
        title = {{Regret-Minimizing Representative Databases}},
        author = {Nanongkai, Danupon and Sarma, Atish Das and Lall, Ashwin and Lipton, Richard J. and Xu, Jun},
        journal = {PVLDB},
        series = {{VLDB} '10},
        volume = {3},
        number = {1},
        pages = {1114--1125},
        doi = {10.14778/1920841.1920983},
        url = {https://doi.org/10.14778/1920841.1920983},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 26 of 26 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,379	Designing Fair Ranking Schemes	2019	SIGMOD	0.0001086418
2,105	Computing k-Regret Minimizing Sets	2014	VLDB	9.0330207e-05
2,545	Interactive Regret Minimization	2012	SIGMOD	8.3178501e-05
4,831	Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative	2017	SIGMOD	6.3897334e-05
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
5,786	k-Regret Queries with Nonlinear Utilities	2015	VLDB	5.9954861e-05
6,065	k-Hit Query: Top-k Query with Probabilistic Utility Function	2015	SIGMOD	5.8978409e-05
6,176	Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings	2018	VLDB	5.8609559e-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
7,032	Minimizing Average Regret Ratio in Database	2016	SIGMOD	5.6170961e-05
7,452	Strongly Truthful Interactive Regret Minimization	2019	SIGMOD	5.5235226e-05
7,658	FindYourFavorite: An Interactive System for Finding the User's Favorite Tuple in the Database	2019	SIGMOD	5.4772833e-05
8,846	Data Driven Approximation with Bounded Resources	2017	VLDB	5.2649328e-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
10,087	Interactive Search for One of the Top-k	2021	SIGMOD	5.0830849e-05
10,696	On Fair Epsilon Net and Geometric Hitting Set	2026	VLDB	4.9793485e-05
11,541	Directional Queries: Making Top-k Queries More Effective in Discovering Relevant Results	2024	SIGMOD	4.9793485e-05
11,582	Robust Best Point Selection under Unreliable User Feedback	2024	VLDB	4.9793485e-05
11,712	rkHit: Representative Query with Uncertain Preference	2023	SIGMOD	4.9793485e-05
11,884	Interactive Mining with Ordered and Unordered Attributes	2022	VLDB	4.9793485e-05

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
342	The Onion Technique: Indexing for Linear Optimization Queries	2000	SIGMOD	0.00020530255
418	PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries	2001	SIGMOD	0.00018617842
817	Finding k-Dominant Skylines in High Dimensional Space	2006	SIGMOD	0.00013672764
1,990	Discovering Relative Importance of Skyline Attributes	2009	VLDB	9.2454758e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,996	Multi-objective Query Processing for Database Systems	2004	VLDB
2	2,105	Computing k-Regret Minimizing Sets	2014	VLDB
3	6,716	RRR: Rank-Regret Representative	2019	SIGMOD
4	7,452	Strongly Truthful Interactive Regret Minimization	2019	SIGMOD
5	6,918	A Unified Optimization Algorithm For Solving “Regret-Minimizing Representative” Problems	2020	VLDB
6	4,831	Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative	2017	SIGMOD
7	2,545	Interactive Regret Minimization	2012	SIGMOD
8	5,786	k-Regret Queries with Nonlinear Utilities	2015	VLDB
9	5,068	Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality	2018	SIGMOD
10	7,032	Minimizing Average Regret Ratio in Database	2016	SIGMOD