4.2.2 基于内存模型的空间近似查询
单要素的近似查询处理方法解决了针对单条地理要素的空间条件及约束条件的查询处理,而现实中地理空间数据集是众多要素的集合。当针对地理空间数据集进行空间近似查询时,需要在空间索引的基础上同时考虑每个要素中顶点误差权值的分布以确定在查询过程的搜索策略。
1.要素集的近似查询
在进行要素集的近似查询时,可以将单个要素的近似查询进行扩展,将所有要素形成的层次结构的根节点作为一个代表整体数据集的虚拟节点,然后执行加权广度遍历。由于顶点层次结构的剪枝结果是二叉树节点集合子集的生成树,因此,将顶点子集的生成树按中序遍历的方式进行输出,可将层次结构还原为顶点序列,用于表示空间要素的几何部分。
给定空间数据集D,依据层次化方法构建生成的顶点层次结构集合定义为F＝{T L,T R},其中T L＝{T L i}表示所有线对象生成的顶点层次结构的集合,T R＝{T R i}表示所有组合对象所生成的顶点层次结构的集合。本节以时间约束为限制条件,对集合F进行时间约束的近似查询,设置时间阈值T,在给定时间内进行对象结果集的近似,同时返回近似查询所产生的误差。
表4-7 面向要素集的时间约束的近似查询算法
(https://www.daowen.com)
2.要素集的空间近似查询
空间近似查询是在近似查询条件的基础上增加了空间条件,是近似查询与空间条件的联合处理。当仅考虑空间条件的查询时,通常使用空间索引进行处理,如四叉树、R树、R+树等,并根据实际需要和数据本身的特性选择索引结构。对于数据分布较为均匀且数据所在的空间范围较大时,一般采用四叉树索引,对于数据分布不均匀且数据范围分布较小时,一般采用R树索引。
在进行空间近似查询时,需要同时考虑空间条件与约束条件(如时间约束、误差约束)。需要使用两个条件对数据进行预选,通过建立一个多维的空间索引以实现不同维度的查询条件的联合剪枝,预选操作可以避免后期复杂的空间连接处理。将顶点误差与顶点的空间位置进行联合索引,相当于在定义顶点的空间中增加一个新的维度,即误差维度。在顾及误差的多维索引结构中,顶点即根据空间范围维度分片,同时也根据误差维度进行分层。
本书采用顾及误差的四叉树索引结构进行带误差的顶点的索引。在顾及误差的四叉树索引结构中,任意一个树节点都能连接顶点。单个树节点连接的顶点个数上限制设为m。对任意树节点而言,该节点所对应的空间范围内的所有顶点按误差值进行降序排列,若顶点数量大于m,则将top m个顶点存储于该节点内,并建立该节点的四个子节点,将该范围内未纳入树节点的顶点进行分配索引。
在顾及误差的四叉树索引结构中,将同时根据要素间的拓扑关系来后期调整各顶点的误差值,以保证查询结果的拓扑一致性。
