Font Size: a A A

Research On Reverse Skyline Query Over Distributed Data

Posted on:2014-01-02Degree:MasterType:Thesis
Country:ChinaCandidate:P P YangFull Text:PDF
GTID:2248330398465370Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
Reverse skyline query, as a typical method about multi-criteria optimization, is beingwidely used in data mining and multi-criteria decision. However, till now, most of the workis based on the centralized data and there is no work over distributed data. In practice, mostof the data is stored over diferent sites connected by network in consideration of the costand performance. The existing centralized algorithm can’t simply satisfy distributed envi-ronment. In this thesis, we talk about reverse skyline query algorithm over distributed data,and our work includes the following parts:(1)By studying reverse skyline query over centralized data,we put forward BBDRS al-gorithm that is suitable for distributed static datasets.On the remote sites,it takes use of Rtree index to pre-compute the candidate and filter dataset as the data summary which appar-ently reduces not only the query delay but also communication cost by avoiding sending allthe data.(2)As R tree method costs so much time to create index,then we propose an optimizedPDRS algorithm based on the pre-sorting.PDRS takes the same communication strategy asabove and pre-sorts all the points according to their distance to the query point.As PDRShas no need to create index,and also can reduce a great many times of domination checksthrough pre-sorting,a lot of computation time can be saved.Over a not so big dataset,PDRSalgorithm performs better than BBDRS.(3)By using current reverse skyline query method over single data stream for ref-erence,we design an DCDRS algorithm to compute reverse skyline over distributed datastreams.On the remote sites,it takes use of DC tree to timely compute and maintain the datasummary of the current window objets.While on the centralized site,centralized algorithmis applied to compute the last results.DCDRS algorithm can not only accurately but alsoefciently compute the reverse skyline over distributed data streams.(4)An experiment platform is designed for reverse skyline query over distributed data.As for kind of control function of control end,it makes all the experiments be automatedcompleted and avoids a lot of manual operation.To some extent,it guarantees the realnessand accuracy of the experimental data.Our research has great significance on the application of reverse skyline query in user- preference system and multi-criteria decision making system as well as data mining. Nowa-days,as data storing is tending to be distributed and is receiving more and more attention, ourstudy can promote the application and the development of the reverse skyline query underthe distributed environment.
Keywords/Search Tags:Reverse skyline, Distributed query, Skyline, Database query, Data stream
PDF Full Text Request
Related items