Paper Info
Title
Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality.
Abstract
Extracting interesting tuples from a large database is an important problem in multi-criteria decision making. Two representative queries were proposed in the literature: top- k queries and skyline queries. A top- k query requires users to specify their utility functions beforehand and then returns k tuples to the users. A skyline query does not require any utility function from users but it puts no control on the number of tuples returned to users. Recently, a k-regret query was proposed and received attention from the community because it does not require any utility function from users and the output size is controllable, and thus it avoids those deficiencies of top- k queries and skyline queries. Specifically, it returns k tuples that minimize a criterion called the maximum regret ratio . In this paper, we present the lower bound of the maximum regret ratio for the k -regret query. Besides, we propose a novel algorithm, called SPHERE, whose upper bound on the maximum regret ratio is asymptotically optimal and restriction-free for any dimensionality, the best-known result in the literature. We conducted extensive experiments to show that SPHERE performs better than the state-of-the-art methods for the k -regret query.
Year
DOI
Venue
2018
10.1145/3183713.3196903
SIGMOD/PODS '18: International Conference on Management of Data Houston TX USA June, 2018
Keywords
Field
DocType
k-regret,multi-criteria decision making,data analytics
Skyline,Data analysis,Regret,Tuple,Upper and lower bounds,Computer science,Algorithm,Curse of dimensionality,Asymptotically optimal algorithm
Conference
ISSN
ISBN
Citations 
0730-8078
978-1-4503-4703-7
6
PageRank 
References 
Authors
0.49
24
5
Name
Order
Citations
PageRank
Min Xie1207.20
Raymond Chi-Wing Wong2130585.98
Jian Li3214.50
Cheng Long4286.01
Ashwin Lall521515.31