基于时序分区的时态索引与查询-杨佐希，汤娜，汤庸，潘明明，李丁丁，叶小平.pdf

上善若水

350

21页

0次

2022-05-24

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software,2020,31(11):3519−3539 [doi: 10.13328/j.cnki.jos.005826] http://www.jos.org.cn

基于时序分区的时态索引与查询

∗

杨佐希

汤

娜

汤

庸

潘明明

李丁丁

叶小平

(华南师范大学计算机学院,广东广州 510631)

通讯作者: 汤庸, E-mail:

ytang@m.scnu.edu.cn, http://www.scholat.com/ytang

摘要: 时态索引作为一种高效管理和检索时态数据的有效手段,一直是时态数据领域的研究热点.提出了一种

基于时序分区的时态索引技术 TPindex.首先将海量时态数据的时态属性映射到二维平面上,对平面上的“有效时

间”点进行采样处理,通过使用自上而下,自左而右的时序分区方法将平面划分成若干个均匀的区域.其次,使用基于

拟序关系的线序划分算法对每个分区中的数据构建数据结构,并建立基于“有效时间戳”的全区索引,实现“一次一

集合”的数据查询操作.再次,还提出了使用分文件存储线序索引的模式将分区线序索引磁盘化,同时可以结合多线

程技术并行处理数据,充分利用现代化硬件资源以满足海量数据下的高性能需求,提高索引性能.另一方面,我们还

研究了海量时态数据下 TPindex 的增量式更新操作.最后,设计相应的仿真实验,通过与现有的代表性工作进行对比

评估,验证了所提出方法的有效性和实用价值.

关键词: 时态索引;时序分区;拟序关系;海量数据;并行化

中图法分类号: TP311

中文引用格式: 杨佐希, 汤娜, 汤庸, 潘明明, 李丁丁, 叶小平.基于时序分区的时态索引与查询. 软件学报,2020,31(11):

3519−3539. http://www.jos.org.cn/1000-9825/5826.htm

英文引用格式: Yang ZX, Tang N, Tang Y, Pan MM, Li DD, Ye XP. Temporal index and query based on timing partition. Ruan

Jian Xue Bao/Journal of Software, 2020,31(11):3519−3539 (in Chinese). http://www.jos.org.cn/1000-9825/5826.htm

Temporal Index a nd Qu ery Base d o n Timing Partition

YANG Zuo-Xi, TANG Na, TANG Yong, PAN Ming-Ming, LI Ding-Ding, YE Xiao-Ping

(School of Computer Science, South China Normal University, Guangzhou 510631, China)

Abstra ct : Temporal index is one of key methods for temporal data managements and retrieval, which has been a hotspot in the field of

temporal data. This paper presents a temporal index technique TPindex which is based on a temporal timing partition method. Firstly, the

temporal attributes of massive amount of temporal data is mapped to a two-dimensional plane and the “Valid Time” points in this plane

are sampled for timing partition. A “form up to down and form left to right” timing partition method is used to divide the plane into

several balanced temporal areas and whole-partition index would be established at the same time. Once the steps above are completed,

temporal data can be dynamically indexed by its querying schema of “one time, one set”. Secondly, the TPindex would build data

structures through using “linear order partition” algorithm based on quasi-order relation for the data in each temporal area. Besides, a

“Separated Files Model Index” based on disks and multi-threading parallel process technique that can be combined are proposed to make

full use of modern hardware resources to meet the high performance needs under high-volume data, leading to better performance with

index. On the other hand, the incremental updating algorithm was also studied. Finally, the corresponding simulation experiments are

designed to compare with the current representative work to verify the feasibility and validity of the proposed algorithm.

∗ 基金项目: 国家自然科学基金(61772211, U181120009); 广州市产学研协同创新重大专项(201704020203); 广东省应用型科技

研发专项(2016B010124008)

Foundation item: National Natural Science Foundation of China (61772211, U181120009); Major Project of Industry-university-

research Collaborative Innovation of Guangzhou Municipality (201704020203); Special Fund for Applied Technology Research and

Development of Guangdong Province (2016B010124008)

收稿时间: 2018-09-05; 修改时间: 2019-01-07; 采用时间: 2019-02-22

3520

Journal of Software 软件学报 Vol.31, No.11, November 2020

Key words: temporal index; timing partition; quasi-order relation; high-volume data; parallelize

时间和空间是客观事物存在和发展的基本形式,所有的信息都具有相应的时态属性

[1]

.随着互联网信息技

术的高速发展,全球的信息呈现出爆炸式增长,海量的历史数据被存储供企业进行查询和分析,这些数据与时间

的联系十分密切.因此,如何对时态数据进行高效地存储与管理是时态数据库领域研究的热点.时态数据的存储

与管理要解决的其中一项关键技术就是时态索引

[2]

的构建.

针对时态索引的构建问题,研究人员提出了多种解决方案.自 20 世纪 90 年代以来,传统的时态索引以时态

数据模型

[3]

为理论基础(该模型主要包括“数据本体”和“时态信息”),一般通过结合 B+-tree(比如 MAP21

[4]

)或

R-tree(比如 4R-tree

[5]

和 GR-tree

[6]

)等技术对时态数据进行处理

[7,8]

.根据不同的时态数据模型,时态索引的处理有

3 种处理方式:将“数据本体”和“时态信息”依次处理

[4,5,9,10]

;将“时态信息”处理归结到非时态部分,对时态数据和

非时态数据统一进行处理

[11−13]

;将“数据本体”与“时态信息”协同处理

[14−16]

传统的时态索引能够较好地适用于小规模数据的时态需求,然而在面对海量数据时,由于其数据类型复杂,

传统的时态索引结构存在冗余、空间开销过大、更新维护成本过高、难以支持复杂的时态查询以及复杂查询

效率低等问题因此,研究一种适用海量数据的时态索引显得很有必要.

另外一方面,支持并行、多核和大内存等的现代化硬件使用非常普遍,多核处理器已经是市场上的主流配

置.传统基于单线程的时态索引显然不能很好地利用目前计算机体系结构的优势.因此,研究如何将基于多线程

的并行化技术应用到时态索引,提出可并行化的时态索引方案,可以为时态数据的检索带来性能的提升.在这方

面,文献[17]提出了一种基于内存的索引 Timeline,结合可并行化的现代化硬件,其优化的核心主要在于减少 CPU

的计算时间.但是其对机器性能需求过高,缺乏普遍适用性.而结合多线程的并行化技术,基于外存的时态索引仍

然是一种有价值的解决方案,其优化的核心在于增加查询数据的命中率,减少 I/O.

因此,本文提出了一种基于时序分区的时态索引技术 TPindex.该索引通过时序分区和线序划分的方法将海

量的时态数据分为分区层和索引层两个部分.在用户进行时态数据查询的时候,首先通过分区层快速地定位到

目标数据对应的时序分区中,然后再通过相应时序分区中顺序结构的索引层进行目标数据的筛选,实现“一次一

顺序序列”的高效据检索方式.本文的贡献如下:

(1) 提出了一种基于时序分区的时态索引方案,适用于海量数据存储与管理的时态索引 Tpindex.

(2) 在 TPindex 的基础上了,设计了一种基于多线程技术的并行化优化方案.同时设计分文件存储线序索引

的模式将时序分区的线序索引磁盘化,减少内存中的存储压力,将时态索引外存化.

(3) 讨论了基于 PLOB 的时态数据增量式更新机制,实现了对大规模历史数据的有效动态管理.

(4)

通过多组仿真实验,实验结果表明,在海量数据的情况下,本文提出的 TPindex 索引具有一定的有效性和

实用性.

本文第 1 节介绍相关的研究工作.第 2 节给出 TPindex 索引构建的详细步骤.第 3 节描述 TPindex 索引的多

种查询模式.第 4 节讨论 TPindex 索引的动态增量式更新机制.第 5 节通过多个仿真实验进一步验证 TPindex 的

有效性与实用性.第 6 节总结全文,并提出未来的工作展望.

1 相关研究

随着信息技术的高速发展,全球的信息量正在以指数级的速度增加,其增长速度已经超过摩尔定律

[18]

.现实

中的信息几乎都显示或隐式地包含时间特征,天然的具备时态属性.海量的历史数据被存储和管理,是企业分析

和决策的重要资料.这些时态数据可以看成是由“数据本体”和“时间标签”两部分组成,所以在某种程度上时态

数据存储和管理也可以看作是常规数据存储和管理的拓展.但是在传统的关系型数据库中,数据的时间属性通

常不是显式的,只保留数据的当前状态,相当于一种“快照数据”.但是当数据发生变化的时候,常规数据库会通过

覆盖原有的数据来实现数据的更新,这样就使得历史数据被“抹除”掉而导致出现历史数据丢失的问题.虽然常

规的数据库也能够存储历史数据,但是这样会导致时态数据的完整性被打破,难以重建对象数据的历史状态、

of 21

免费下载

软件学报计算机技术

关注

评论