Font Size: a A A

Research On Methods Of Multi-k-Dominant Skyline Query

Posted on:2011-01-28Degree:MasterType:Thesis
Country:ChinaCandidate:J J TangFull Text:PDF
GTID:2178360302494764Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
The technology of skyline query is a hot research point in the domain of spatial query and optimization, and the k-dominant skyline query has become a new research direction in the field of skyline query. The k-dominant skyline query and its dynamic processing have been widely used in all kinds of spatial databases, and it will be a large potential application in many aspects, such as the Data mining, Visible Database, Multi-objective decision and so on. In this paper the technologies of skyline query and its updating are studied, and then based on these the concept of multi-k-dominant skyline is proposed, and then the intensive study is made, the material contents are as follows.Firstly, the problem that the existing k-dominant skyline methods can only return single result is researched. And focused on it, the concept of k-dominate attribute is presented. The methods of the k-dominate attribute set query for the k-dominant skyline are proposed. Furthermore, the NP completeness of the k-dominate attributes set query is demonstrated. In addition, the correctness of the algorithm is proved and analyzed through examples.Secondly, the advantage and disadvantage of the present k-dominant skyline algorithms are analysed. And then based on these the concept of multi-k-dominant skyline is given; the qualitative theorem of multi-k-dominant skyline is proposed and proved. Furthermore, the enumerate algorithm for multi-k-dominant skyline and the index algorithm for multi-k-dominant skyline are put forward in order to find the multi-k-dominant skyline based on the theorem. At last the correctness of the algorithms is demonstrated and analyzed by instances.Thirdly, if the values of the attributes in a data set are updated, the multi-k-dominant skyline has to be computed again. And aimed at this the updating methods for finding multi-k-dominant skyline are presented. Besides, the point-attributes algorithm and the set-attributes algorithm are proposed to solve the different situations that the attributes value of only one point and several points are changed. Then the theoretical analysis of each algorithm is given.Fourthly, when a point is added to or deleted from the dataset, the multi-k-dominant skyline will be disabled. For solving it the new finding multi-k-dominant skyline methods are presented. And the AddPoint m-k-Skyline algorithm and the Delete Point m-k-Skyline algorithm are proposed aimed at the different situations. Then the theoretical analyses of the algorithms are given.Finally, several algorithms of this paper were verified by experiments. The figures of result are given, and the results are analysed and compared.
Keywords/Search Tags:Spatial database, Skyline, k-dominantskyline, Multi-k-dominant skyline, Update
PDF Full Text Request
Related items