7.2.1　总体框架

图7-1为本书中空间近似查询的总体框架,可以看出,空间近似查询的总体框架包括三个步骤,基于分布式内存计算的预处理、近似查询和可视化。在分布式内存计算环境下,将原始数据通过层次结构模型构建顶点层次结构;然后,通过加权广度优先遍历实现顾及多种约束条件的空间近似查询;最后基于空间近似查询引擎实现查询结果的可视化。

图7-1　空间近似查询的总体框架(https://www.daowen.com)

数据预处理阶段中主要的计算量来自递归划分集合中对于误差的计算。误差的具体计算方法依赖于误差定义,但总体上相当于空间中的距离定义。计算每一个集合内部的误差的时间复杂度至少是线性的,而集合内部误差计算的工作是相对独立的,可以较为方便地在多台计算节点间进行任务分配。

近似查询的首要目标是能够以任意大小的数据量来表达一个要素,这里有一些隐含的限制条件:线对象的组成顶点数量不能少于2个,面对象组成顶点的数量不能少于3个。为了实现这一目标,这里将对每个要素的组成顶点进行采样,同时采样后的顶点之间的关系遵从其内部的结构关系,同时地理要素的一致性需要得到保持。单个要素近似查询之后的完整性得以保持;多个要素的拓扑关系,如共点或共线,在近似查询之后,同样必须得以保持。

为了实现有效的近似查询处理,这里对地理要素集中的每个顶点赋予一个权值,顶点采样过程中将基于该权值降序进行顶点的选择,从而取得一个原地理要素集的组成顶点的子集,同时根据原顶点的关系重建这些要素,形成空间近似查询的结果集,该结果集满足用户对于数据量的限制条件。