太阳城集团

  • / 10
  • 下载费用:30 金币  

一种基于动态索引结构的海量数据实时查询方法.pdf

摘要
申请专利号:

太阳城集团CN201310648180.X

申请日:

2013.12.04

公开号:

太阳城集团CN103678550A

公开日:

2014.03.26

当前法律状态:

授权

有效性:

有权

法律详情: 专利权的转移IPC(主分类):G06F 17/30登记生效日:20190314变更事项:专利权人变更前权利人:南京邮电大学变更后权利人:朗坤智慧科技股份有限公司变更事项:地址变更前权利人:210003 江苏省南京市鼓楼区新模范马路66号变更后权利人:210009 江苏省南京市鼓楼区山西路67号世贸中心大厦A808室|||授权|||实质审查的生效IPC(主分类):G06F 17/30申请日:20131204|||公开
IPC分类号: G06F17/30 主分类号: G06F17/30
申请人: 南京邮电大学
发明人: 陈丹伟; 庄俊
地址: 210003 江苏省南京市鼓楼区新模范马路66号
优先权: 2013.09.09 CN 201310408184.0
专利代理机构: 南京知识律师事务所 32207 代理人: 胡玲
PDF完整版下载: PDF下载
法律状态
申请(专利)号:

CN201310648180.X

授权太阳城集团号:

|||||||||

法律状态太阳城集团日:

太阳城集团2019.04.02|||2017.02.08|||2014.04.23|||2014.03.26

法律状态类型:

太阳城集团专利申请权、专利权的转移|||授权|||实质审查的生效|||公开

摘要

本发明公开一种基于动态索引结构(DC-Tree)的海量数据实时查询方法,该方法是将海量多维数据集降维,支持高空间效率低查询太阳城集团的方法,并支持分布式冗余存储,从而提升了传统分布式机制中数据分配的效率,适应大规模数据的处理;该方法包括:多维数据记录DR通过MasterNode中Z Curve映射函数fz,生成降维结果集S;MasterNode选定k个哈希函数,通过Bloom Filter对结果集S进行映射,生成节点集NN;更新数据记录DR,对节点集NN中每个元素实行动态构建;用户User查询MDS结果,通过步骤1、步骤2获得节点集NN,启用并行查询方法;用户User对节点集NN中所有访问节点的结果集进行聚合,得到最终查询结果Rset。

权利要求书

权利要求书
1.  一种基于动态索引结构的海量数据实时查询方法,其特征在于,所述方法包含如下步骤:
步骤1:多维数据记录DR通过MasterNode中Z Curve映射函数fz,生成降维结果集S;
步骤2:MasterNode选定k个哈希函数,通过Bloom Filter对结果集S进行映射,生成节点集NN;
步骤3:更新数据记录DR,对节点集NN中每个元素实行动态构建;
步骤4:用户User查询MDS结果,通过步骤1、步骤2获得节点集NN,启用并行查询方法;
步骤5:用户User对节点集NN中所有访问节点的结果集进行聚合,得到最终查询结果Rset。

2.  根据权利要求1所述的一种基于动态索引结构的海量数据实时查询方法,其特征在于:所述方法中建立了实时查询模型,将海量多维数据集降维。

3.  根据权利要求1所述的一种基于动态索引结构的海量数据实时查询方法,其特征在于:所述方法中建立了具有概念层次化结构的多维数据树。

4.  根据权利要求1所述的一种基于动态索引结构的海量数据实时查询方法,其特征在于,所述方法中包括:MDS(最小描述子集)分解、Z curve降维处理、Bloom Filter定位、DC-Tree索引及结果聚合。

5.  根据权利要求1所述的一种基于动态索引结构的海量数据实时查询方法,其特征在于:所述方法是基于动态索引结构。

说明书

说明书一种基于动态索引结构的海量数据实时查询方法
技术领域
本发明涉及计算机大数据查询技术领域,特别涉及一种基于动态索引结构的海量数据实时查询方法。
背景技术
随着互联网的飞速发展,社交网络、移动应用等日趋火热,我们看到网络太阳城集团的数据量在日益增多,大数据作为一种新兴数据概念而被定义,数据作为太阳城集团的载体,起着举足轻重的作用。数据的爆炸式增长使得我们进入了大规模数据分析的时代,其特点是计算强度大,并且要求大规模并发存储和处理能力。如何快速地处理海量数据,及时有效地从海量数据中提取有价值的太阳城集团,是急需解决的技术问题。
目前,大规模数据分析有2种主流技术:第一种是20世纪80年代开始,以Teradata、Gamma研究项目为代表的并行数据库逐步发展成熟,它是由一系列操作符组成,前一操作符的输出流是下个操作符的输入流,记录按流水线的方式依次经过这些操作符,具有较高的性能。第2种是以Google为首的基于Map Reduce和分布式文件系统GFS组成一种“无共享”的简单函数式编程的并行计算框架,支持其每天亿万次的搜索。Apache的Hadoop是一种Map Reduce的开源实现。但这些大规模数据处理技术难以满足实时性要求,更多的是针对离线数据的处理。Hadoop更像是一种ETL工具,两者的关系不是相互竞争而是互为补充。
另一方面,由Guttman提出的动态索引结构R-Tree及基于R-Tree的变种,其插入、查询等操作可以同时进行,并且支持多维的模型,在众多空间索引技术中的优势非常明显,但是其针对大规模数据处理时随着树高度的增加,其查询结点重叠度增加,造成查询效率下降较快。而本发明能够很好地解决上面的问题。
发明内容
本发明目的在于提供一种基于动态索引结构(DC-Tree)的大规模多维数据实时查询方法,该方法解决了大规模多维数据处理的滞后性问题,实现了在分布式架构体系上的海量数据实时查询模型。
本发明解决其技术问题所采用的技术方案是:本发明提出一种基于动态索引结构(DC-Tree)的海量数据实时查询方法,该方法包括如下步骤:
步骤1:多维数据记录DR通过MasterNode中Z Curve映射函数fz,生成降维结果集S;
步骤2:MasterNode选定k个哈希函数,通过Bloom Filter对结果集S进行映射,生成节 点集NN;
步骤3:更新数据记录DR,对节点集NN中每个元素实行动态构建;
步骤4:用户User查询MDS结果,通过步骤1、步骤2获得节点集NN,启用并行查询方法;
步骤5:用户User对节点集NN中所有访问节点的结果集进行聚合,得到最终查询结果Rset。
本发明是基于动态索引结构将海量多维数据集降维,支持高空间效率低查询太阳城集团的方法,并支持分布式冗余存储,从而提升了传统分布式机制中数据分配的效率,适应大规模数据的处理。本发明建立了具有概念层次化结构的多维数据树,打破传统的单一属性查询方法,使带有多维功能属性的数据集分成不同维度进行构建,大大降低了单一属性查询时的聚合工作量。
本发明通过将高维数据空间数据映射到一维空间,大大降低了数据管理节点的工作负担,支持数据存储节点的动态增加。同时设计了海量数据插入和查询方法,支持多维属性数据的动态构建,并支持海量数据查询的实时性效果,增加了查询过程访问锁机制,适应查询的并发性需求。
一、系统架构
图1给出海量数据实时查询系统的体系架构,该系统由以下四部分组成:数据管理节点(Master Node)、动态索引树(DC-Tree)、数据存储节点(Data Node)及用户(User)。MasterNode负责数据查询/更新的定位,主要运用降维和快速查询技术。DC-Tree主要是用于动态构建多维属性数据查询树,提供实时查询效果。DataNode负责具体数据的存储。用户(User)向MasterNode发送查询请求,MasterNode将对查询请求内容处理,确定所查询内容在部分DataNode上,并将这些符合要求的DataNode提交给用户。完成这个操作之后,用户将于MasterNode断开连接,并主动访问提交的DataNode进行查询。系统整体架构如下图1所示。
本发明的海量数据实时查询方案由以下四部分操作组成:MDS(最小描述子集)分解、Z curve降维处理、Bloom Filter定位、DC-Tree索引及结果聚合。
二、方法流程
1.MDS(最小描述子集)分解
MDS(最小描述子集)表现形式为(M1,...,Md),其中不妨设Mi={ai1,ai2,...,aik},其中1≤i≤d,aik∈Di,则此MDS(最小描述子集)对应的多维数据记录集为{(a11,a21,...,ad1),...,(a1k,a2k,...,adk)},记为MM。
2.Z curve降维处理
根据上述步骤1中所得结果集MM,运用Z Curve方法进行降维操作,设Z Curve映射函数为fz(p,m,n),其中p∈MM,m为Z Curve阶数,n为多维模型的维度数,不妨设映射函数fz返回值为yp。该映射函数计算过程伪代码如下:
(1)yp=0;
REPEAT
REPEAT
(2)yp=yp+2n(i-1)+j-1aji
UNTIL j≥n
UNTIL i≥m
(3)RETURN yp
由于n维m阶Z Curve的映射函数空间复杂度为O(n),所以上述结果需要长度为n的数组来存放结果集yp,不妨设此结果集为S。
3.Bloom Filter定位
根据上述步骤2中所得降维处理后的结果集S={y1,...,yn},再根据相关工作中对Bloom Filter的阐述,此时需要选择k个哈希函数HFi,其中1≤i≤k,由于Bloom Filter本身存在一定的错误率,为了能够减少这种正向性错误,本发明在构建哈希函数时运用了Knuth论证:两个哈希函数HF1和HF2通过下面的形式可以生成更多的哈希函数:
HFi=[HF1+HF2+f(i)]mod r
其中1≤i≤k,r为Bloom Filter数组长度,HF1和HF2是两个相互独立的哈希函数。当f(i)=0时,采用双哈希函数机制,否则就为扩展哈希函数机制,这样产生的哈希函数保持了正向性错误率不变,并且提高了系统的计算效率。
选定k个函数函数后,对集合S中数据进行映射,返回一个DataNode节点集,不妨设为NN。并将此集NN返回至用户。
4.DC-Tree索引及结果聚合
用户根据上述步骤3中所得集合NN,定位到所需进行索引的DataNode,DataNode采用 DC-Tree索引方法进行查找。在每个DataNode上进行查找后,会将索引结果发送到一个索引结果集中,不妨设为RSet,此时再对该索引结果集进行聚合,获得最终查询结果。
有益效果:
1、本发明提高了数据分配的效率,适应大规模数据的处理,降低了单一属性查询时的聚合工作量。
2、本发明实现了大规模数据高效并发处理和实时性功能。
附图说明
图1是本发明的系统架构图。
图2是本发明的动态插入方法流程图。
图3是本发明的并行查询方法流程图。
具体实施方式
下面通过结合说明书附图,进一步说明本发明的技术方案。
实施例1
如图2和图3所示,本发明提出一种基于动态索引结构(DC-Tree)的海量数据实时查询方法,该方法包括如下步骤:
步骤1:多维数据记录DR通过MasterNode中Z Curve映射函数fz,生成降维结果集S;
步骤2:MasterNode选定k个哈希函数,通过Bloom Filter对结果集S进行映射,生成节点集NN;
步骤3:更新数据记录DR,对节点集NN中每个元素实行动态构建;
步骤4:用户User查询MDS结果,通过步骤1、步骤2获得节点集NN,启用并行查询方法;
步骤5:用户User对节点集NN中所有访问节点的结果集进行聚合,得到最终查询结果Rset。
本发明是基于动态索引结构将海量多维数据集降维,支持高空间效率低查询太阳城集团的方法,并支持分布式冗余存储,从而提升了传统分布式机制中数据分配的效率,适应大规模数据的处理。本发明建立了具有概念层次化结构的多维数据树,打破传统的单一属性查询方法,使带有多维功能属性的数据集分成不同维度进行构建,大大降低了单一属性查询时的聚合工作量。
本发明的一个新的多维数据记录DR,通过MasterNode快速定位查询节点集NN,并动态添加到相应DC-Tree,用户User通过MDS查询节点集NN,聚合返回查询结果。
则其具体实施方式为:
(1)多维数据记录DR通过MasterNode中Z Curve映射函数fz,生成降维结果集S;
(2)MasterNode选定k个哈希函数,通过Bloom Filter对结果集S进行映射,生成节点集NN;
(3)更新数据记录DR,对节点集NN中每个元素实行动态构建;
动态插入:为根节点D申请加锁LOCK;更新目录结点的Measure值;如果DR仅仅包含在D的一个孩子的MDS中,那么令D置为这个目录孩子结点;如果DR包含在多个D的孩子的MDS中,那么找出这些孩子中包含最少数据结点的那个孩子,并将D置为这个目录孩子结点;如果DR不包含在D的任何一个孩子的MDS中,首先拷贝一份D,不妨设为D’,将DR添加到D的每一个孩子结点中,计算添加后的重叠值,选择重叠值最小的那个孩子结点,并将其设为D;将数据记录DR插入到D中,并更新D的Measure值;如果D的容纳空间已经达到最大,则调用分裂函数SPLIT,将D作为参数传递;更新D的父亲结点的Measure和MDS;令D指向D的父亲结点,如果D没有更新或者D不是根节点,则重新将数据记录DR插入到D中,并更新D的Measure值,继续执行,否则结束;为根节点D申请解锁UNLOCK;
(4)用户User查询MDS结果,通过步骤1、步骤2获得节点集NN,启用并行查询方法;
并行查询:对节点集NN中所有节点,如果该节点没有上锁,则并发访问所有在NN中节点;为根节点D申请加锁LOCK;对D的每一次孩子结点C,对C的任何一个维度,如果与查询MDS不在同一维度层次上,则将两者中较低维度层次转换为较高维度层次;如果C的_MDS包含在查询MDS中,则将该_MDS及其Measure Values加入到结果集中;如果C的_MDS和查询MDS有重叠但并不包含在查询MDS中,则将该孩子结点C设为D,递归调用并行查询函数PARALLEL QUERY,继续及NN中节点执行同样操作;如果C为叶子结点,则访问结束;为根节点D申请解锁UNLOCK;
(5)用户User对节点集NN中所有访问节点的结果集进行聚合,得到最终查询结果Rset;
(6)全过程结束。
实施例2
如图1所示,本发明给出海量数据实时查询系统的体系架构,该系统由以下四部分组成:数据管理节点(Master Node)、动态索引树(DC-Tree)、数据存储节点(Data Node)及用户(User)。MasterNode负责数据查询/更新的定位,主要运用降维和快速查询技术。DC-Tree主要是用于动态构建多维属性数据查询树,提供实时查询效果。DataNode负责具体数据的存储。用户(User)向MasterNode发送查询请求,MasterNode将对查询请求内容处理,确定所 查询内容在部分DataNode上,并将这些符合要求的DataNode提交给用户。完成这个操作之后,用户将于MasterNode断开连接,并主动访问提交的DataNode进行查询。
本发明的海量数据实时查询方法由以下四个操作部分组成,包括:MDS(最小描述子集)分解、Z curve降维处理、Bloom Filter定位、DC-Tree索引及结果聚合。

关 键 词:
一种 基于 动态 索引 结构 海量 数据 实时 查询 方法
  专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
太阳城集团本文
本文标题:一种基于动态索引结构的海量数据实时查询方法.pdf
链接地址:http://zh228.com/p-6180857.html
太阳城集团我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

copyright@ 2017-2018 zhuanlichaxun.net网站版权所有
经营许可证编号:粤ICP备17046363号-1 
 


收起
展开
葡京赌场|welcome document.write ('');