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: 10918
Venue: VLDB
Year: 2014
Pagerank: 8.6907684e-05
Overall Rank: 2,477 | 82.79%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,113	Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative	2017	SIGMOD	5.6827696e-05
5,259	Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality	2018	SIGMOD	5.5972902e-05
5,558	On Obtaining Stable Rankings	2019	VLDB	5.4375292e-05
5,906	k-Regret Queries with Nonlinear Utilities	2015	VLDB	5.274596e-05
6,378	Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings	2018	VLDB	5.0844506e-05
6,804	RRR: Rank-Regret Representative	2019	SIGMOD	4.917138e-05
6,816	A Unified Optimization Algorithm For Solving "Regret-Minimizing Representative" Problems	2020	VLDB	4.9115662e-05
6,988	Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size	2021	SIGMOD	4.8665394e-05
8,581	Geometric Approaches for Top-k Queries	2017	VLDB	4.4874332e-05
8,812	Creating Top Ranking Options in the Continuous Option and Preference Space	2019	VLDB	4.4397776e-05
9,253	Happiness Maximizing Sets under Group Fairness Constraints	2023	VLDB	4.3648789e-05
9,755	Interactive Search for One of the Top-k	2021	SIGMOD	4.2856385e-05
10,564	Mining the Minoria: Unknown, Under-represented, and Under-performing Minority Groups	2025	VLDB	4.1905499e-05
10,989	Directional Queries: Making Top-k Queries More Effective in Discovering Relevant Results	2024	SIGMOD	4.1905499e-05
11,043	Robust Best Point Selection under Unreliable User Feedback	2024	VLDB	4.1905499e-05
11,197	rkHit: Representative Query with Uncertain Preference	2023	SIGMOD	4.1905499e-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
428	The Onion Technique: Indexing for Linear Optimization Queries	2000	SIGMOD	0.0002349868
913	Finding k-Dominant Skylines in High Dimensional Space	2006	SIGMOD	0.00015372758
1,070	Regret-Minimizing Representative Databases	2010	VLDB	0.00014274615
2,621	Interactive Regret Minimization	2012	SIGMOD	8.4408945e-05
3,665	Ad-hoc Top-k Query Answering for Data Streams	2007	VLDB	6.8631567e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,085	Answering Top-k Representative Queries on Graph Databases	2014	SIGMOD	5.2165029e-05
11,197	rkHit: Representative Query with Uncertain Preference	2023	SIGMOD	4.1905499e-05
5,906	k-Regret Queries with Nonlinear Utilities	2015	VLDB	5.274596e-05
6,804	RRR: Rank-Regret Representative	2019	SIGMOD	4.917138e-05
6,841	Minimizing Average Regret Ratio in Database	2016	SIGMOD	4.9057455e-05
9,753	Minimum Coresets for Maxima Representation of Multidimensional Data	2021	PODS	4.2856385e-05
1,070	Regret-Minimizing Representative Databases	2010	VLDB	0.00014274615
5,259	Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality	2018	SIGMOD	5.5972902e-05
6,816	A Unified Optimization Algorithm For Solving "Regret-Minimizing Representative" Problems	2020	VLDB	4.9115662e-05
5,113	Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative	2017	SIGMOD	5.6827696e-05