Research And Implementation Of G-Skyline Query Algorithm On Massive Data

Skyline query is a typical multi-objective optimization problem,which aims to return the points that are not dominated by any other points in the specified data set.But it focuses on analyzing individual points.In real life,there are many situations that we need to consider their combination of queries.The research of G-Skyline query algorithm aims to solve such problems and help us find groups that are not dominated by any other groups.However,due to the huge output scale of G-Skyline,users can't make fast and effective decisions.Therefore,in order to control the number of returned results of G-Skyline query and help users make choices,k groups with the highest dominance score are returned based on strict dominance.The research content of this paper is G-Skyline query algorithm and top-k G-Skyline query algorithm.In the research of G-Skyline query algorithm,this paper proposes the baseline algorithm of G-Skyline query.The algorithm creates Directed Skyline Graph(Referred to as DSG diagram)and takes the points of the first s layers for preprocessing,and then recursively enumerates the remaining points to the groups of size s.Finally,judge whether the generated group is G-Skyline group in turn;In order to improve the speed of baseline algorithm,this paper proposes the Append Unit of G-Skyline algorithm(Referred to as AUGS algorithm).Firstly,the algorithm creates a DSG graph and prunes some points.After that,some non skyline points are deleted in advance by preprocessing.The algorithm first determines the skyline points in GSkyline,4)-6)7)4)9)0)(1 ? 4)? -1),and then adds -4)non skyline points that meet the conditions.When adding non skyline points,the algorithm prunes the unqualified points in advance through condition judgment and subset pruning.After that,non skyline points are added in the form of adding unit groups,and qualified unit groups are filled for 4)-6)7)4)9)0)to form G-Skyline group with group size s.Finally,the effectiveness of the algorithm is verified by comparing the AUGS algorithm with Point-Wise algorithm and Unit Group-Wise+ algorithm.In the research of top-k G-Skyline query algorithm,this paper first proposes the baseline algorithm for G-Skyline query.Algorithm first finds out all G-Skyline groups,then calculates their dominant scores,and finally returns the k groups with the highest dominant scores;In order to improve the speed of baseline algorithm,this paper proposes Early Termination algorithm(Referred to as ET algorithm)and Quick Termination algorithm(Referred to as QT algorithm)to effectively calculate the topk G-Skyline results.The algorithm first enumerates the G-Skyline which is only composed of skyline points,and then finds out the k G-Skyline groups with the highest dominant score.Experiments show that enumeration is time-consuming when the amount of data increases and the dimension increases,and the time spent by the algorithm is mainly determined by this part.Therefore,this paper focuses on the enumeration process.First,ET algorithm is proposed.ET algorithm uses the upper bound pruning and early termination strategy.It does not need to list all the GSkylines composed of skyline points to return the results.However,there are still unnecessary enumerations in ET algorithm.Therefore,based on ET algorithm,this paper proposes QT algorithm.Compared with ET algorithm,QT algorithm adds early pruning strategy.Through the early pruning strategy,the single enumeration process can be terminated in advance to speed up the overall speed of the algorithm.Experiments show that ET algorithm and QT algorithm have satisfactory performance in terms of running cost.In this paper,we propose the concept of all Top-K G-Skyline query,that is,we can find the × 6)groups with the highest strict dominance score and the group size from 1 to s at one time.Fast algorithm is proposed to deal with all Top-K G-Skyline queries effectively.