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
- 6629
- Venue
- SIGMOD
- Year
- 2023
- Pagerank
- 4.1945683e-05
- Overall Rank
- 11,195 | 22.12%
- 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,072 |
Regret-Minimizing Representative Databases |
2010 |
VLDB |
0.00014270817 |
| 1,597 |
Designing Fair Ranking Schemes |
2019 |
SIGMOD |
0.00011209846 |
| 2,478 |
Computing k-Regret Minimizing Sets |
2014 |
VLDB |
8.6927744e-05 |
| 2,933 |
Answering Top-k Queries Using Views |
2006 |
VLDB |
7.8679669e-05 |
| 3,014 |
Ranking with Uncertain Scoring Functions: Semantics and Sensitivity Measures |
2011 |
SIGMOD |
7.70946e-05 |
| 3,463 |
Towards Robust Indexing for Ranked Queries |
2006 |
VLDB |
7.069675e-05 |
| 3,665 |
Ad-hoc Top-k Query Answering for Data Streams |
2007 |
VLDB |
6.8633354e-05 |
| 4,186 |
Best Position Algorithms for Top-k Queries |
2007 |
VLDB |
6.3764858e-05 |
| 4,564 |
Learning User Preferences By Adaptive Pairwise Comparison |
2015 |
VLDB |
6.0819005e-05 |
| 5,116 |
Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative |
2017 |
SIGMOD |
5.6830089e-05 |
| 5,555 |
On Obtaining Stable Rankings |
2019 |
VLDB |
5.4386174e-05 |
| 6,091 |
Reconciling Skyline and Ranking Queries |
2017 |
VLDB |
5.214376e-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 |
| 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 |
| 7,605 |
The Computation of Optimal Subset Repairs |
2020 |
VLDB |
4.697534e-05 |
| 8,877 |
Creating Top Ranking Options in the Continuous Option and Preference Space |
2019 |
VLDB |
4.4302563e-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 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 6,834 |
A Unified Optimization Algorithm For Solving "Regret-Minimizing Representative" Problems |
2020 |
VLDB |
4.9117328e-05 |
| 3,185 |
Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers |
2009 |
SIGMOD |
7.4192604e-05 |
| 2,478 |
Computing k-Regret Minimizing Sets |
2014 |
VLDB |
8.6927744e-05 |
| 8,848 |
Finding Diverse, High-Value Representatives on a Surface of Answers |
2017 |
VLDB |
4.4369118e-05 |
| 8,825 |
Determining the Impact Regions of Competing Options in Preference Space |
2017 |
SIGMOD |
4.4415078e-05 |
| 13,281 |
Supporting Hard Queries over Probabilistic Preferences |
2020 |
VLDB |
- |
| 9,775 |
Interactive Search for One of the Top-k |
2021 |
SIGMOD |
4.2856106e-05 |
| 10,364 |
A Rank-Based Approach to Recommender System’s Top-K Queries with Uncertain Scores |
2025 |
SIGMOD |
4.1945683e-05 |
| 6,391 |
k-Hit Query: Top-k Query with Probabilistic Utility Function |
2015 |
SIGMOD |
5.0842079e-05 |
| 6,387 |
Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings |
2018 |
VLDB |
5.0851965e-05 |