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

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

42. end if
43. end if
44. Put all the points from the start point to the midpoint of PLOB into R
在上述二分优化查询算法中,由于 PLOB 具有独特的拟序关系,因此通过二分查找可以实现内部线序结构查找
的高效检索效率.对于查询结果,若 PLOB 中包含查询窗口 Q,则该 PLOB 上所有元素都视为查询结果.因此,通过二
分优化查找找到 PLOB 上最后一个包含查询窗口 Q 的元素 M,若存在这样的点,则从 PLOB 的第 1 个元素到元素
M 均为查询结果.设 n 为每个 PLOB 分枝节点的个数,则 n=min–max+1,且算法 2 时间复杂度也为 O(logn).
根据 PLOB 的拟序关系可知 VTs 的单增性与 VTe 的单减特性,因此在下面两组情况下,使用二分优化查找时,
只在始点序列或只在终点序列中做比较即可,减少了结束有效时间序列的比较次数,实现了更加高效的检索
时间.
(1) 当 VTs(Q)<PLs mid 且 VTe(Q)≤PLe mid ,即查询窗口 Q 的开始有效时间小于中点的开始时间且 Q 的结束
时间小于或等于中点的结束时间.
(2) 当 VTs(Q)≥PLs mid 且 VTe(Q)>PLe mid ,即查询窗口 Q 的开始有效时间大于或等于中点的开始时间且 Q
的结束时间大于中点的结束时间.
例 3:假设有查询窗口 Q=[3,4],PLOB={[1,9],[1,7],[1,6],[1,5],[2,5],[2,3],[2,2],[3,2],[4,2]},则由算法 2 可得,算
法初始的 max=[1,9],mid=[2,5],min=[4,2],序列数据中的 PLs 集合为{1,1,1,1,2,2,2,3,4},PLe 集合为{9,7,6,5,5,
3,2,2,2}.观察查询窗口 Q 与 PLs 和 PLe 的关系,可以看出∀τ∈PLs,都满足 VTs(Q)≥τ.因此,对于 VTs 来说,无论
PLs mid 位于哪里,都满足查询窗口的检索要求.此时,只需要对 PLe 集合进行考虑即可.在 PLe 集合中,初始的
PLe mid =5,此时满足查询要求,即此时的查询结果集合 R1={[1,9],[1,7],[1,6],[1,5],[2,5]}.在进行第 2 次二分查找时,
此时 max=[2,3],mid=[2,2],min=[4,2],PLe2 集合为{3,2,2,2}.对于∀ω∈PLe2,都满足 VTe(Q)>ω,即在序列集合
{[2,3],[2,2],[3,2],[4,2]}中,都不满足包含 Q 的查询要求,此时查询结果集合 R2=∅.算法执行完毕,综合两次查询结
果,可以得到最终的查询结果集合为 R=R1∪R2={[1,9],[1,7],[1,6],[1,5],[2,5]}.通过上述说明,可以看出,结合二分
查询算法与线序分枝结构的性质,可以达到高效的时态数据检索效率.
3.2 基于PLOB的多线程查询
计算机硬件的不断发展也为时态索引的性能带来了新的性能提升空间.其中,并行化计算技术已经趋向于
成熟,它可以通过多核处理器的强大计算能力和更大的存储资源来为海量数据进行高效的处理,很好地提高现
代化硬件资源的利用率.因此,研究海量数据下如何结合现代化硬件的优势,带来索引性能的提升,是索引在进行
构建时需要考虑的问题.为了充分地调用现代化计算机硬件的体系结构资源,利用多核处理器的强大计算能力
及存储资源来解决大规模历史数据问题,在使用 TPindex 索引进行时态查询时,可以结合多线程技术并行化地处
理用户的查询.同时,TPindex 特有的上层“分区层”可以很好地结合并行处理机制,即每个分区可以有若干个线
程,而这些线程可以分配到不同的“块”进行时态操作的处理.因此可以利用多线程技术并行处理多个分区的时
态操作或者针对单个的分区分配若干个线程进行并行处理.
给定时态数据集 H(Г),我们不妨设在该时态平面上建立 n 个 TPindex 分区时态索引结构,每个分区中包含若
干个 PLOP,而每个 PLOP 又有若干个 PLOB.现有查询窗口 Q,t 个线程,每个分区将会根据线程个数,自动分配线
程处理的线序分枝块,保证块内有序,直至调用完分区内的所有线程.进而,当运行到每个线序分枝块的具体查询
时,使用上面提出来的基于 PLOB 内部二分优化查询算法,得到每一块的查询结果.最后把每个分区中的所有块
的查询结果合并到一起,就是我们的所需要的查询结果集.基于 PLOB 的多线程查询模式如图 3 所示.