• 快捷搜索
  • 全站搜索

海量数据上一种有效的聚集查询算法

2016-03-16 15:57:50作者:北京大学深圳研究生院计算机应用专业海量数据课题组编辑:金融咨询网
随着大数据渗透到了金融的各个领域,海量数据上聚集查询算法的设计与实现能够作为数据分析和挖掘的支撑与基石。本文通过分析现有的海量数据上聚集查询算法的特点与海量数据的特性,提出了海量数据上快速聚集算法,对海量数据的聚集查询任务提供有效支持。

大数据时代的到来引起IT界又一次颠覆性的技术变革,同时也引起了整个信息技术界和金融界的高度关注。由于金融领域涉及业务范畴广泛,产生的业务数据流转于业务的各个节点中,且数据使用方式多种多样——股份的预测离不开对经济形势的数据挖掘,银行的业务创新离不开对客户的数据分析。同时金融数据容量大,常以TB甚至PB作为基本处理单位,因此难以直接分析出数据中存在的关联和规则。在实际业务中需要对数据进行相应的处理后进一步分析挖掘,支撑金融业务人员进一步挖掘数据间隐藏的知识和价值。

  在海量数据的场景下聚集查询能够提供数据集合间的概要信息。如查询具有不同用户体验的用户,查询某一地区用户平均消费水平等。这些信息有助于挖掘或预测用户行为模式,帮助研究人员进行决策和数据分析,进而对用户提供更具有针对性的服务。然而在海量数据场景下的聚集查询操作存在以下几方面的性能瓶颈。

  (1)由于用户查询需求不断变化,难以预先确定聚集查询所涉及的元组属性范围,同时海量数据场景下难以获得具体的数据分布情况,因此难以预存储所有可能的聚集查询结果,需要对每一个聚集查询进行实时处理。

  (2)聚集查询需要扫描并读取全部数据后进行相应的聚集运算,然而由于数据的海量性,特别是数据中存在大量的元组(如我国一个省内单月移动通讯信令数据就多达上千万条元组)。往往一个简单的聚集查询就会花费数分钟的时间进行执行,难以及时地向用户反馈查询结果。因此不能满足金融业的快速反应需求。

  本课题组通过提出一种新的适用于海量数据的聚集查询算法BBSA(Based on Bit String Array aggregation algorithm),提高金融数据查询处理效率,减少查询响应时间。该算法能够处理在任意属性上的单属性和多属性聚集查询,也不依赖于数据的具体存储模型,因此具有广泛的适用性。

一、现有相关工作

  当前针对海量金融数据的聚集查询主要有两种方式:基于排序(sort一based)和基于哈希(hash—based)。基于排序的方法将所有数据元组按照Grouping Key进行排序,然后对排序文件进行一遍扫描,得出聚集查询结果。基于哈希的方法以Grouping Key作为键值将元组存入哈希表中,对映射到同一位置的数据元组进行聚集计算,当下海量数据上的聚集查询主要使用基于哈希的方法。两种方法在性能上都不能完全满足业内需求。

  基本的聚集查询算法在海量数据上会造成较大的时间开销。为了提高聚集查询效率,缩短查询语句反应时间,研究人员提出了一些新的方法用于提高聚集查询的效率。一些研究者提出了基于采样的近似聚集查询算法。通过对整个数据集按照一定的采样函数进行采样,在样本集上进行聚集运算得出近似聚集结果,减少查询执行时间。而由于在样本集上进行聚集会造成整体数据上概要信息的缺失,因此该方法只能得出非精确的查询结果。若采用在线聚集(Online Aggregation)方式通过在线的获得随机元组,对聚集查询结果进行实时的近似估计,则需要数据随机分布,在整个查询未结束时只能反馈出非精确结果。

  由于大数据涉及数据库技术从底层到顶层的一系列变革,不仅为各个领域发展带来了机遇,同时也带来了挑战。当下围绕大数据生态系统的业务模式正在形成,对大数据任务处理的实时性和多样性有着很高的要求,因此需要快速发展新技术,洞察整体产业的发展规律,为金融业分析研究整个市场环境提供技术支撑,才能更好地利用大数据创造价值。

二、快速聚集算法

   由于数据的海量性,传统的单机计算环境难以胜任海量数据处理和存储的任务。分布式环境拥有庞大的计算资源和较强的并行计算能力,是当前处理和存储海量数据的主要趋势。分布式环境中海量数据在各个数据节点中分区存储,每个分区称为一个数据分片,分片之间可以并行进行计算。

  由于海量数据并非孤立产生,相邻数据元组之间属性值存在相等的情况,如移动通讯信令数据中往往同一个人的通话数据会存储为相邻的数据元组,因此设计存储相邻数据元组相似性信息的辅助结构——位串数组,可以利用该辅助结构减少数据聚集查询时在元组扫描阶段的磁盘I/O开销,进而节省整个聚集查询语句的执行时间。

  1.位串数组结构

  假设表T中共有m个数据元组和k个数据分片,T中元组具有属性C1,C2,…,Cn。元组采用连续存储的策略平均分布在k个分片中,且在每个分片内按主键值递增的顺序存储,因此每个数据分片中包含个m/k个元组。对表T的每一个数据分片,我们在内存中构建大小为m/k的位串数组,数组中元素为长度为n的二进制位串。每个位串和分片中元组一一对应,分片中第j个元组对应数组中第j个位串。对于给定元组t,其属性Ci对应于相应位串第i位bi。位串的具体生成方式如下:

  (1)对每个数据分片中的第一个元组f,将其对应位串中每一位都设为0。

  (2)对每个数据分片中其他任意元组t,对i∈[1,n] 若元组t属性Ci的值与同一数据分片下前一个元组t’属性Ci的值相同,则其对应位串中bi=1;若不同则bi=0。

  每个数据分片有m/k个元组,因此对应的位串数组大小为(m/k)×(n/8)Kb,这个数据规模相对较小。例如假设表T元组数为10000000,具有两个数据分片,元组共有32个属性,则每个分片对应的位串数组仅有20Mb,完全可以存储内存进行维护,因此位串数组带来的额外存储开销完全在我们的承受范围内。通过对数据进行一遍扫描,便可完成位串数组的构建,下面以某省移动通讯信令数据为例,介绍对应的位串数组生成过程。

  给定移动通信信令数据表,属性vcCallingNumber表示主叫用户号码,属性vcCalledNumber表示被叫用户号码,属性intDuration表示通话时间,Rowkey为主键。该表包含两个数据分片,每个数据分片下包含6个元组。以分片1中主键为3的元组(称为元组3)为例,其同一分片下的前一个数据元组为主键为2的元组(称为元组2),元组3属性vcCallingNumber和属性vcCalledNumber的值与元组2对应的属性值相同,属性intDuration值不同,因此其对应的位串为110。整个数据表和两个分片对应的位串数组如图1所示。

图片1.jpg

  2.算法预处理阶段

  当所有位串构建完成后,将位串数组存储在对应的数据分片所在节点的内存中。对于每个聚集查询请求Q,首先对每个数据分片构建一个局部哈希表,其键值为Grouping Key。同时我们额外对每一个数据分片在内存中额外维护一个数据元组r,在每一个元组t处理结束后将r的各个属性值置为t的属性值,将r的主键置为t的主键,起到缓存作用。

  3.算法执行阶段

  对于每个数据分片,首先进行局部聚集。局部聚集需要将磁盘中的每个元组存储到对应的局部哈希表中,对数据分片中元组的处理方式如下。

  (1)对于分片中第一个数据元组f,需要将f从磁盘中读入内存,将f按grouping key存储该分片对应的局部哈希表,-并将元组r的各个属性值置为f的各个属性值,同时将元组r的主键置为f的主键。

  (2)对于分片中任意其他元组t,我们首先检查其对应的位串。对i∈[1,n]。若位串中位bi=l,说明该位对应的元组t的属性Ci的值与同一数据分片下前一个元组t’属性Ci的值相同。由于我们使用r缓存了t’的各个属性值,因此不必从磁盘中读取元组t属性Ci的值。若bi=0,则需要从磁盘中读取属性Ci的值。所以对于元组t,我们只需根据该元组的主键从磁盘中读取对应位串中位为0的属性值。而数据在分片中按照主键递增的顺序连续存储,因此当前r的主键值加1即为t的主键值。在读取元组t所需的属性值后,利用r补全元组t,将t存入哈希表并将r的属性值和主键更新为t的属性值和主键。

  在将元组t存入哈希表时,若哈希表中元组t映射位置上元素为空,则将元组t信息作为局部聚集结果存入相应位置。若映射位置上元素非空,则需要对表中元素和当前元组t按照聚集算子进行局部聚集,并将局部聚集结果存入相应位置。

  在所有数据分片的局部聚集操作完成后,构建一个全局哈希表,其键值为Grouping Key,并行扫描所有的局部哈希表,将其中元素存入全局啥希表。这里使用与局部哈希表一样的存入策略。最终所有元素全部存入全局哈希表后,全局哈希表中元素即为聚集查询结果。

  4.算法改进

  为了提高位串数组存储相似性的能力,对算法进行了进一步的改进。由于数据元组不仅仅与其前一个元组存在相似性,还可能与该元组之前的多个元组相关。因此将每个分片对应的位串数组个数由1个增加为h个,每个数据分片中的元组t对应h个二进制位串,分别存储该元组与前h个相邻元组的相似性信息,对于j∈[1,n]第j个位串记录前h个相邻元组中第1个元组和元组t的相似性信息。位串数组的具体生成方式不变。同时在查询阶段我们将内存中额外维护的缓存元组也扩充为h个,用以缓存元组的前h个元组各个属性值,可用滚动数组维护h个缓存元组。在处理元组t时,对其属性Ci检查该元组对应的h个位串,只要有一个位串中位bi=l,就不必从磁盘中读取Ci的值。

  显然,h的值越大位串数组所能够覆盖的相邻元组范围越大,从而保存的相似性信息就会越多。同时随着h的增大,会导致额外的存储和计算开销的增大,因此需要谨慎设计h的大小。

三、总结

  随着大数据渗透到了金融的各个领域,海量数据上聚集查询算法的设计与实现能够作为数据分析和挖掘的支撑与基石。通过分析现有的海量数据上聚集查询算法的特点与海量数据的特性,提出了海量数据上快速聚集算法,对海量数据的聚集查询任务提供有效支持。以此进一步支持研究人员快速得到数据集合间的概要信息,辅助金融领域业务人员进行决策,支撑行业发展。

  课题组成员:
  1.北京大学云计算关键技术与应用重点实验室李湛、雷凯
  2.北京大学信息科学技术学院王腾蛟教授
  3.中国农业银行科技与产品管理局系统管理处桑博亭

(文章来源:《金融电子化》杂志)

扫码即可手机
阅读转发此文

本文评论

相关文章