1.一种并行top-k范围skyline查询方法,其特征在于,包括以下步骤:(1)获取需要查询的原始数据集、该原始数据集中每个数据点的属性个数d、对原始数据集的查询范围Ω(其中查询范围Ω的起始点为qs,结束点为qe,且起始点qs和结束点qe具有d个属性)、以及范围skyline的查询结果数量k,其中d、k为任意自然数;
(2)将步骤(1)中得到的原始数据集中的每个数据点与该原始数据集的查询范围组合成该数据点对应的数据元组,并将每个数据元组的评分初始化为0;
(3)对于所有数据元组而言,根据其对应的各个数据点到查询范围的起始点qs的距离,按照距离升序的方式对这些数据元组进行并行排序,并将排序结果中的第一个数据元组加入到范围skyline的第一候选查询结果中;
(4)设置计数器count=1;
(5)判断count是否大于步骤(3)得到的排序结果中数据元组的总数,如果是则进入步骤(11),否则进入步骤(6);
(6)从步骤(3)的排序结果中获取第count个数据元组,并使用范围Skyline查询(Range Skyline Query,简称RSQ)方法确定第count个数据元组对应的数据点与第一候选查询结果中每一个数据元组对应数据点之间的范围支配关系;
(7)根据步骤(6)中确定的第count个数据元组对应的数据点与第一候选查询结果中每一个数据元组对应数据点之间的范围支配关系对该第count个数据元组对应的数据点对应的查询范围进行更新,记录此时第一候选查询结果中的数据元组,并判断更新后的该查询范围相对更新前的查询范围是不变,还是缩小,如果不变则进入步骤(9),如果缩小则进入步骤(8);
(8)将步骤(7)中记录的第一候选查询结果中使得第count个数据元组对应数据点对应的查询范围发生更新的数据元组的评分加1,然后进入步骤(10);
(9)将步骤(6)中获取的第count个数据元组加入第一候选查询结果中,然后进入步骤(10);
(10)设置计数器count=count+1,并返回步骤(5);
(11)对于第一候选查询结果中的所有数据元组而言,利用双调排序算法(Bitonic sort algorithm)并行地对所有数据元组的评分按照从大到小的顺序进行排序;
(12)从步骤(11)获得的排序结果中获取前k个数据元组对应的数据点,将这些数据点加入最终查询结果中,过程结束。
2.根据权利要求1所述的并行top-k范围skyline查询方法,其特征在于,步骤(3)包括以下子步骤:(3-1)根据以下公式计算每个数据点到查询范围的起始点qs的距离dis(Pi):其中i∈[1,原始数据集中数据点的总数],Pij表示第i个数据点的第j个属性值,qsj表示查询范围的起始点qs的第j个属性值,且j∈[1,d];
(3-2)利用双调排序算法并行地对步骤(3-1)得到的到查询范围的起始点qs的距离按照从小到大的顺序进行排序;
(3-3)将排序结果中的第一个数据元组加入到范围skyline的第一候选查询结果中。
3.根据权利要求1所述的并行top-k范围skyline查询方法,其特征在于,前一个数据点与后一个数据点之间的范围支配关系包括:A、前一个数据点在其对应的查询范围内都不被后一个数据点支配;以及B、前一个数据点在其对应的查询范围内被后一个数据点支配。
4.一种并行top-k范围skyline查询系统,其特征在于,包括以下步骤:第一模块,用于获取需要查询的原始数据集、该原始数据集中每个数据点的属性个数d、对原始数据集的查询范围Ω(其中查询范围Ω的起始点为qs,结束点为qe,且起始点qs和结束点qe具有d个属性)、以及范围skyline的查询结果数量k,其中d、k为任意自然数;
第二模块,用于将第一模块中得到的原始数据集中的每个数据点与该原始数据集的查询范围组合成该数据点对应的数据元组,并将每个数据元组的评分初始化为0;
第三模块,用于对于所有数据元组而言,根据其对应的各个数据点到查询范围的起始点qs的距离,按照距离升序的方式对这些数据元组进行并行排序,并将排序结果中的第一个数据元组加入到范围skyline的第一候选查询结果中;
第四模块,用于设置计数器count=1;
第五模块,用于判断count是否大于第三模块得到的排序结果中数据元组的总数,如果是则进入第十一模块,否则进入第六模块;
第六模块,用于从第三模块的排序结果中获取第count个数据元组,并使用范围Skyline查询方法确定第count个数据元组对应的数据点与第一候选查询结果中每一个数据元组对应数据点之间的范围支配关系;
第七模块,用于根据第六模块中确定的第count个数据元组对应的数据点与第一候选查询结果中每一个数据元组对应数据点之间的范围支配关系对该第count个数据元组对应的数据点对应的查询范围进行更新,记录此时第一候选查询结果中的数据元组,并判断更新后的该查询范围相对更新前的查询范围是不变,还是缩小,如果不变则进入第九模块,如果缩小则进入第八模块;
第八模块,用于将第七模块中记录的第一候选查询结果中使得第count个数据元组对应数据点对应的查询范围发生更新的数据元组的评分加1,然后进入第十模块;
第九模块,用于将第六模块中获取的第count个数据元组加入第一候选查询结果中,然后进入第十模块;
第十模块,用于设置计数器count=count+1,并返回第五模块;
第十一模块,用于对于第一候选查询结果中的所有数据元组而言,利用双调排序算法并行地对所有数据元组的评分按照从大到小的顺序进行排序;
第十二模块,用于从第十一模块获得的排序结果中获取前k个数据元组对应的数据点,将这些数据点加入最终查询结果中,过程结束。
5.根据权利要求4所述的并行top-k范围skyline查询系统,其特征在于,第三模块包括:第一子模块,用于根据以下公式计算每个数据点到查询范围的起始点qs的距离dis(Pi):其中i∈[1,原始数据集中数据点的总数],Pij表示第i个数据点的第j个属性值,qsj表示查询范围的起始点qs的第j个属性值,且j∈[1,d];
第二子模块,用于利用双调排序算法并行地对第一子模块得到的到查询范围的起始点qs的距离按照从小到大的顺序进行排序;
第三子模块,用于将排序结果中的第一个数据元组加入到范围skyline的第一候选查询结果中。
6.根据权利要求1所述的并行top-k范围skyline查询系统,其特征在于,前一个数据点与后一个数据点之间的范围支配关系包括:A、前一个数据点在其对应的查询范围内都不被后一个数据点支配;以及B、前一个数据点在其对应的查询范围内被后一个数据点支配。