Research On Skyline Query Processing Techniques

With the continuous development of database technology,the volume of data stored and processed by databases increases rapidly.Mining the information of interest to users from massive data is an important topic in database research field.According to preferences of users,skyline queries can return the set that users are most interested in,which has been widely recognized by domestic and foreign scholars.At present,skyline query has become a key topic in database,and wealth of research results have been obtained.As an important operator of multi-objective decision making,skyline has been widely applied in people's daily life.In order to make skyline query applied in different scenarios flexibly,people extend the skyline query and many skyline variants have been proposed.This paper analyzed the requirements of users and deeply studied the various skyline variant query problems.According to different application situations,some efficient and targeted solutions are proposed to satisfy people's practical needs.The main contributions are summarized as follow.(1)Some algorithms are proposed to process the subspace global skyline query problem.1)A index structure RB-tree,which can rapidly locate the initial scan positions of query points in ad hoc subspace,is proposed.2)Based on RB-tree index,two single subspace global skyline algorithms SSRB and OSSRB are proposed.SSRB applies round-robin method to scan data in different dimensions until all the subspace global skyline points are scanned.OSSRB improves the scan strategy and reduces the scan space.Hence,OSSRB can calculate the subspace global skyline more efficiently.3)A multiple subspace global skyline algorithm MSRB is proposed.By sharing the scan space of different queries,MSRB can answer different subspace global skyline queries through once scan.Finally,we verify the effectiveness of the proposed algorithms through a series of experiments.(2)For skyline-join query problem in distributed environments,we propose algorithm DSJQ.1)A tailored distributed framework is proposed to facilitate the calculation of skyline-join queries.2)The distributed skyline-join query algorithm DSJQ is proposed to process skyline-join queries.DSJQ contains two phases.In the first phase,two filtering strategies are proposed to filter out unpromising tuples before the join operation.In the second phase,a rotation scheduling plan is designed to schedule the calculations between different nodes.The rotation scheduling plan can ensure all calculations are equally assigned to all data nodes without creating a bottleneck node.Finally,the effectiveness and efficiency of DSJQ are evaluated through a series of experiments.(3)For dynamic skyline problem over data streams,we propose two algorithms BDS2 and IDS2.1)We propose a hybrid index to manage the data in data streams.This hybrid index can be updated quickly and suitable for any data distribution.2)Based on this hybrid index,we propose the basic dynamic skyline query algorithm BDS2 over data streams.Using the filtering strategies,BDS2 can quickly compute the dynamic skyline by maintaining a small amount of data.3)Based on BDS2,we propose the improved dynamic skyline query algorithm IDS2 over data strezams.By maintain a silple data structure,IDS2 can calculate the dynamic skyline stably.Finally,we evaluate the performance of the proposed algorithms through the simulation experiments.(4)We propose some solutions to process the k representative skyline over data streams.1)We propose a new criterion to choose k skyline points as the k representative skyline over data stream environments,termed k-LDS.k-LDS wants to find a subset of k skyline points with the largest dominance area.2)For the k-LDS problem in 2-dimensioal space,we propose an exact algorithm PBA.Using the dynamic programming method,PBA can efficiently calculate the k-LDS.3)For the k-LDS problem in d-dimensional space(d>3),we propose an approximate algorithm--GA to answer k-LDS queries.Using the greedy strategy,?-GA can achieve an approxirmate factor of 1/1+?(1-1/(?)).Finally,experimental results show that our k-LDS significantly outperforms its competitors in data stream environments.Furtheemore,PBA and ?-GA can efficiently answer k-LDS queries over data stream environments.