K Representative Skyline Query Processing Techniques Based On Users' Happiness Ratio

Finding k data points that users are most interested in from a large database to support users' multi-criteria decision making is an important topic in database area.The k-regret query uses maximum regret ratio as a metric to return k data points that minimize user's maximum regret ratio.However,the existing studies about the k-regret query suffer from the drawbacks of low efficiency and bias towards the least satisfied users.Motivated by these,a k representative skyline query based on users' happiness ratio is provided in this thesis,efficient algorithms based on the properties that the objective functions exhibited are proposed to answer our proposed query.The main work and contributions are listed as follows.(1)We study the metrics of k representative skyline points in this thesis.There are various metrics to existing k representative skyline points.Concrete analysis on advantages and disadvantages of these metrics are given.The measurements of minimum happiness ratio and average happiness ratio are proposed to better measure the quantity of the returned k representative skyline points.(2)The k representative skyline query processing techniques based on user's minimum happiness ratio are studied.Firstly,we propose the concept of minimum happiness ratio and prove that the minimum happiness ratio function is monotone and non-decreasing.Based on these properties,an accelerated strategy we called lazy evaluation is proposed,which is used to reduce the number of function evaluations required of the k-regret query.Besides,random sampling technique is adopted to reduce the size of the candidate set for the k-regret query.Finally,two efficient algorithms based on lazy evaluation and random sampling technique are designed.Experiments show the algorithms proposed in this thesis can effectively improve the efficiency of the k-regret query by reducing the number of function evaluations required of the k-regret query.(3)The k representative skyline query processing techniques based on users' average happiness ratio are discussed.To avoid the problem that the k-regret query will be biased towards the most dissatisfied users,we propose average happiness ratio as a metric to better measure users' satisfaction after a user sees k returned data points,instead of all the data points in the database.Then,the problem of maximizing average happiness ratio is given and we prove that this problem is NP-hard.In addition,we find that the average happiness ratio function is a monotone and non-decreasing submodular function.Based on this property and combined with lazy evaluation and random sampling technique,efficient algorithms with approximation guarantees as well as detailed theoretical analysis are proposed.Experiments show that our proposed algorithms outperform the existing algorithms in terms of the efficiency and the quality of the result set.