一种并行处理Skyline查询的有效方法  

An E?cient Method for Parallel Processing of Skyline Queries

作　　者：黄震华[1,2] 向阳[1] 薛永生[3] 赵杠[4] 

机构地区：[1]同济大学电子与信息工程学院,上海200092 [2]同济大学嵌入式系统与服务计算教育部重点实验室,上海200092 [3]厦门大学信息科学与技术学院,厦门361005 [4]复旦大学信息科学与工程学院,上海200433

出　　处：《自动化学报》2010年第7期968-975,共8页Acta Automatica Sinica

基　　金：国家高技术研究发展计划(863计划)(2008AA04Z106);国家自然科学基金(60903032);教育部博士点基金(20090072120056);同济大学青年优秀人才基金(0800219093)资助~~

摘　　要：Skyline查询是近年来数据库领域的一个研究重点和热点,这主要是因为Skyline查询在许多领域有着广泛的应用.现有的工作大都集中于单处理机环境,然而,由于Skyline查询是CPU敏感的,因此,在实际应用中,现有的方法具有很大的局限性.基于此,提出一种有效降低处理Skyline查询时间开销的并行算法PAPSQ(Parallel algorithm for processing skyline queries).算法有机结合多维数据对象的自身特性和通用多处理机系统的实施优点,以Skyline查询搜索偏序格为底层结构,利用多维数据对象的同胚评估值和偏序格加权技术来有效提高并行处理Skyline查询的效率.实验评估表明,PAPSQ算法具有有效性和实用性.Skyline query processing has recently received a lot of attention in database community. Most related works focus on the single processor environment. However, since skyline queries are CPU-sensitive and time costly, the existing methods have prodigious limitations in real applications. Motivated by the above fact, in this paper, we propose an effcient method for parallel processing of skyline queries, called parallel algorithm for processing skyline queries （PAPSQ）. The PAPSQ algorithm seamlessly combines the speciality of multidimensional data objects and the implementary advantage of universal multiprocessor systems. Specially, the PAPSQ algorithm takes the partial order lattice of skyline queries as substrate structure, and utilizes the homeomorphism evaluation of multidimensional data objects and the weighted technology to markedly improve the performance of parallel processing of skyline queries. Furthermore, detailed theoretical analyses and extensive experiments are given to demonstrate that the algorithm is both effcient and effective.

关 键 词：SKYLINE查询 并行处理 搜索偏序格 查询优化 性能评估 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]