Back to papers
rkHit: Representative Query with Uncertain Preference
Summary: Proposes rkHit, selecting r representative tuples under a distribution over scoring functions to maximize the probability a chosen tuple is attractive in top-k (expected user satisfaction). In 2D, 2DH gives an exact polynomial algorithm; rkHit is NP-hard for d≥3; 3D offers a (1−1/e)-approximation 3DH under uniform preferences while MDH handles any dimension/distribution via sampling+clustering; experiments show efficiency.
(summarized by gpt-5-nano on Feb 09 2026)
- Paper ID
- 6630
- Venue
- SIGMOD
- Year
- 2023
- Pagerank
- 4.1905499e-05
- Overall Rank
- 11,197 | 22.19%
- DOI
-
10.1145/3589271
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
Outgoing Citations (Sorted by Pagerank)
Showing 23 of 23 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank |
Cited Paper |
Year |
Venue |
Pagerank |
| 1,070 |
Regret-Minimizing Representative Databases |
2010 |
VLDB |
0.00014274615 |
| 1,577 |
Designing Fair Ranking Schemes |
2019 |
SIGMOD |
0.00011276814 |
| 2,477 |
Computing k-Regret Minimizing Sets |
2014 |
VLDB |
8.6907684e-05 |
| 2,936 |
Answering Top-k Queries Using Views |
2006 |
VLDB |
7.8579393e-05 |
| 3,015 |
Ranking with Uncertain Scoring Functions: Semantics and Sensitivity Measures |
2011 |
SIGMOD |
7.7079141e-05 |
| 3,447 |
Towards Robust Indexing for Ranked Queries |
2006 |
VLDB |
7.082382e-05 |
| 3,665 |
Ad-hoc Top-k Query Answering for Data Streams |
2007 |
VLDB |
6.8631567e-05 |
| 4,178 |
Best Position Algorithms for Top-k Queries |
2007 |
VLDB |
6.3757762e-05 |
| 4,556 |
Learning User Preferences By Adaptive Pairwise Comparison |
2015 |
VLDB |
6.0815983e-05 |
| 5,113 |
Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative |
2017 |
SIGMOD |
5.6827696e-05 |
| 5,558 |
On Obtaining Stable Rankings |
2019 |
VLDB |
5.4375292e-05 |
| 6,090 |
Reconciling Skyline and Ranking Queries |
2017 |
VLDB |
5.214198e-05 |
| 6,378 |
Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings |
2018 |
VLDB |
5.0844506e-05 |
| 6,381 |
k-Hit Query: Top-k Query with Probabilistic Utility Function |
2015 |
SIGMOD |
5.0839387e-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 |
| 7,541 |
Strongly Truthful Interactive Regret Minimization |
2019 |
SIGMOD |
4.7104726e-05 |
| 8,014 |
The Computation of Optimal Subset Repairs |
2020 |
VLDB |
4.6020746e-05 |
| 8,812 |
Creating Top Ranking Options in the Continuous Option and Preference Space |
2019 |
VLDB |
4.4397776e-05 |
| 9,753 |
Minimum Coresets for Maxima Representation of Multidimensional Data |
2021 |
PODS |
4.2856385e-05 |
| 9,754 |
On m-Impact Regions and Standing Top-k Influence Problems |
2021 |
SIGMOD |
4.2856385e-05 |
| 9,755 |
Interactive Search for One of the Top-k |
2021 |
SIGMOD |
4.2856385e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 6,816 |
A Unified Optimization Algorithm For Solving "Regret-Minimizing Representative" Problems |
2020 |
VLDB |
4.9115662e-05 |
| 3,190 |
Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers |
2009 |
SIGMOD |
7.413338e-05 |
| 2,477 |
Computing k-Regret Minimizing Sets |
2014 |
VLDB |
8.6907684e-05 |
| 8,848 |
Finding Diverse, High-Value Representatives on a Surface of Answers |
2017 |
VLDB |
4.4326582e-05 |
| 8,823 |
Determining the Impact Regions of Competing Options in Preference Space |
2017 |
SIGMOD |
4.4372904e-05 |
| 13,294 |
Supporting Hard Queries over Probabilistic Preferences |
2020 |
VLDB |
- |
| 9,755 |
Interactive Search for One of the Top-k |
2021 |
SIGMOD |
4.2856385e-05 |
| 10,376 |
A Rank-Based Approach to Recommender System’s Top-K Queries with Uncertain Scores |
2025 |
SIGMOD |
4.1905499e-05 |
| 6,381 |
k-Hit Query: Top-k Query with Probabilistic Utility Function |
2015 |
SIGMOD |
5.0839387e-05 |
| 6,378 |
Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings |
2018 |
VLDB |
5.0844506e-05 |