Page 207 - 《软件学报》2020年第11期

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

用于海量数据,同时可以结合并行化优化方案,具有外存存储模式的基于时序分区的时态索引技术 TPindex.通
过特有的时序分区技术,可以使 TPindex 适用于海量数据的时态索引创建和查询.结合并行化的技术,可以在“拟
序关系”的顺序结构中实现高效的时态检索.最后基于外存的存储模式,使得在减少时态索引对于运行机器的过
高需求的同时又能充分的发挥现代化计算机体系结构的优势,具有一定的适用性.

2 TPindex 索引

时态数据(temporal data,简称 TD)可以定义为一个二元组 TD=<RD,VT>,其中 RD 表示常规数据,VT 表示一个
有效时间期间标签.VT=[VTs,VTe),其中 VTs,VTe 分别表示 VT 的开始时间与终止时间(VTs≤VTe).TD 有效时间记
为 VT(TD).如果将有效时间映射在二维平面上,那么不妨将 VT=[VTs,VTe)可以看作是二维平面(其中横坐标是
VTs,纵坐标是 VTe)的坐标点(VTs,VTe),则实现时间期间集 Г 和平面 VTs-VTe 点集 H(Г)一一对应.在本文中,对于 Г
和 H(PГ),不做细致区分.
2.1 时序分区
定义 1(时序分区(timing partition)). 对于平面集 H(Г)上满足拟序关系的数据集 E,按照某种特定方式进行
平面分区的操作,称为时序分区.Г 经过时序划分之后,得到若干个分区平面集 H(PГ),其中 H i PГ)表示第 i 个分区
平面.同上,在本文中,对于 H(PГ)与 PГ 不做详细区分.
事实上,在时态查询的操作过程中,满足查询条件的时态数据相较于整体的时态数据比例较小,存在着大量
的“无关”数据,尤其是在海量数据的情况下,如果将数据全部读取再进行查询比较,其付出代价将会过于昂贵.因
此,在进行时态查询操作之前,将大量的“无关”数据过滤,可以极大地减少中间查询比较过程的工作量,提高时态
查询操作的效率.数据分区 [29−31] 作为海量数据预处理策略的一种,在缓解内存压力,提高索引效率等方面有着较
好的性能提升.通过数据分区,使得数据能够有规则的“缩减”和尽可能的分布均匀.针对时态数据独特的属性组
成,我们提出了一种基于时态降维的自上而下,自左而右的时序分区方法.在时序分区中,我们采用随机采样的方
法.不妨设采样阈值为α,数据总量为 S,综合考虑时态数据总量的稀疏程度与离散化程度,我们给出了公式(1)用
以计算采样数量 D,公式(2)用以计算时序分区数量.
D = S α× (1)
σ
2 log(1 λ+
k =+ e ) (2)
其中,k 表示分区的数量(向下取整的正整数),λ 代表内存消耗系数(0≤λ≤1),σ表示时态数据的膨胀系数(0≤σ),
用以衡量时态数据的稀疏性与离散化程度.时态数据分布范围越广、越密集,说明膨胀系数越大.例如,给定时态
数据集 H 1 (Г)={[1,10],[1,9],[1,8],[1,7],[1,6],[1,5],[1,4],[1,3],[1,2],[1,1]},H 2 (Г)={[1,10],[1,9],[1,6],[1,1]},可以看出,
虽然 H 1 (Г)和 H 2 (Г)的数据分布范围都是由[1,10]到[1,1],但是 H 1 (Г)的数据相对于 H 2 (Г)而言更稠密,因此在进行
时序分区时,可以认为需要划分更多的时序分区,即相应的膨胀系数也会更大.由公式(2)可以得到,索引默认的最
小时序分区为 2(时序分区等于 1 时没有意义).通过上述公式计算的分区数量可以保证每个分区的数据加索引
的体积不超过数据总量.
在确定分区数 k 之后,将随机抽取的样本按照自上而下、自左而右的时序排列并找出 k–1 个分段点.首先,
根据采样的阈值大小得到相应的样本数据.针对时态数据特殊的时间属性 VT,本文通过时态降维的方法,通过映
射函数 ƒ 将二维平面上的任意 VT 区间转换成一维数据集 N.最后将 N 通过快速排序递归算法查找到 k–1 个分
段点.本文给出了时态降维映射函数如公式(3)所示.
⎛ η VTs ⎞
⎜ 10 ⎟
f = e ⎝ M ⎠ − VTe (3)
M
其中,η 表示 VTs 的最大位数,M 表示所有时态数据中“有效时间”元组里最大的 VTe(即所有数据中处于最后一个
元组中的 VTe).在进行时态降维过程中,主要考虑两个问题:当 VTs 不同时,VTs 越大,时态降维得到的结果越大;当
VTs 相同时,VTe 越大,映射的时态降维结果越小.通过上述公式,可以很好地区分不同时态点的映射位置,M 的平