Font Size: a A A

The Research On Group-skyline Query Algorithm

Posted on:2018-08-03Degree:MasterType:Thesis
Country:ChinaCandidate:K Y LiuFull Text:PDF
GTID:2348330533963073Subject:Computer Science and Technology
Abstract/Summary:PDF Full Text Request
Skyline query is a typical muti-objective optimization problem,aiming at identifying the information that users may interested in a multi-dimensional dataset.Skyline query is widely applied in many fields,such as multi-criteria decision making system,navigation system,information recommendation system,data mining,etc.Group-Skyline is the further generalization of the original skyline.Group-Skyline needs to consider not only individual point but also groups consisting of points,aiming at finding the set of groups that are not dominated by any other group in dataset.As the dataset,dimension,and the size of the requested group increases,the result returned by the existing algorithm is extremely large.However,in the practical application,users only care about a small number of representative results.In this paper,the problem of top-k Group-Skyline query is researched.The specific research contents are as follows.Firstly,through the analysis of the existing query algorithms,we find that the problem of existing methods have a large result and inefficient.We use the characteristic which the points in the low skyline layers dominate the points in the high skyline layers and propose a ranking strategy based on the skyline layer for the result,which is according to the skyline layer and the number of vertices on them.We propose the corresponding SLGS algorithm,used to return the top-k results.Secondly,for the problem that the SLGS may return the same ranking result,we propose a ranking strategy of Group-Skyline result based on the skyline layer and the vertex coverage and the relative importance of the result of the same ranking is further distinguished by the size of the vertex overlay set.We propose the corresponding VCGS algorithm,which sorts the result and returns the top-k results.In order to improve the efficiency of the algorithm,we propose the VCGS+ algorithm based on VCGS.Through pruning the skyline layers and getting some of the results merely,the method can find the best k Group-Skyline results,thus reducing the cost of the enumeration and improving the efficiency of the algorithm.At last,based on real data set,the result of the experiment shows the effectiveness of the proposed method according to the query response time and the quality of returned results.
Keywords/Search Tags:skyline query, Group-Skyline, skyline layer, vertex coverage
PDF Full Text Request
Related items