摘要: 1．本文的创新点现有的研究工作只限于单个子空间skyline查询,因此无法适用于多用户skyline查询的环境.本文的创新点主要在于给出一种能够同时处理和优化多个子空间skyline查询的方法AOMSSQ,从而扩展现有的skyline查询应用到多用户系统中.2．实现方法本文给出的多skyline查询优化方法是基于单个子空间skyline查询方法的.然而现有处理单个子空间skyline查询方法SUBSKY存在着3个性能缺陷,因此,本文首先基于正规格索引提出一种处理单个skyline查询的高效算法CDCA. CDCA算法首先将数据集划分为若干个组，其中每一组的所有对象均落入同一个投影格中．然后，CDCA算法将这些格组织为序列,序列中的格满足如下条件：前面的格在子空间上至少存在一个维的位置值比后面的格小．接着，从第一个格开始，依次将格序列中的格与它前面的格进行比较，如果在它前面的格中，存在一个格，使得该格完全支配当前格，我们称格当前格为不活动格，那么从格序列中删除当前格；如果当前格是活动格，那么首先过滤掉格当前格中在子空间上被同一个格中的其它对象支配的所有对象，记保留下来的对象集合为Sj，然后，对于Sj中的每个对象p，将p与所有局部支配当前格的格中的对象进行比较，如果p被这些对象支配，则过滤掉p；当处理完格序列中的最后一个格时，序列里面所有活动格中保留下来的对象的并集即为所求的结果．AOMSSQ算法基于CDCA算法．假定用户发出w个维空间V1, V2,…, Vw上的skyline查询．我们首先对w个维空间进行分组，每一组对应一棵维空间树，分组过程如下：(1) 将这w个维空间组织成一致维空间序列ODS;(2) 循环如下过程直到ODS为空：①获取ODS中的第１个维空间V’；②以V’为根构造ODS上的最大维空间树Tdim；③从ODS中删除Tdim的所有节点对应的维空间．当我们获取t棵维空间树之后，对于每棵维空间树，我们从根节点出发，以广度优先遍历的方式来处理每个节点上的skyline查询,处理策略如下:(1)对于根节点，我们使用CDCA算法直接在原始数据集中获取根节点维空间上的skyline对象集合;(2) 对于其余的非根节点,我们同样使用CDCA算法来处理该节点上的skyline查询，然而此时，CDCA算法的输入不是整个原始数据集,而是该节点的父节点parent维空间上的sky(parent)集合.最后获取每个重复对象.本文实验的环境是:DELL微机,P4 2.4 GHz处理器,1G内存,160G硬盘, Windows XP操作系统.所有程序在Jbuilder 9.0软件下编译通过.实验中使用的数据集有两类:实际数据集和综合数据集.其中实际数据集有两个:(1)欧洲足球运动员统计资料,包括21649条记录,每条记录具有8个属性,从1920年到2006年.该数据集可以从网站www.profootball.com上下载; (2)日本千叶大学医院胶原质疾病数据,包括165937条记录,每条记录具有9个属性,从1980年到1999年.该数据集可以从网站www.lisp.vse上下载.综合数据集包含两种分布类型:(1)独立分布类型,对象各维值不具有相关性; (2)反相关分布类型,对象在一部分维度上取值较优而在另一部分维度上取值较差.3．结论 本文给出的多skyline查询优化方法能够有效适用于多用户环境,详细理论分析以及大量的实验评估表明本文给出的方法具有有效性和可扩展性。4．本文的主要贡献 本文主要有4个贡献:(1)首次考虑在多用户环境下如何优化用户发出的多个子空间skyline查询问题。(2)本文提出一种有效处理任意维空间上的skyline查询计算的方法CDCA,同时给出一种有效的格剪枝技术来进一步加快返回单个子空间skyline查询的结果集。(3)基于CDCA算法,本文给出一种有效的处理多个子空间skyline查询的方法AOMSSQ。(4)分别使用实际数据集和综合数据集来验证本文方法的有效性和实用性。