美章网 资料文库 基于HBase的时态信息索引策略范文

基于HBase的时态信息索引策略范文

时间:2022-09-23 03:55:55

基于HBase的时态信息索引策略

《广东工业大学学报》2014年第二期

1时态信息在HBase的存储模型

Hadoop是一个开源的云计算框架,向用户提供系统底层细节透明的分布式基础架构.Hadoop生态系统中的Commom、Avro、Chukwa、Hive、HBase等子项目提供了互补性服务或是核心层上提供了更高级的服务.HBase适于存储松散型的非结构化数据,即是介于映射(key/value)和关系型数据之间的数据.其表索引由行关键字、列关键字和时间戳组成,表中的数据可以有多个版本(通过时间戳区分),并且能动态地实现数据列族的添加.不同于RDBMS具有丰富的数据类型和存储方式,HBase只有简单的字符串类型,所有的用户所需的类型都额外自行处理获得,同时由于HBase的非事务性,是通过牺牲一些高级的查询能力以换取更好的在分布式环境下的性能,故不支持多表连接进行复杂的查询操作,也没有时态语义的约束.HBase向下提供了存储,以分布式文件系统(HDFS)为底层框架,向上提供了运算,能使用MapReduce计算模式来并行处理大规模数据.对于电子医疗时态信息数据集R=∑rk=1Rk(k=1,2,…,r)的存储,在HBase中进行数据模型的构建:将时态数据所描述的对象(患者)的根本特征作为主键,即KeyRow,可表示为病人的姓名或编号ID;列族是对事务属性的扩展性描述,能更详尽地描述事物所抽象出来的各种属性,HBase的灵活性可以实现对列族的自由添加.为了对临床医疗数据的时态特性进行描述,本文引入时态列族用于记录患者在就诊过程不同时段内病况信息的时态属性值,即Column:Temporal,它可以用时间点、时态区间或者时态集合作为时态信息的描述对象,本文基于具体医疗应用背景使用时态集合作为时态信息存储的基本单元;对于病人信息的非时态属性值的描述,可以通过添加列族Column:Notemporal实现,它可以用来描述患者的病症、年龄、既往病史、用药情况、主治医生等其他信息,但这些信息对于不同的患者来说并不具备高度的一致性,若无相关联的信息,则该列族中所对应的数据项可设置为空.为保证电子医疗数据的完整性,也可继续动态添加类似的列族.构建以时态集合为医疗时态数据存储单元的时态数据模型(THBase)如表1所示.医疗信息中时态属性值的表示方式由具体医疗背景决定.由于患者在诊疗活动中的时态信息往往由若干在时序上间断的信息构成,比如病人发烧时间,可能仅仅某些天若干时段高烧,又如某些流行性疾病如伤寒、癫痫病等通常表现出反复发作的特性.因此为了兼顾信息的语义分析处理,采用时态集合作为医疗信息的时态属性值的描述手段.时态集合是时间点和时态区间在时序上的叠加,相对于时间点和时态区间的单一表达性,它可根据对象在时态论域的多样性特征变化更为灵活和精确体现出其时态性,适于诊疗信息对象整个病理周期的全程记录,清晰明了,若将时态元素拆分通常不能满足正确性、完备性需要,往往会失去时态语义;另一方面通过合并时间点和时态区间这两种时态数据类型,在数据库中进行海量信息存储能够最大限度地压缩存储空间并减少数据冗余.

2时态集合的聚类策略

由于Hadoop的分布式特征,数据是按分块的形式存储在集群的各个节点上.HBase将逻辑上很大的一张数据表在存储实现时以一定的方式进行“切割”形成不同的区域,即时态信息存储表根据行被分成了多个HRegions,每个HRegions又包含一个较大的数据集.若以列族作为查询条件,只能根据行键从第一行数据开始查找,扫描全表直到查询到相关的数据为止,这样显然是十分低效的.对于海量数据的快速检索方法,目前的研究成果包括B树及其变形树的检索,哈希检索,分布式哈希表(DistributeHashTable,简称DHT)检索等.因此结合Hadoop体系特性,本文采用分布式哈希表作为海量时态信息的索引方式.由于THBase模型以时态集合作为存储对象,其数据结构较为复杂,直接在该类型的数据上构建索引难度较大.考虑到现阶段较为成熟的空间索引模式更适于海量非结构化数据的组织,因此,本文首先需将时态数据向空间数据转化,对以时态集合为存储对象的时态信息进行空间映射,构造二维空间上的时态数据区域集,在此基础上再作数据集划分、数据的聚类操作,得到若干层次的时态数据域,并以这些时态数据域作为各级索引表的主键.

2.1时态集合的空间映射在HBase中,对于任意一条电子医疗时态记录记录时间的终点,且Ps≤Pe.由于作为时态信息描述对象的时态集合是由若干时间点和时态区间构成,结构较为复杂,对于任意DRt,其维度(包含的时间点和时态区间的数目)并不恒定,若对时态属性进行索引构建,需简化其表示方法.借鉴空间索引的实现方式,将其映射到二维空间,再以空间数据划分方式实现聚类.定义1(时态数据区域)将时态属性值映射到二维空间所得到的二维空间区域.任意的时态数据Rf、IjRf是时态集合DRt任意一个时间点或时态区间,以(0,0)为原点,时态集合中各时态区间起始点所代表的时间轴为X轴、各时态区间终止点所代表的时间轴为Y轴,建立二维空间上的XY垂直坐标系.(Ⅰ)对于时态区间IjRf=[PRf,s,PRf,e],PRf,s所在为横坐标(X坐标),PRf,e所在为纵坐标(Y坐标).那么,时态区间IjRf在空间坐标系中则可以表示为时态数据区域S(IjRf),该区域是由X≥PRf,s、Y≤PRf,e以及Y≥X共同围成的区域构成.事实上,由于时态信息具有一定的粒度性,该区域包含若干独立的、离散的时间点,如图1所示.(Ⅱ)由于时间点可表示为起始时间与终止时间一致的时态区间,因此,时间点在二维空间上可表示为时态数据点.

2.2时态数据区域的划分策略在设计HBase海量时态数据索引结构时,数据或数据空间的划分是至关重要的环节,好的数据划分策略会提高数据库I/O吞吐性能及系统数据吞吐能力,从而提高整个系统的检索性能.在将THBase中所有的时态集合映射为时态数据区域集合S(t)后,如何对已空间化的时态数据区域进行数据组织?针对时态数据区域S(t)结构复杂、数据量大以及数据之间存在着空间拓扑关系等特点,本文在K-均值聚类算法的基础上,提出在分布式系统下的时态数据区域S(t)的数据划分方案如下。

3基于HBase多级哈希索引表的设计

在分布式集群存储系统中,数据的组织优化是提高存储系统性能的有效方法之一.而索引是存储系统重要的部分,它直接决定数据的存取效率,影响数据分析与应用效率.在HBase分布式存储结构中,对时态信息构建索引可以极大地提高对HBase中数据的访问速度,有效地避免对非主键的全表扫描所产生的巨大系统开销.同时由于HBase“一次写入多次读取”的特点,并不需要频繁进行表结构的更新和数据的添加、删除操作,因此为海量时态信息存储表建立索引是十分必要的.本文在分布式哈希表(DHT)的基础上,提出THBase模型下的多级索引表DHT算法(tDHT).设→D为THBase所存储的时态集合值域,D代表时态记录R的时态属性值。对于多级哈希索引表构建,本文提出的tDHT算法将THBase时态列族Column:Temporal的时态属性值进行聚类,并以此作为行键,即KeyRow,并以THBase的KeyRow作为列族重新构造数据表.对于THBase时态信息的检索,索引结构可实现根据列值快速地定位相关数据所在的行,由此构成THBase的一级索引,再以一级索引表为原表,按照上述方式构建多级索引表.这样,各级HBase索引表除了以上一级的时态数据子区域作为KeyRow之外,仅需要再构建时态索引列族Column:TIndex作为新的时态索引列族即可.如此,索引表结构以及所包含的信息比原表要精简得多,访问索引表所消耗的时间也较少.

3.1一级索引表结构的设计根据THBase模型以及HBase存储结构的特点,首先构建HBase的一级时态索引结构TIndex-1.以时态数据区域聚类生成的一级时态子区域r(1)i(i=1,2,…,K)为KeyRow,即TIndex1的主键,同时建立时态索引列族Column:Tindex,以THBase的主键KeyRow(患者编号)作为该列族的(Key,Value)取值.则构建的HBase一级索引表目录如表2所示定义2(时态检索域)将用户的时态检索请求(通常是时态区间或时态集合)按照上文所述的方式映射为时态数据域,称为时态检索域.索引表与原表通过原表的KeyRow(患者编号)建立映射关系.用户进行时态检索时,将时态检索域分别与一级索引表的所有RowKey(一级时态子区域)进行运算:(Ⅰ)若两者存在交集,则读取列族TIndex1的值,获取此值后以该值作为HBase时态信息存储表(THBase)的KeyRow,读取相应的时态信息;(Ⅱ)若不存在交集,则不再读取该RowKey对应的列族TIndex1的值,时态检索域与索引表的下一行RowKey值进行比较.

3.2多级索引表结构的设计采用多级哈希表索引可以进一步提升检索性能.根据本文所提出的(tDHT)算法。当用户提交涉及时态信息的查询请求时,首先进入第N级的哈希索引表中快速检索,根据时态检索域与N级索引表KeyRow主键r(n)i的空间重叠性,若存在重叠区域,则扫描时态索引列族Column:TIndex,继续判断两者是否存在交集,然后根据(Key,Value)中Key所对应的Value值进入N-1级哈希索引表,由此通过上一级索引表的时态索引列族与下一级索引表主键建立哈希映射关系,以时态检索域与各级时态数据子区域r(n)i进行各层索引表的关联条件判断,以此类推直到获取用户需数据的地址信息并定位到数据为止.

4性能测试

搭建测试平台进行多级分布式哈希表索引结构的性能验证.本文采用HBase0941和Hadoop0210进行实验,将其部署在5个物理计算机节点上,搭建Hadoop集群,其中1个节点作为Master节点,其余4个作为Slave节点.每台PC机的系统参数配置为:CPU(Inter(R)Core(TM)i3M350@227GHz)、RAM(400GB)和硬盘(500GB).为了获取更好的稳定性,实验在Linux系统(ubuntu1104desktopi386)下进行,使用openssh实现系统内节点无密码互访.本文采用的是以时态集合方式进行重构的电子医疗时态数据,将其写入到HBase中作为测试数据,并进一步对设计的不同N值的多级索引表tDHT算法与HBase按主键扫描方法进行查询时间的性能比较.实验中用来进行查找时间对比的基础时态数据量分别为10万、1000万、2000万和4000万,由于HBase只能根据RowKey进行查询,不支持对非主键(如列族)条件查询.在获取所要查询的时态数据主键或是按照某些列族的属性取值一致性的前提下,抽取、过滤所得时态列族的时态属性值,通过并、交等操作完成Map/Reduce并行编程模式下的时态集合关系代数演算,实现对时态数据的查找.在不构建索引以及构建不同级数的分布式哈希索引表索引(N=3,5)的时态数据检索时间如表3所示.为了更直观地展示实验结果,绘制时态数据查找的时间对比折线如图3所示.由表3、图3的时态检索的时间对比分析可知,相对于全表的条件查找,使用HBase进行存储的分布式哈希表索引能较大程度地改善系统对于时态信息查询的性能,特别是当时态数据量达到千万级以上时,构建索引在查找时具有非常巨大性能优势,能极大地缩短检索所需时间;而索引级数N的取值不同,也在一定程度上影响时态检索的性能,当数据量不大时,索引级数越高,各级索引表的数据量则较小,多表映射所造成的时间损耗抵消了部分由于更精细的数据集划分带来的优势,N值的大小对索引性能的提升不够明显,但当存储的时态数据量加大,各级索引表长度急剧增长时,索引结构tDHT(N=5)相对于tDHT(N=3)在进行时态信息搜索时所需的查询时间几乎呈几何递减趋势,当数据量达到千万级以上时差异性更为突出.由此可得,构建分布式哈希索引能较大程度地改善时态检索性能。

5结语

时态属性,作为刻画事物的一个重要维度,对时态信息检索、时态知识推理、时态数据挖掘等研究领域均有深远的影响.针对海量的非结构化电子医疗时态数据,以时态集合作为基本的时态数据存储结构,本文提出使用Hadoop平台下分布式存储系统HBase进行数据存取,并在此基础上构建多级分布式哈希表以提升对海量时态信息检索的性能.鉴于以时态集合为基本存储元素的时态信息结构复杂,故借鉴对空间数据的处理方法将时态信息映射为空间数据区域,进行数据集的聚类以及划分等数据重构和组织操作,构建N级时态数据子区域,并设计基于HBase的多级分布式哈希表索引(tDHT)算法,以各级时态子区域作为对应索引表的主键,并通过时态索引列族建立上、下级索引表主键的映射关系,实现N级索引目录与原时态信息存储表的关联,完成多级分布式哈希表的构造.通过测试验证了所构建的索引结构在Hadoop平台下对于海量时态信息进行检索的有效性.需要指出的是,本文是在单一时间粒度的前提下开展的确定性时态信息的研究,针对的是公历系统,显然这是较为理想的时态数据处理模型.然而在现实生活中涉及的多粒度、模糊的、不确定的时态信息,不仅需要进行不同时态粒层的映射转换,还需额外地增加时态因子以描述时态信息的不确定性程度,这还需要另行研究.另外,针对不同的时态数据集,索引级数N的取值大小与性能提升程度的对应关系仍然需要进一步研究.

作者:陈磊封朝永单位:广东工业大学计算机学院

被举报文档标题:基于HBase的时态信息索引策略

举报类型:

非法(文档涉及政治、宗教、色情或其他违反国家法律法规的内容)

侵权

其他

验证码:

点击换图

举报理由:
   (必填)