一种分布式环境下基于度量空间的top‑k支配查询方法

摘要

本发明公开一种分布式环境下基于度量空间的top‑k支配查询方法，依次包括以下步骤：步骤1：给定查询输入集合Q以及度量空间中的距离公式d()，距离公式用来衡量整个数据对象与查询对象Q之间的距离；步骤2：根据步骤1提出基于集合ANN和k‑skyband并行算法。通过在分布式环境下充分利用各个节点之间的并行计算的特点，通过剪枝、排序极大的改善了在大数据集环境下基于度量空间的top‑k支配查询性能，加快查询速度，为用户的决策提供服务。

说明书

技术领域

本发明涉及一种查询方法，具体涉及一种在海量数据集中分布式环境下基于度量空间的并行top-k支配查询方法。

背景技术

基于度量空间的top-k支配查询作为一种重要的复杂查询越来越得到更多的关注，它从海量多维数据集中返回一部分满足用户需求的数据。这种类型的查询为用户提供决策，例如在网页搜索、多媒体检索、电子商务等领域有广泛的应用。该查询不需要用户给定评价函数且结果集可控，计算每个对象支配分数，返回支配分数最高的k个结果集。

基于度量空间的top-k支配查询定义如下：用O＝{o₁,o₂,…,o_n}表示所有数据对象的集合，o_i表示其中第i个数据对象，每个数据对象有D维，且都是空间中的一个点。对于一个度量空间的top-k支配查询，Q表示查询输入集合，d()表示度量空间中距离公式，这种距离公式可以自己定义，例如图中的最短路径、网络中的最大流量、曼哈顿距离等，k表示返回支配分数最高的k个结果。支配含义是：若存在o_i∈O,o_i'∈O，用符号＜表示两个对象之间的支配关系，若o_i＜o_i'，则有：

给定一个数据对象o_i∈O，对象o_i的支配分数dscore为整个数据集中被它支配对象的个数，如下：

dscore＝|{o_j∈O|o_i＜o_j}|

基于度量空间的top-k支配查询最后只要得到支配分数最高k个元素，是一种动态的top-k支配查询。Tiakas E等人最先提出该概念，但也只是在传统的单机模式下的研究，目前随着数据集急剧增加，传统的单机算法遇到性能瓶颈，且Tiakas E等人使用M-tree这种索引存储结构对于大数据集完全不适用，会导致大量的数据冗余，所以研究基于度量空间的并行top-k支配算法迫在眉睫。

发明内容

发明目的：本发明的目的在于解决现有技术中存在的不足，提供及一种分布式环境下基于度量空间的并行top-k支配查询方法。

技术方案：本发明所述的一种分布式环境下基于度量空间的并行top-k支配查询方法，依次包括以下顺序执行的步骤：

(1)给定查询输入数据对象集合Q以及度量空间中的距离公式d()，距离公式d()用来衡量整个数据对象O与查询输入数据对象集合Q之间的距离；

(2)根据步骤(1)提出基于集合ANN和k-skyband并行算，该并行算法的具体内容为：

(21)利用ANN(Q,k)剪枝：

根据距离度量函数d()和查询输入Q计算所有数据对象与查询输入对象之间的距离Deal_Data_RDD并将其保存在各个分区中然后每个分区单独并行求解该分区的中ANN(Q,k)，最后将每个分区的ANN(Q,k)结果通过reduce接口进行筛选得到全局的ANN(Q,k)；将获取的全局ANN(Q,k)广播到各个节点上，利用ANN(Q,k)去过滤原始的数据集，最后得到候选集KANN(Q,k)_RDD，KANN(Q,k)_RDD中一定包含最后的top-k支配结果集D，过滤的规则是不被ANN(Q,k)中对象所支配；

(22)利用k-skyband剪枝：

由于得到的KANN(Q,k)_RDD有可能非常的大，如果直接计算KANN(Q,k)_RDD中所有对象的支配分数也是非常耗时的，所以利用k-skyband思想，找到KANN(Q,k)_RDD中的k-skyband进一步剪枝得到最终的候选集GlobalCandidate(k-skyband)；

(23)获取top-k支配：

计算GlobalCandidate(k-skyband)中所有对象的支配分数，然后找出top-k个支配分数最高的，返回作为top-k支配结果。

进一步的，所述步骤(21)中，由于每个分区的ANN(Q,k)不一定是全局的ANN(Q，k)，则需要将各个分区的ANN(Q,k)一一比较距离的远近最终得到全局的ANN(Q，k)。

进一步的，所述步骤(23)的详细内容为：将步骤(22)中得到的候选集与原始数据集进行笛卡尔积运算，然后使用Spark提供的ReduceByKey的API接口，得到每个候选集的支配分数。

有益效果：本发明提供在分布式环境下基于度量空的top-k支配查询，并提出三种分布式算法去求解top-k支配，通过在分布式环境下充分利用各个节点之间的并行计算的特点，通过剪枝、排序极大的改善在大数据集环境下基于度量空间的top-k支配查询性能，加快查询速度，为用户的决策提供服务；具体包括以下优点：

(1)提出并行计算skyline方法，可以使每个分区都同时进行求解skyline，这样可以快速求解skyline从而得到top-k支配结果集；

(2)提出并行计算k-skyband方法，每个分区单独求解k-skyband，互不影响，利用k-skyband的特性不需要循环就可以得到结果；

(3)提出先利用集合ANN剪枝，然后并行计算k-skyband方法。有效的剪枝，减少了数据之间的比较操作，从而加快了查询速度。

附图说明

图1本发明中DAKDA算法的流程图；

图2为实施例中k的大小对查询影响示意图；

图3为实施例中m的大小对查询影响示意图；

图4为实施例中c的大小查询影响示意图；

图5为本发明中各个算法的可扩展性对比图；

图6为本发明分布式处理图；

图7为本发明的示例图。

具体实施方式

下面对本发明技术方案进行详细说明，但是本发明的保护范围不局限于所述实施例。

下文中所涉及符号和参数的定义如表1：

表1符号说明

定义1(KNN(q,k))：给定一个数据集O，d()为度量函数，且o∈O，对象o的k-近邻为KNN(o,k)，KNN(o,k)表示距离对象o最近的k个对象。

定义2(ANN(Q,k))：给定一个数据集O，d()为度量函数，Q表示一组查询输入对象集合Q＝{q₁,q₂,…,q_m}，ANN(Q,k)表示距离Q最近的k个对象。选择合理集合距离函数d()会影响查询，一般来说集合距离函数有：最小，最大，平均值等。

定义3(度量空间中的支配)：若(O,d())是一个度量空间，Q表示一组查询输入对象集合Q＝{q₁,q₂,…,q_m}。那么对于对象o∈O，它与Q中所有对象距离集合为：

adist(o,Q)＝{d(o,q₁),d(o,q₂),…,d(o,q_m)}

当对象p∈O，若o＜p，则有：

这种支配是通过距离的大小来衡量的。

定义4(基于度量的top-k支配)：给定一组查询输入Q，和距离度量函数d()。根据度量空间中的支配关系，若数据对象o_i∈O，对象o_i的支配分数为：

dscore＝|{p∈O|o＜p}|，其中返回其中支配分数最高的k个对象，就是基于度量空间的top-k支配查询结果集。

如图7,所示，本实施例中的基于度量空间的top-k支配查询，首先查询输入Q＝{q₁,q₂}，使用的距离度量函数d()为欧氏距离，top-1支配结果为o₁，因为o₁到q₁,q₂的距离均小于圆外(包括圆上)所有点，只有o₂对象不被o₁支配(因为o₂到q₁距离小于o₁到q₁距离)，如果空间中有n个数据对象o₁的支配分数为dscore(o₁)＝n-1，而o₂至少不支配对象o₁,o₃，所以o₂的支配分数dscore(o₂)≤n-2，则dscore(o₁)>dscore(o₂)所以top-1支配为o₁。

定义5(k-skyband)整个数据空间，至多k-1个对象支配对象o，这一系列o组成的集合就是k-skyband。

定理1：top-k支配结果集

证明.反证法，假设存在一个对象o₁∈D，且支配o₁的对象个数>k-1，因此一定存在k个对象的支配分数dscore≥o.dscore+1，此时矛盾，因此top-k支配结果集得证。

定理2：查询输入集合Q，ANN(Q,k)的k个对象{o₁,o₂,…,o_k}∈O，由(其中表示不支配)组成集合KANN(Q,k)，其中kANN(Q,k)包含对象ANN(Q,k)本身，top-k支配结果集

证明.设ANN(Q,1)查询对象Q的1-近邻对象为o，因为D-1ANN(Q,1)中所有的对象均被对象o所支配，所以top-1支配一定在1ANN(Q,1)。若top-1支配不是对象o，则由上可知支配分数第二高的对象一定在集合1ANN(Q,1)中；若top-1支配是对象o，则由上可知支配分数第二高的对象一定在集合2ANN(Q,2)中，依次类推我们知道top-k支配结果集得证。

以下所有的算法均在spark平台上实现：：

(1)基于skyline的top-k支配算法(DSDA)

现有的DSDA中，首先将数据集随机分配到各个节点中，然后使用spark中的Mappartition接口，在Mappartition接口中实现计算skyline算法，这样可以得到每个分区的skyline，最后将每个分区的skyline两两比较获取全局skyline，返回skyline中支配分数最高的对象就是top-k支配的结果集。依次进行k次循环就可以得到最终的结果集。

(2)基于k-skyband的top-k支配算法(DKDA)

现有的DKDA，将该算法在spark集群中并行化，并行算法的思想类似于skyline。根据定理1可知top-k dominating结果集所以先求k-skyband，然后从k-skyband中返回支配分数最高的k个对象为top-k dominating结果集。

首先将数据集随机分配到各个节点中，然后使用spark中的Mappartition接口，在Mappartition接口中实现计算k-skyband算法，这样可以得到每个分区的k-skyband，最后将每个分区的k-skyband两两比较获取全局k-skyband，返回k-skyband中支配分数最高的对象就是top-k支配的结果集。该方法对比于skyline方法优点在于不需要进行k次循环，但是求解原始数据集的k-skyband非常耗时。(3)基于集合ANN剪枝和k-skyband的并行top-k支配算法(DAKDA)

由于算法1需要进行k次循环，导致查询时间随k增大而增大，而算法2求解原始数据集k-skyband非常耗时，所以本发明可以进行剪枝。

本发明中，根据定理1可知top-k支配结果集而根据定理2可知top-k支配结果集由于求解k-skyband比求解KANN(Q,k)费时，所以先利用集合ANN去掉不是候选集的数据，得到候选集KANN(Q,k)，然后求解KANN(Q,k)中的k-skyband，最后从k-skyband中返回支配分数最高的k个结果为top-k支配。步骤如图1所示：

步骤1：利用ANN(Q,k)剪枝

如下图1阶段一所示，需要根据距离度量函数d()和查询输入Q对数据进行处理得到各个对象与查询对象之间的距离Deal_Data_RDD保存在各个分区中，然后求每个分区的中ANN(Q,k)，最后得到全局的ANN(Q,k)。利用全局的ANN(Q,k)去filter原始的数据集得到候选集KANN(Q,k)_RDD，根据定理2可以知道KANN(Q,k)_RDD中一定包含最后的top-k支配结果集D。

步骤2：利用k-skyband剪枝

如下图1阶段二所示，由于得到的KANN(Q,k)_RDD有可能非常的大，如果直接计算KANN(Q,k)_RDD中所有对象的支配分数也是非常耗时的，所以利用k-skyband思想，找到KANN(Q,k)_RDD中的k-skyband进一步剪枝得到最终的候选集GlobalCandidate(k-skyband)。根据定理1可以知道GlobalCandidate(k-skyband)中一定包含最终的top-k支配结果集D。

步骤3：获取top-k支配结果集

如下图1阶段三所示，将候选集与原始数据集进行笛卡尔积运算，形成<key,value>形式，其中key表示候选集，若候选集支配原始数据集中的一个数据则value为1，否则为0；最后通过ReduceByKey这个API接口得到GlobalCandidate(k-skyband)中所有对象的支配分数，然后找出top-k个支配分数最高的。

实施例1：

本实施例是在一个7节点的spark分布式集群上完成的，spark是搭建在hadoop上，使用hadoop的yarn资源管理器和HDFS文件存储系统。7个结点中master结点既作为Driver结点又做worker结点，其余6个结点均为worker结点。所有的算法均用Scala语言编写，基本配置如下表2：

表2实验环境配置

如图2至图5所示，实验部分主要从以下若干个方面来评价DSDA、DKDA、DAKDA三个算法：分区数量num对查询时间的影响(选择合理分区数目)、返回结果k对查询的影响、查询输入集合Q大小对查询时间的影响、各个算法候选集的比较以及算法的可扩展性，实验中的参数默认设置如下表3所示，其中覆盖率c＝覆盖输入Q最小圆的半径/覆盖所有数据集最小圆半径。

表3实验默认参数配置

先对真实的较大数据集进行分析：ZILLOW数据集，原始数据集有2245109条，由于有的记录中有的属性值空缺的，删除后的数据集大小为1771107条，总共有5个属性，对于度量空间的距离公式使用的是马哈顿距离。具体流程如图1所示。如图6所示，将数据集均匀分不到各个slaver节点中，然后每个节点单独执行上述提出的算法，得到候选集，最后汇总得到top-k支配结果集。

给定m＝5，实验1评价各个算法随返回结果数量k变化情况的性能。如图2所示，发现DSDA算法随k的变化比较明显，而DAKDA算法随k的变化小，说明DSDA算法对k比较敏感。

给定k＝10，实验2评价各个算法随查询集合Q大小m变化情况的性能。从图3中我们发现随着m的增大，算法DKDA急剧增大。

给定k＝10，m＝5，实验3评价各个算法随查询集合Q覆盖率c变化情况的性能。如图4所示：在覆盖率较大情况下DSDA算法查询最慢。本发明方法的可扩展性如图5所示。

通过上述实施例1可以看出，本发明对于给定的数据集，根据用户的查询输入以及给定的度量空间中的距离公式，提出适合于大数据集的top-k支配并行的方案；利用k-skyband结果集中包含top-k支配结果集特性，先利用集合k-近邻剪枝获取候选集，然后再获取候选集的k-skyband，最后求解top-k支配结果。

这种基于k-skyband和集合ANN方法对比于传统的使用skyline求解top-k支配，以及单纯使用k-skyband求解top-k支配方法，对数据进行了筛选，减少了数据之间比较次数，加快了查询速度。本发明在spark平台上并行实现，由于基于度量空间的top-k支配查询目前研究只是单机算法，而本本发明提出的是并行算法，远快于单机而实施例1的结果也恰恰证明该结论，所以本发明将传统的基于skyline以及k-skyband方法并行化，法查询速度更快，且对于较大的输入集合或者海量数据集都适用。