Font Size: a A A

Research On Several Key Problems Of Subspace Skyline Queries

Posted on:2009-11-08Degree:DoctorType:Dissertation
Country:ChinaCandidate:Z H HuangFull Text:PDF
GTID:1118360272459244Subject:Computer software and theory
Abstract/Summary:PDF Full Text Request
Skyline query processing has recently received a lot of attention in database community.This is mainly due to the importance of skyline results in many applications,such as multi-criteria decision making,trip planning,data mining and visualization,defense and intelligence systems,and geographic information Systems. The existing works focus on how to efficiently improve the performance of full-space skyline query by constructing multi-dimensional index structures(e.g.,R-tree). However,in most real applications,the existing algorithms and data structures can not satisfy the needs of efficiency and scalability for subspace skyline queries.This is mainly due to the following three aspects:(ⅰ) the dimensionality of full space is large; (ⅱ) the users are only interested in some useful subspace skyline sets;and(ⅲ) different users usually focus on different subspaces.Motivated by the above facts,in this paper,we focus on tackling with several key problems which mainly include the following three aspects:(1) Efficiently parsing issued subspace skyline queriesThe existing works assume that there are only one subspace skyline query in skyline systems and there do not exists any relational operator in this query.Hence, one of our works is that we regard the subspace skyline query as a special relational operator,called subsapce skyline operator,and focus on consider the equivalence transformation rules and appendent conditions of their implementing orders.Then, based on these equivalence transformation rules and appendent conditions,we change the implementing orders for subspace skyline operator and traditional relational operator and markedly improve the query performance.It is important to note that,we strictly prove the correctness of these equivalence transformation rules.Moreover,we present the cost model of before-transformations and after-transformations.Detailed theoretical analyses and extensive experiments that demonstrate the proposed solution markedly outperforms the existing ones.(2) Efficiently implementing multiple-subspace skyline computationWe propose an efficient cell-dominance computation algorithm(i.e.,CDCA) to tackle with the problem of arbitrary-subspace skyline queries.The CDCA algorithm uses the regular grid index and prunes all the cells which are dominated by any other ones,and hence it can dramatically reduce the number of comparisons between objects.Specially,we present several effective optimization heuristics to further improve the query performance of CDCA.On the other hand,we present APMSSQ, the first efficient sound and complete algorithm for optimizing multiple subspace skyline queries simultaneously in multi-user environments.The APMSSQ algorithm first organizes all issued subspace skyline queries as a subspace tree sequence.Then it utilizes the share mechanism in tree paths and the relationship between skylines of subspaces to reduce the total query time.Detailed theoretical analyses and extensive experiments that demonstrate the proposed solution markedly outperforms the existing ones.(3) Efficiently retuming subspace skyline sets in distributed networksSince distributed networks become the network models of most enterprises,and the networks with C/S architecture can be easily updated to distributed networks with super peer architecture(SPA),we study the problem of returning subspace skyline sets in super peer distributed networks.The existing works do not consider the redundancies of objects on transferring data.That is,they do not consider how to avoid transferring many unnecessary objects.And all these existing works transfer the whole objects,and therefore,the cost of data transferring become huge as the increase of the dimensionality of these objects.In this paper,we avoid transferring redundant objects by the equivalence transformation rule between the subspace skyline operator and relational projection(union).And hence,we can markedly reduce the volume of data transferring.Moreover,we only transfer the encoding values of most objects,and do not need to transfer all values of objects,and hence can further reduce the cost of data transferring.On the other hand,APMSSQ algorithm is used to process subspace skyline computation in each super node.Detailed theoretical analyses and extensive experiments that demonstrate the proposed solution markedly outperforms the existing ones.
Keywords/Search Tags:subspace, Skyline query, Cell dominance, multi-query optimization, SPA network, equivalence transformation rule, distributed environments, redundant transferring
PDF Full Text Request
Related items