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

杨佐希 等:基于时序分区的时态索引与查询 3523

滑化处理可以控制 VTe 对于整体映射结果的影响,即当 VTs 不同时,对于时态降维结果的大小判断几乎不产生影
响(此时的大小由 VTs 的大小决定).当 VTs 相同时,又可以根据 VTe 的大小进行时态降维结果大小的判断.
例 1:下面给出有关于时态降维的例子.给定无序的 VT 点集 I={[1,8],[2,6],[3,6],[7,8],[2,5],[4,9],[5,8]},分别用
a,b,c,d,e,f,g 表示.根据给出的函数 ƒ,得到的时序排序结果为 a<b<e<c<f<g<d.
综上所述,通过时态降维的处理方式,将时态数据特有的 VT 属性转换成一维相点,进行自上而下,自左而右
的排序.可以看出,通过将二维时间区间转化为具有一定顺序排列的一维操作,形成了多个不同分分区层.在时态
数据中具有大量与目标数据“无关”的时态点,因此在进行索引查找的时候,通过分区层过滤掉大量的“无关节
点”,再判断剩余时态点是否满足查询条件,可以很好地节省查询处理的时间开销.在整个时序分区过程中,算法
的平均时间复杂度为 O(nlogn),平均的空间复杂度也为 O(nlogn).
2.2 时态拟序结构

定义 2(时态拟序关系(temporal quasi-ordering relation)). 若 R 是集合 Г 中时态数据集 E 满足自反性和传
递性的关系,则称 R 是 E 上的一个拟序.下面给出相关的拟序关系.其中,
• 自反性:若׊TD 1 ∈E,满 VT(TD 1 )كVT(TD 1 ).
• 传递性:׊TD 1 ∈E,׊TD 2 ∈E,׊TD 3 ∈E,若 VT(TD 1 )كVT(TD 2 ),且 VT(TD 2 )كVT(TD 3 ),则有 VT(TD 1 )كVT(TD 3 ).
定义 3(col 集合). 对于׊Y 0 ∈H(Г),有 col(Y 0 )表示 H(Г)中 VTs(P)=VTs(P 0 )的点 P 集合.
本文提出了时态索引技术是的线序划分基础上进行的,该方法引入了“拟序关系”概念,这是一种与传统的
“代数”模式不同的关系模式.通过将 H(PГ)上的时态数据按照拟序关系进行划分,进而将数据按照某种特定的结
构进行组织构建,从而使得进行时态数据查询检索时,由该特定结构的良好过滤性而达到高效的检索需求.因此,
我们需要对相应的线序构造算法进行探讨.其中最主要的思想是:为了在每个时序分区的时态数据中,TPindex
从 H(PГ)“最左上方”的点开始,通过同列优先,而后从左到右的原则进行构建,直到所有的元素点进入相应的线
序中.该算法伪代码如算法 1 所示.
算法 1. H(PГ)“下右优先”线序划分构建算法.
输入:H(PГ).
输出:L 1 ,L 2 ,...,L n .
1. u(i, j)=the “top left” point, P=u(i,j), L k ={P}, k=1;
2. for m=i to j do
3. traverse the H(PГ) the col(i), while the K(i,m)=traverse point;
4. L k .add(K(i,m)), P=K(i,m);
5. if ׌N(i+1,m)∈H(PГ) and VTe(N)≤VTe(K) then
6. L k .add(N(i+1,m)); goto Step 2;
7. else i++;
8. end if
9. if i==m then
10. goto Step 11;
11. else goto Step 2;
12. end if
13. end for
14. return L k
通过上述算法,按照“下优先”和“右优先”的原则,经过有限次迭达之后,我们得到若干条完整的“路径”(在下
文另有详细说明).我们在不妨设 g=max{VTs(u)|u∈Г},h=max{VTe(u)|u∈Г},则算法 1 的时间复杂度为(g×h)/2.
例 2:假设在某一个时序分区内的数据为 H(PГ)={[1,9],[1,7],[1,6],[1,5],[2,8],[2,7],[2,5],[2,3],[2,2],[3,8],[3,7],
[3,4],[3,2],[4,8],[4,7],[4,4],[4,2],[5,10],[5,9],[5,7],[5,5],[6,10],[7,10],[7,9],[7,8],[7,7],[7,6]},则根据算法 1 可以得到