基于不确定偏好关系的轮廓查询的并行方法

摘要

本发明公开了一种基于不确定偏好关系的轮廓查询的并行方法，实施步骤包括：输入数据集D、初始化数据集D的标签长度|L|，根据标签长度|L|生成2

说明书

技术领域

本发明涉及大规模数据轮廓查询、推荐系统等应用领域的不确定偏好的轮廓查询方法的并行实现的研究，具体涉及一种基于不确定偏好关系的轮廓查询的并行方法。

背景技术

轮廓查询也被称为Skyline查询，最早作为最大化向量问题研究，是一个典型的多目标优化问题，目前在数据库领域引起了广泛关注。Skyline查询是指从给定的一个N维空间的对象集合S中选择一个子集，该子集中的点均不能被S中其它的点所支配，满足此条件的点称为SP(Skyline Point)。此处的支配关系指在N维空间内，若存在两个对象P和Q，对象P的N维数据中的每一维都优于或等于Q，且至少存在一个维度要优于Q，则称P支配Q。

随着信息技术的不断发展和现实应用需求的不断扩大，在无线传感器网络、无线射频识别RFID(Radio Frequency Identification)网络、移动对象跟踪、气象雷达网络和隐私保护等应用中逐渐涌现出一类数据，即不确定性数据。目前学术界对于不确定数据的Skyline查询开展了非常多的研究，相比之下对于不确定偏好的Skyline查询的研究才刚刚起步。当前存在的基于不确定偏好的Skyline查询算法都是基于抽样或者近似原理来计算，尚还没有算法能够准确查询大规模数据集中基于不确定偏好的Skyline。和不确定数据相似，不确定偏好广泛存在于大量应用中。不确定偏好存在的原因有很多，首先在不同的应用背景中“好”与“坏”的标准是相对的；其次是在很多时候我们无法百分之百判断两个属性值之间的好坏，在这种情况下我们使用概率来描述这两个属性值之间的好坏情况。比如60％情况下属性值a比属性值b好，或者30％情况下属性值b比属性值a好。不确定偏好的Skyline查询是为适应现实环境中不断出现的不确定偏好应用而提出的一类Skyline查询。自从将Skyline查询引入不确定偏好之后，基于不确定偏好的Skyline查询在推荐系统、人工智能、信息检索、数据挖掘和决策制定等众多应用中发挥着重要作用。目前已成为数据库领域的一个研究新的热点。随着近年来不确定偏好应用的广泛兴起和发展，高效处理不确定偏好的Skyline查询成为当前亟待解决的问题。然而，由于查询需求的不断扩大及其计算时间复杂度与数据集的大小成指数关系，导致已有的集中式方法难以满足现实应用对查询效率的需求。

由于不确定偏好Skyline建模的特点以及复杂的概率表示和计算，使得不确定偏好的Skyline查询面临严峻挑战。而且因为基于不确定偏好Skyline查询指数级别的时间复杂度，不确定偏好的Skyline查询面临着查询实用性的问题。当前的基于不确定偏好Skyline查询都是串行方法，其性能不能满足大规模查询的需求，目前还没有基于不确定偏好Skyline的并行查询方法。

发明内容

本发明要解决的技术问题是：针对现有技术的上述问题，提供一种并行进程数目可控、能最大化并行效率、所需时间随着标签长度指数下降，能够极大的减少查询时间，实现高效查询针对大规模数据的基于不确定偏好关系的轮廓查询的并行方法。

为了解决上述技术问题，本发明采用的技术方案为：

一种基于不确定偏好关系的轮廓查询的并行方法，其特征在于实施步骤包括：

1)输入数据集D，数据集D＝{Q¹,Q²,...,Qⁿ}为一个包含n个数据元组的数据集，Qⁱ均为数据集D中的第i个数据元组，1≤i≤n，数据元组其中表示元组Qⁱ的第j个属性值，1≤j≤d，d表示元组的属性数目；初始化标签长度|L|；

2)根据标签长度|L|将数据集划分D生成2^L个不同的标签L，数据集D的标签L是一个二进制数，L[i]表示标签L的第i位，|L|表示标签L的位数；

3)从数据集D中遍历选择一个数据元组作为当前数据元组O；

4)针对当前数据元组O的轮廓查询Sky(O)包含2ⁿ项，将当前数据元组O的轮廓查询Sky(O)划分为相应的大小相等的2^L个不相交晶格，每一个晶格都对应于一个标签；其中任意一个晶格[α，β]，其标签为L；任意一个属于[α，β]的元素S满足如果标签L的第i位L[i]等于1，则数据集D中的第i个数据元组Qⁱ属于元素S；如果L[i]＝0，则数据集D中的第i个数据元组Qⁱ不属于元素S；

5)分别采用2^L个进程并行计算2^L个不相交晶格的值，每个进程计算一个晶格，将各个进程计算得到的结果相加得到当前数据元组O的轮廓查询Sky(O)并输出；

6)判断数据集D中的n个数据元组是否已经遍历完毕，如果尚未遍历完毕，则跳转执行步骤3)；否则，结束并退出。

优选地，步骤1)初始化数据集D的标签长度|L|具体是指根据计算节点分配得到的计算资源确定数据集D的标签长度|L|，且计算节点分配得到的计算资源中的最大并发进程数P和数据集D的标签长度|L|之间满足表达式|L|≤log₂P。

本发明基于不确定偏好关系的轮廓查询的并行方法具有下述优点：本发明对于数据集D中任意一个数据元组O，根据标签长度|L|，将当前数据元组O的轮廓查询Sky(O)中包含的2ⁿ项划分为不相交的2^L晶格。并行2^L个进程计算这2^L个不相交晶格的值，每个进程计算一个晶格。最后将各个进程计算得到的结果相加得到当前数据元组O的轮廓查询Sky(O)的值。通过上述并行计算方法，即可对基于不确定偏好关系的轮毂查询完成并行计算。上述并行计算可以通过调节标签长度L来实现不同进程数目的并行。既能达到最大并行效率，又能根据机器的实时状态调节并行进程的数目。本发明将并行2^L个进程计算这2^L个不相交晶格的值，因此每个进程所承担的计算量是一致的。所以每个进程所需要的计算时间基本相同，采用本发明基于不确定偏好关系的轮廓查询的并行方法能够最大限度利用CPU的计算能力，从而使并行效率最大化，具有以下效果：

1)控制并行进程数目：通过控制标签长度|L|能够控制并行进程数目。可以根据机器的实时状态调整并行进程数；

2)最大化并行效率：本发明将任意当前数据元组O的轮廓查询Sky(O)中包含的2ⁿ项均等的划分为不相交晶格，所以每个进程上所承担的计算量大小是一致的，不会出现有进程空闲等待的情况发生，因此本发明能最大化并行效率；

3)高效查询：采用本发明可实现高效查询。本发明中并行计算方法所需时间随着标签长度|L|指数下降。能够极大的减少查询时间，实现高效查询。

附图说明

图1为本发明实施例方法的基本流程示意图。

图2为本发明实施例方法的标签划分示意图。

图3为本发明实施例方法的扩展性验证试验结果。

具体实施方式

如图1所示，本实施例基于不确定偏好关系的轮廓查询的并行方法的实施步骤包括：

1)输入数据集D，数据集D＝{Q¹,Q²,...,Qⁿ}为一个包含n个数据元组的数据集，Qⁱ均为数据集D中的第i个数据元组，1≤i≤n，数据元组其中表示元组Qⁱ的第j个属性值，1≤j≤d，d表示元组的属性数目；初始化标签长度|L|；本实施例中，输入数据集D为包含6个数据元组的数据集，D＝{Q¹,Q²,...,Q⁶}，数据元组的上标序号被用来标识数据元组。2^D为数据集D的幂集其中包含2^|D|个元素。

本实施例中，步骤1)初始化数据集D的标签长度|L|具体是指根据计算节点分配得到的计算资源确定数据集D的标签长度|L|，且计算节点分配得到的计算资源中的最大并发进程数P和数据集D的标签长度|L|之间满足表达式|L|≤log₂P。本发明中的并行算法部署在国防科学技术大学天河2A计算机节点上，计算节点分配得到的计算资源为两颗八核CPU，因此在此计算节点上最多并发16条进程，所以|L|≤4。本实施例中取标签长度|L|＝2。

2)根据标签长度|L|将数据集划分D生成2^L个不同的标签L，数据集D的标签L是一个二进制数，L[i]表示标签L的第i位，|L|表示标签L的位数；

本实施例中取标签长度|L|＝2，因此共生成4个标签，分别为{(00)，(01)，(10)，(11)}，参见图2中，分别表示为Label(00)、Label(01)、Label(10)、Label(11)，其中标签中的数字为数据元组Qⁱ的上标序号，例如1代表Q¹，12代表{Q¹,Q²}，代表任意当前数据元组O的轮廓查询Sky(O)中包含的64项。

3)从数据集D中遍历选择一个数据元组作为当前数据元组O；

4)针对当前数据元组O的轮廓查询Sky(O)包含2ⁿ项，将当前数据元组O的轮廓查询Sky(O)划分为相应的大小相等的2^L个不相交晶格，每一个晶格都对应于一个标签；其中任意一个晶格[α，β]，其标签为L；任意一个属于[α，β]的元素S满足如果标签L的第i位L[i]等于1，则数据集D中的第i个数据元组Qⁱ属于元素S；如果L[i]＝0，则数据集D中的第i个数据元组Qⁱ不属于元素S；

5)分别采用2^L个进程并行计算2^L个不相交晶格的值，每个进程计算一个晶格，将各个进程计算得到的结果相加得到当前数据元组O的轮廓查询Sky(O)并输出；

6)判断数据集D中的n个数据元组是否已经遍历完毕，如果尚未遍历完毕，则跳转执行步骤3)；否则，结束并退出。

对于任意当前数据元组O而言，表示当前数据元组O支配数据集D中的第i个数据元组Qⁱ，当且仅当O在所有属性都比优于或等于并且至少在一个属性上严格优于e_i表示事件P_r(e_i)表示e_i发生的概率，根据前述定义则有式(1)和式(2)：

式(1)和(2)中，e_i表示事件P_r(e_i)表示e_i发生的概率，表示支配，表示数据元组Qⁱ的第1个元素，表示数据元组Qⁱ的第d个元素，O₁表示数据元组O的第1个元素，O_d表示数据元组O的第d个元素，数据集D中的各个属性相互独立。

对于数据集D而言，一个任意当前数据元组O属于轮廓集合Skyline表明当前数据元组O不被数据集D中其他元组所支配。当前数据元组O的轮廓查询Sky(O)表示当前数据元组O在轮廓集合Skyline中的概率。因此则有式(3)：

式(3)中，Sky(O)为当前数据元组O的轮廓查询，n为数据集D包含的数据元组数量，Qⁱ均为数据集D中的第i个数据元组，表示e₁,e₂,…,e_n联合发生的概率，e_i表示事件

定义且根据该定义则有式(4)；

式(4)中，E_I表示事件数据集I中的所有元素联合支配O，I表示数据集D中的一个子集，Qⁱ表示数据集D中的第i个数据元组，e_i表示事件

根据式(4)和和容斥原理可知式(5)：

式(7)中，Sky(O)为当前数据元组O的轮廓查询，n表示数据集D中包含的数据元组个数，k为数据元组的序号，I表示数据集D中的一个子集，|I|表示I中的元素个数，E_I表示事件数据集I中的所有元素联合支配O，P_r(E_I)表示E_I发生的概率。由上述公式可知，当前数据元组O的轮廓查询Sky(O)包含2ⁿ项，计算当前数据元组O的轮廓查询Sky(O)的时间复杂度为O(2ⁿ)。

为了对本实施例基于不确定偏好关系的轮廓查询的并行方法的并行效率进行验证，针对不同大小的数据集分别运行现有串行算法和本实施例基于不确定偏好关系的轮廓查询的并行方法，现有串行算法和本实施例基于不确定偏好关系的轮廓查询的并行方法所需要的时间如图2所示。在实验中记录串行算法运行时间为t₁，串行算法运行时间为t₂。如图2所示，黑色柱状图表示t₁，格子柱状图表示t₂，t₂随着并行进程数的增加指数下降。并行效率如图2所示当并行进程数为16时，speedup≥12。利用不同大小和维度的数据集验证并行算法的可扩展性。如图3所，在不同大小和维度的数据集中，当使用16条进程并行计算时，加速比都大于等于10。终上所述，本实施例基于不确定偏好关系的轮廓查询的并行方法不但能够用于上面介绍的基于不确定偏好关系的轮廓查询的并行计算，同样可以用到各类基于偏好查询的推荐系统的并行实现。本实施例基于不确定偏好关系的轮廓查询的并行方法能够加快对偏好不确定的查询的处理速度，最大化CPU利用率；实时返回查询结果，提高用户体验。

以上所述仅是本发明的优选实施方式，本发明的保护范围并不仅局限于上述实施例，凡属于本发明思路下的技术方案均属于本发明的保护范围。应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理前提下的若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。