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
5611
Venue
SIGMOD
Year
2018
Pagerank
6.4336325e-05
Overall Rank
4,939 | 66.12%
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,636 Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size 2021 SIGMOD 5.8172769e-05
6,786 A Unified Optimization Algorithm For Solving “Regret-Minimizing Representative” Problems 2020 VLDB 5.7740702e-05
7,305 Strongly Truthful Interactive Regret Minimization 2019 SIGMOD 5.6501646e-05
8,825 Creating Top Ranking Options in the Continuous Option and Preference Space 2019 VLDB 5.3616725e-05
9,393 Happiness Maximizing Sets under Group Fairness Constraints 2023 VLDB 5.2755515e-05
9,899 Minimum Coresets for Maxima Representation of Multidimensional Data 2021 PODS 5.1997534e-05
9,900 On m-Impact Regions and Standing Top-k Influence Problems 2021 SIGMOD 5.1997534e-05
9,901 Interactive Search for One of the Top-k 2021 SIGMOD 5.1997534e-05
11,576 Interactive Mining with Ordered and Unordered Attributes 2022 VLDB 5.093636e-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
333 The Onion Technique: Indexing for Linear Optimization Queries 2000 SIGMOD 0.0002089582
792 Finding k-Dominant Skylines in High Dimensional Space 2006 SIGMOD 0.00013979615
1,072 Regret-Minimizing Representative Databases 2010 VLDB 0.0001230281
1,454 Diversifying Top-K Results 2012 VLDB 0.00010739504
1,938 Discovering Relative Importance of Skyline Attributes 2009 VLDB 9.4514785e-05
2,063 Computing k-Regret Minimizing Sets 2014 VLDB 9.2399169e-05
2,259 Top-k Bounded Diversification 2012 SIGMOD 8.8529269e-05
2,491 Interactive Regret Minimization 2012 SIGMOD 8.5086491e-05
4,727 Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative 2017 SIGMOD 6.5362946e-05
5,654 k-Regret Queries with Nonlinear Utilities 2015 VLDB 6.1330869e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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