Font Size: a A A

Research On Skyline Query Algorithm Based On New Data Index Structure

Posted on:2022-11-10Degree:MasterType:Thesis
Country:ChinaCandidate:H T WuFull Text:PDF
GTID:2518306611985579Subject:Electronic information
Abstract/Summary:PDF Full Text Request
In the era of big data,how to efficiently deal with massive spatial data information is very important.Spatial database has gradually developed,and it has very important applications in decision support,geographic information,GIS and device positioning.Skyline query and reverse Skyline query are both very important query methods and are also the focus of continuous research by many scholars.This paper mainly consists of three parts: the study of the new data index structure,the study of Skyline query algorithm based on the new data index structure and the study of the reverse Skyline query algorithm.First,two order relations of spatial data are given,and a new type of spatial data index structure is proposed by using these two order relations to divide spatial data alternately: DSP-Tree(Data Space Partition-Tree,DSP-Tree).The data index structure uses a variety of good order relationships of spatial data to divide the spatial data,thereby obtaining the smallest outer enclosing rectangle containing the corresponding order relationship.According to different order relationships,the data index structure is divided into different levels when constructing the data index structure.To reduce the overlapping and invalid access paths between nodes at the same level,the DSP-tree generation algorithm,data update algorithm and area query algorithm are given.Secondly,on the basis of the new data index structure DSP-tree,the nature of Skyline query and the characteristics of DSP-tree are effectively combined,and efficient pruning rules for Skyline query based on DSP-tree are given.On this basis,a Skyline query algorithm based on DSP-tree is given.This algorithm uses a variety of order relationships among the nodes of the DSP-tree,which effectively reduces the access of invalid paths and nodes,and improves the performance of Skyline query.Theoretical analysis and experiments show that the Skyline query algorithm based on DSP-tree has better query performance.Finally,on the basis of DSP-tree,a new reverse Skyline query algorithm is proposed.The algorithm uses the order relationship of the DSP-tree sibling nodes at the same level to improve query performance,and prunes nodes at different levels through new pruning rules,reducing invalid node access and speeding up the query speed of the algorithm.Experimental analysis and demonstration show that the reverse Skyline query algorithm based on DSP-tree has better query performance.
Keywords/Search Tags:order relation, index structure, DSP-tree, dominance, skyline query
PDF Full Text Request
Related items