Computing k-Regret Minimizing Sets

Summary: Proposes k-regret minimizing sets as a relaxed data-summary: small R approximates D's top-k results via top-1 queries. In 2D, optimal R via DP plane-sweep; in higher dimensions, a greedy LP-based algorithm yields compact summaries despite NP-hardness. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h582060a9faa083e4
Venue: VLDB
Year: 2014
Pagerank: 8.9989036e-05
Overall Rank: 2,119 | 85.80%
DOI: 10.14778/2735479.2735483
PDF: Download (CC BY-NC-ND 3.0)

Incoming Non-self Citations Over Time

Authors

1. Sean Chester (University of Victoria)
2. Alex Thomo (University of Victoria)
3. S. Venkatesh (University of Victoria)
4. Sue Whitesides (University of Victoria)

BibTeX Citation

@article{chester_vldb14,
        title = {{Computing k-Regret Minimizing Sets}},
        author = {Chester, Sean and Thomo, Alex and Venkatesh, S. and Whitesides, Sue},
        journal = {PVLDB},
        series = {{VLDB} '14},
        volume = {7},
        number = {5},
        pages = {389--400},
        doi = {10.14778/2735479.2735483},
        url = {https://doi.org/10.14778/2735479.2735483},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,856	Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative	2017	SIGMOD	6.3655902e-05
5,092	Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality	2018	SIGMOD	6.2656058e-05
5,624	On Obtaining Stable Rankings	2019	VLDB	6.0456849e-05
5,802	k-Regret Queries with Nonlinear Utilities	2015	VLDB	5.9728325e-05
6,191	Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings	2018	VLDB	5.8388106e-05
6,736	RRR: Rank-Regret Representative	2019	SIGMOD	5.6777742e-05
6,780	Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size	2021	SIGMOD	5.6685383e-05
6,939	A Unified Optimization Algorithm For Solving “Regret-Minimizing Representative” Problems	2020	VLDB	5.623188e-05
8,826	Geometric Approaches for Top-k Queries	2017	VLDB	5.2539334e-05
9,020	Creating Top Ranking Options in the Continuous Option and Preference Space	2019	VLDB	5.2221152e-05
9,609	Happiness Maximizing Sets under Group Fairness Constraints	2023	VLDB	5.1376962e-05
10,126	Interactive Search for One of the Top-k	2021	SIGMOD	5.0638787e-05
11,295	Mining the Minoria: Unknown, Under-represented, and Under-performing Minority Groups	2025	VLDB	4.9605343e-05
11,596	Directional Queries: Making Top-k Queries More Effective in Discovering Relevant Results	2024	SIGMOD	4.9605343e-05
11,636	Robust Best Point Selection under Unreliable User Feedback	2024	VLDB	4.9605343e-05
11,764	rkHit: Representative Query with Uncertain Preference	2023	SIGMOD	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
344	The Onion Technique: Indexing for Linear Optimization Queries	2000	SIGMOD	0.00020463118
820	Finding k-Dominant Skylines in High Dimensional Space	2006	SIGMOD	0.00013621724
1,092	Regret-Minimizing Representative Databases	2010	VLDB	0.00012052099
2,551	Interactive Regret Minimization	2012	SIGMOD	8.2864226e-05
3,391	Ad-hoc Top-k Query Answering for Data Streams	2007	VLDB	7.3290724e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,043	Answering Top-k Representative Queries on Graph Databases	2014	SIGMOD
2	11,764	rkHit: Representative Query with Uncertain Preference	2023	SIGMOD
3	5,802	k-Regret Queries with Nonlinear Utilities	2015	VLDB
4	6,736	RRR: Rank-Regret Representative	2019	SIGMOD
5	7,053	Minimizing Average Regret Ratio in Database	2016	SIGMOD
6	10,124	Minimum Coresets for Maxima Representation of Multidimensional Data	2021	PODS
7	1,092	Regret-Minimizing Representative Databases	2010	VLDB
8	5,092	Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality	2018	SIGMOD
9	6,939	A Unified Optimization Algorithm For Solving “Regret-Minimizing Representative” Problems	2020	VLDB
10	4,856	Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative	2017	SIGMOD