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.2893698e-05
Overall Rank
5,068 | 65.93%
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,756 Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size 2021 SIGMOD 5.6900378e-05
6,918 A Unified Optimization Algorithm For Solving “Regret-Minimizing Representative” Problems 2020 VLDB 5.6445155e-05
7,452 Strongly Truthful Interactive Regret Minimization 2019 SIGMOD 5.5235226e-05
8,993 Creating Top Ranking Options in the Continuous Option and Preference Space 2019 VLDB 5.2419215e-05
9,576 Happiness Maximizing Sets under Group Fairness Constraints 2023 VLDB 5.1571823e-05
10,085 Minimum Coresets for Maxima Representation of Multidimensional Data 2021 PODS 5.0830849e-05
10,086 On m-Impact Regions and Standing Top-k Influence Problems 2021 SIGMOD 5.0830849e-05
10,087 Interactive Search for One of the Top-k 2021 SIGMOD 5.0830849e-05
11,884 Interactive Mining with Ordered and Unordered Attributes 2022 VLDB 4.9793485e-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
342 The Onion Technique: Indexing for Linear Optimization Queries 2000 SIGMOD 0.00020530255
817 Finding k-Dominant Skylines in High Dimensional Space 2006 SIGMOD 0.00013672764
1,087 Regret-Minimizing Representative Databases 2010 VLDB 0.00012097722
1,476 Diversifying Top-K Results 2012 VLDB 0.00010551487
1,990 Discovering Relative Importance of Skyline Attributes 2009 VLDB 9.2454758e-05
2,105 Computing k-Regret Minimizing Sets 2014 VLDB 9.0330207e-05
2,174 Top-k Bounded Diversification 2012 SIGMOD 8.917444e-05
2,545 Interactive Regret Minimization 2012 SIGMOD 8.3178501e-05
4,831 Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative 2017 SIGMOD 6.3897334e-05
5,786 k-Regret Queries with Nonlinear Utilities 2015 VLDB 5.9954861e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,893 Efficient Processing of Top-k Dominating Queries on Multi-Dimensional Data 2007 VLDB
2 7,452 Strongly Truthful Interactive Regret Minimization 2019 SIGMOD
3 6,065 k-Hit Query: Top-k Query with Probabilistic Utility Function 2015 SIGMOD
4 2,105 Computing k-Regret Minimizing Sets 2014 VLDB
5 6,918 A Unified Optimization Algorithm For Solving “Regret-Minimizing Representative” Problems 2020 VLDB
6 4,831 Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative 2017 SIGMOD
7 2,545 Interactive Regret Minimization 2012 SIGMOD
8 5,786 k-Regret Queries with Nonlinear Utilities 2015 VLDB
9 7,032 Minimizing Average Regret Ratio in Database 2016 SIGMOD
10 1,087 Regret-Minimizing Representative Databases 2010 VLDB