4.1.2　单个地理对象的近似查询

在对地理要素进行预处理建立了几何顶点的层次结构后,针对地理要素查询的就转化为对顶点层次结构的操作。在近似查询中,数据量约束与误差约束是两种类型的限制条件,近似查询就转化为top k查询问题。为了在限制条件内实现查询操作,本书采用渐进式的方式进行几何顶点的选择,采用加权广度遍历算法处理,以此有效控制查询数量和误差,渐进式采样需按照误差降序选择顶点。

因此,近似查询的基本思路为:经过线简化算法将线对象生成二叉树类型的顶点层次结构,查询时在二叉树上运行权值优先广度遍历,按照误差降序取出顶点。在不考虑窗口大小的情况下,以单个地理对象的数量约束的近似查询为例,表4-1为单个地理对象的数量约束的近似查询算法,表4-2为单个地理对象的误差约束的近似查询算法。

表4-1　针对单个地理对象的数量约束的近似查询算法(https://www.daowen.com)