一种基于数据离散度无关性的数据立方体构建方法

摘要

本发明提供了一种基于数据离散度无关性的数据立方体构建方法，包括针对第一元组，利用其中的N个不同属性产生2

说明书

技术领域

本发明涉及通信技术领域，具体涉及一种基于数据离散度无关性 的数据立方体构建方法。

背景技术

OLAP(On-Line Analytical Processing，联机分析处理)是数据仓 库应用和决策支持系统的热点。OLAP分析是基于多维数据上的即席 (ad hoc)查询分析。支持在多维数据上进行上卷，下钻，切片等数据 操作，侧重决策支持，并且提供直观易懂的查询结果。而绝大多数OLAP 产品在进行数据分析之前，都要进行数据立方体预计算(即CUBE计 算)，生成物化方体。CUBE的预计算是OLAP查询分析的基础。在预 计算方面，Frag-Shells算法是一种较常用的计算方法。

但是Frag-Shells算法依赖于数据离散度，在数据之间数据量大、 离散度高的情况下表现出来效率低下。而现实生活中，对于具体的分 析需求，每个属性要包含很多的数值，因此数据的离散度往往会很大。 因此在数据量较大，数据离散度较高的情况下，现有的构建数据立方 体的Frag-Shells算法效率大大降低。

发明内容

针对现有技术中的缺陷，本发明提供一种基于数据离散度无关性 的数据立方体构建方法，解决了现有数据立方体构建方法中由于数据 离散度较高而引起的效率大大降低的问题。

本发明提供一种基于数据离散度无关性的数据立方体构建方法， 包括：

对于N维数据，每维数据中有n个属性，所述N*n个属性分布在 m个元组中；其中，N>1，n>1，每个元组对应一个元组标示符；

其中，每一个元组中有N个属性，所述N个属性分别属于不同维；

针对第一元组，利用其中的N个不同属性产生2^N个子集，每个子 集对应第一元组标识符；

将所述2^N个子集以及每个子集对应的元组标识符放入Hash表中， 所述Hash表中至少有两列，一列用来存放子集，一列用来存放所述子 集对应的元组标识符；

针对第二元组，利用其中的N个不同属性产生2^N个子集，每个子 集对应第二元组标识符；

将第二元组所产生的2^N个子集和Hash表中已有的子集进行对比；

若第二元组所产生的某个子集和Hash表中已有的某个子集一致， 则将该子集所对应的元组标识符添加到Hash表中与该子集对应的元组 标识符一列中；

若第二元组所产生的某个子集和Hash表中已有的子集都不相同， 则将该子集以及该子集对应的元组标识符放入Hash表中；

按照同第二元组同样的方式对第三元组至第m元组进行操作，得 到一张完整的Hash表；

根据所述完整的Hash表可以得到小于等于N的任意维数据立方 体。

优选地，若数据维数N值大于第一阈值时，则先将N维数据划分 为p个数据片段，每一数据片段包括两个以上的数据维，所述p个数 据片段共包括了N维数据，其中p<N；

对所述每一个数据片段构建每一数据片段的任意维数据立方体。

优选地，所述第一阈值为4。

优选地，采用MapReduce框架对所述p个数据片段进行并行处理。

由上述技术方案可知，本发明的基于数据离散度无关性的数据立 方体构建方法，利用每个元组中的属性产生全部维的属性子集，将属 性子集及该属性子集对应的标示符TID放在Hash表中，通过对所有元 组进行操作，维系和更新Hash表，最终得到包含所有维的完整Hash 表。该方法与数据离散度无关，解决了在数据离散度高的条件下，现 有Frag-Shells算法效率大大降低的问题。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面 将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而 易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通 技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图 获得其他的附图。

图1是本发明实施例一提供的基于数据离散度无关性的数据立方 体构建方法的流程图；

图2是本发明实施例提供的现有Frag-Shells算法中计算三维ABC 方体的过程示意图。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结 合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、 完整的描述，显然，所描述的实施例是本发明一部分实施例，而不是 全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有 作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护 的范围。

图1示出了本发明实施例一提供的基于数据离散度无关性的数据 立方体构建方法的流程图，本发明实施例一所述的基于数据离散度无 关性的数据立方体构建方法包括：

步骤101：对于N维数据，每维数据中有n个属性，所述N*n个 属性分布在m个元组中；其中，N>1，n>1，每个元组对应一个元组标 示符；其中，每一个元组中有N个属性，所述N个属性分别属于不同 维；针对第一元组，利用其中的N个不同属性产生2^N个子集，每个子 集对应第一元组标识符；将所述2^N个子集以及每个子集对应的元组标 识符放入Hash表中，所述Hash表中至少有两列，一列用来存放子集， 一列用来存放所述子集对应的元组标识符。

步骤102：针对第二元组，利用其中的N个不同属性产生2^N个子 集，每个子集对应第二元组标识符。

步骤103：将第二元组所产生的2^N个子集和Hash表中已有的子集 进行对比，判断Hash表中是否存在第二元组所产生的2^N个子集；若 存在，即第二元组所产生的某个子集和Hash表中已有的某个子集一致， 则执行步骤103a；；否则，即第二元组所产生的某个子集和Hash表中 已有的子集都不相同，则执行步骤103b。

步骤103a：将该子集所对应的元组标识符添加到Hash表中与该子 集对应的元组标识符一列中。

步骤103b：将该子集以及该子集对应的元组标识符放入Hash表 中。

步骤104：按照同第二元组同样的方式对第三元组至第m元组进 行操作，得到一张完整的Hash表。

步骤105：根据所述完整的Hash表可以得到小于等于N的任意维 数据立方体。

本发明实施例的基于数据离散度无关性的数据立方体构建方法， 利用每个元组中的属性产生全部维的属性子集，将属性子集及该属性 子集对应的标示符TID放在Hash表中，通过对所有元组进行操作，维 系和更新Hash表，最终得到包含所有维的完整Hash表。该方法与数 据离散度无关，解决了在数据离散度高的条件下，现有Frag-Shells算 法效率大大降低的问题。

优选地，若数据维数N值大于第一阈值时，则先将N维数据划分 为p个数据片段，每一数据片段包括两个以上的数据维，所述p个数 据片段共包括了N维数据，其中p<N；

对所述每一个数据片段按照步骤101-105所述方法构建每一数据 片段的任意维数据立方体。

优选地，所述第一阈值为4。

优选地，采用MapReduce框架对所述p个数据片段进行并行处理。

下面以一个具体实施例来对本发明实施例一所述的基于数据离散 度无关性的数据立方体构建方法进行解释。

如下表所示，按照倒排索引的方式对给定的N维数据进行归类， 数据维数N为7，七维数据分别为A、B、C、D、E、F、G。其中每 维数据下有若干个属性，例如A维数据下有a1、a₂、a₃三个属性。所 述N维数据下的所有属性分布在m个元组中，m为8。每个元组对应 一个元组标识符TID，这里，第一元组的元组标识符为1，第二元组的 元组标示符为2，具体可参见下表1。

这里，由于数据维数N大于第一阈值，则先将7维数据划分为3 个数据片段，(A，B，C)、(D，E)、(F，G)，对每一个数据片段按照 下面所述方法构建每一数据片段任意维数据立方体。

表1原数据库

例如，对于数据片段(A，B，C)构建其任意维数据立方体的方 法如下：

针对第一元组，其中有3个属性(a₁，b₁，c₁)，利用其中的3个不 同属性产生2³＝8个子集，即子集{a₁，b₁，c₁}、{a₁，*，*}、{*，b₁， *}、{*，*，c₁}、{a₁，b₁，*}、{a₁，*，c₁}、{*，b₁，c₁}、{*，*，*}， 其中每个子集对应第一元组标识符1，将所述8个子集以及每个子集对 应的元组标识符放入Hash表中，所述Hash表中至少有两列，一列用 来存放子集，一列用来存放所述子集对应的元组标识符TID。如下表2 所示意。

表2Hash表

子集 TID列表 {a₁，b₁，c₁} {1} {a₁，*，*} {1} {*，b₁，*} {1} {*，*，c₁} {1} {a₁，b₁，*} {1} {a₁，*，c₁} {1} {*，b₁，c₁} {1} {*，*，*} {1}

针对第二元组，其中有3个属性(a₁，b₂，c₂)，利用其中的3个不 同属性产生2³＝8个子集，即子集{a₁，b₂，c₂}、{a₁，*，*}、{*，b₂， *}、{*，*，c₂}、{a₁，b₂，*}、{a₁，*，c₂}、{*，b₂，c₂}、{*，*，*}， 其中每个子集对应第二元组标识符2。

将第二元组所产生的8个子集和上述Hash表中已有的子集进行对 比；

若第二元组所产生的某个子集和Hash表中已有的某个子集一致， 例如，第二元组所产生的子集{a₁，*，*}在上述Hash表中已经存在， 则将该子集所对应的元组标识符添加到Hash表中与该子集对应的元组 标识符一列中，即在原有的与该子集对应的元组标识符TID列表{1} 中增加第二元组的元组标识符：{1，2}。

若第二元组所产生的某个子集和Hash表中已有的子集都不相同， 例如第二元组所产生的子集{*，b₂，*}在上述Hash表中不存在，则将 该子集{*，b₂，*}以及该子集对应的元组标识符{2}放入到上述Hash 表中。

按照同第二元组同样的方式对第三元组至第八元组进行操作，得 到一张完整的Hash表。

根据所述完整的Hash表可以得到数据片段(A，B，C)的一维数 据立方体、二维数据立方体和三维数据立方体。

利用上述同样的方法对数据片段(D，E)和数据片段(F，G)进 行操作，得到数据片段(D，E)的一维数据立方体和二维数据立方体； 得到数据片段(F，G)的一维数据立方体和二维数据立方体。

为了说明本发明实施例所述方法的优势，下面结合现有技术中的 Frag-Shells算法进行一下对比。

同样，对于上述数据片段(A，B，C)，现有技术中的Frag-Shells 算法在计算数据片段(A，B，C)的一维数据立方体、二维数据立方 体和三维数据立方体时，采用如下做法：

1)一维方体：A方体、B方体、C方体；

2)二维方体：AB方体，AC方体，BC方体；

3)三维方体：ABC方体。

对于A方体，从表1中找出数据维A的各个属性所对应的元组标 识符，即{a₁}->{1，2，3}、{a₂}->{4，5}、{a₃}->{6，7，8}；

对于B方体，从表1中找出数据维B的各个属性所对应的元组标识 符，即{b₁}->{1}、{b₂}->{2，3，4，6}、{b₃}->{5，7，8}；

对于C方体，从表1中找出数据维C的各个属性所对应的元组标识 符，即{c₁}->{1，5，6，7}、{c₂}->{2，3，8}；

对于AB方体，需要对A方体的所有属性值和B方体中每一个属性 值做交集，即{a₁，b₁}->{1}、{a₁，b₂}->{2，3}、{a₂，b₂}->{4}；{a₂， b₃}->{5}、{a₃，b₂}->{6}、{a₃，b₃}->{7，8}；

同理算出方体AC和BC；

为了计算三维ABC方体，根据先计算出的AB方体，分别与C方体 各个属性维的TID值做交集，得出ABC方体。其具体过程可参见图2， 图2示出了现有Frag-Shells算法中计算三维ABC方体的过程示意图。

从上面的描述可知，现有技术中的Frag-Shells算法在由小维立方 体做交集生成多维立方体的过程中，每生成一个多维方体，就需要两 个维属性的多个属性值的元组标识符TID集合做交集。若数据的离散度 很大，那么倒排索引的元组个数也将变大，即元组标识符TID的个数将 变大，那么在做交集时，操作次数将大大增加，这样会严重拖慢算法 的处理速度。

而本发明实施例所述的基于数据离散度无关性的数据立方体构建 方法，利用每个元组中的属性产生全部维的属性子集，将属性子集及 该属性子集对应的标示符TID放在Hash表中，通过对所有元组进行操 作，维系和更新Hash表，最终得到包含所有维的完整Hash表。该方 法与数据离散度无关，因而解决了在数据离散度高的条件下，现有 Frag-Shells算法效率大大降低的问题。

在本申请的另外一个实施例中，采用MapReduce框架对实施例一 中所述三个数据片段(A，B，C)、(D，E)、(F，G)进行并行处理， 以提高系统的性能。

以上实施例仅用于说明本发明的技术方案，而非对其限制；尽管 参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员 应当理解：其依然可以对前述各实施例所记载的技术方案进行修改， 或者对其中部分技术特征进行等同替换；而这些修改或替换，并不使 相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。