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.2863925e-05
Overall Rank
5,071 | 65.92%
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,761 Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size 2021 SIGMOD 5.6873442e-05
6,920 A Unified Optimization Algorithm For Solving “Regret-Minimizing Representative” Problems 2020 VLDB 5.6418435e-05
7,456 Strongly Truthful Interactive Regret Minimization 2019 SIGMOD 5.5209079e-05
9,002 Creating Top Ranking Options in the Continuous Option and Preference Space 2019 VLDB 5.23944e-05
9,584 Happiness Maximizing Sets under Group Fairness Constraints 2023 VLDB 5.154741e-05
10,090 Minimum Coresets for Maxima Representation of Multidimensional Data 2021 PODS 5.0806786e-05
10,091 On m-Impact Regions and Standing Top-k Influence Problems 2021 SIGMOD 5.0806786e-05
10,092 Interactive Search for One of the Top-k 2021 SIGMOD 5.0806786e-05
11,890 Interactive Mining with Ordered and Unordered Attributes 2022 VLDB 4.9769913e-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.00020520649
818 Finding k-Dominant Skylines in High Dimensional Space 2006 SIGMOD 0.00013666302
1,087 Regret-Minimizing Representative Databases 2010 VLDB 0.00012092041
1,476 Diversifying Top-K Results 2012 VLDB 0.00010546498
1,992 Discovering Relative Importance of Skyline Attributes 2009 VLDB 9.2411032e-05
2,106 Computing k-Regret Minimizing Sets 2014 VLDB 9.0287481e-05
2,177 Top-k Bounded Diversification 2012 SIGMOD 8.9132232e-05
2,545 Interactive Regret Minimization 2012 SIGMOD 8.3139128e-05
4,833 Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative 2017 SIGMOD 6.3867086e-05
5,788 k-Regret Queries with Nonlinear Utilities 2015 VLDB 5.9926479e-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,456 Strongly Truthful Interactive Regret Minimization 2019 SIGMOD
3 6,066 k-Hit Query: Top-k Query with Probabilistic Utility Function 2015 SIGMOD
4 2,106 Computing k-Regret Minimizing Sets 2014 VLDB
5 6,920 A Unified Optimization Algorithm For Solving “Regret-Minimizing Representative” Problems 2020 VLDB
6 4,833 Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative 2017 SIGMOD
7 2,545 Interactive Regret Minimization 2012 SIGMOD
8 5,788 k-Regret Queries with Nonlinear Utilities 2015 VLDB
9 7,034 Minimizing Average Regret Ratio in Database 2016 SIGMOD
10 1,087 Regret-Minimizing Representative Databases 2010 VLDB