DBScholar

Back to papers

Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality

Summary: Lower bound on the maximum regret ratio for k-regret queries; Sphere, a restriction-free algorithm that works in arbitrary dimensionality. Asymptotically optimal upper bound on regret, outperforming state-of-the-art methods in extensive experiments. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h77a393fca8859d08
Venue
SIGMOD
Year
2018
Pagerank
6.2656058e-05
Overall Rank
5,092 | 65.87%
DOI
10.1145/3183713.3196903

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{xie_sigmod18,
        title = {{Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality}},
        author = {Xie, Min and Wong, Raymond Chi-Wing and Li, Jian and Long, Cheng and Lall, Ashwin},
        series = {{SIGMOD} '18},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3183713.3196903},
        url = {https://dl.acm.org/doi/10.1145/3183713.3196903},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank Citing Paper Year Venue Pagerank
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
7,474 Strongly Truthful Interactive Regret Minimization 2019 SIGMOD 5.5026548e-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,124 Minimum Coresets for Maxima Representation of Multidimensional Data 2021 PODS 5.0638787e-05
10,125 On m-Impact Regions and Standing Top-k Influence Problems 2021 SIGMOD 5.0638787e-05
10,126 Interactive Search for One of the Top-k 2021 SIGMOD 5.0638787e-05
11,934 Interactive Mining with Ordered and Unordered Attributes 2022 VLDB 4.9605343e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 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
1,478 Diversifying Top-K Results 2012 VLDB 0.00010511781
2,000 Discovering Relative Importance of Skyline Attributes 2009 VLDB 9.2105506e-05
2,119 Computing k-Regret Minimizing Sets 2014 VLDB 8.9989036e-05
2,192 Top-k Bounded Diversification 2012 SIGMOD 8.8838688e-05
2,551 Interactive Regret Minimization 2012 SIGMOD 8.2864226e-05
4,856 Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative 2017 SIGMOD 6.3655902e-05
5,802 k-Regret Queries with Nonlinear Utilities 2015 VLDB 5.9728325e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,904 Efficient Processing of Top-k Dominating Queries on Multi-Dimensional Data 2007 VLDB
2 7,474 Strongly Truthful Interactive Regret Minimization 2019 SIGMOD
3 6,081 k-Hit Query: Top-k Query with Probabilistic Utility Function 2015 SIGMOD
4 2,119 Computing k-Regret Minimizing Sets 2014 VLDB
5 6,939 A Unified Optimization Algorithm For Solving “Regret-Minimizing Representative” Problems 2020 VLDB
6 4,856 Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative 2017 SIGMOD
7 2,551 Interactive Regret Minimization 2012 SIGMOD
8 5,802 k-Regret Queries with Nonlinear Utilities 2015 VLDB
9 7,053 Minimizing Average Regret Ratio in Database 2016 SIGMOD
10 1,092 Regret-Minimizing Representative Databases 2010 VLDB