4.1.3 带有约束条件的空间近似查询
1.数量约束的空间近似查询
空间近似查询处理可以归结为一个空间范围内的top k查询问题。由于空间查询处理的复杂度为O(log n+k),其中n为要素的顶点数量,k为输出数据量,因此查询处理的时间与查询结果的数据量是线性相关的。数量约束的近似查询即是以查询窗口作为空间条件进行近似查询,在该条件之外,加入数量条件作为约束,查询达到数量上限时终止查询操作。表4-3为数量约束的窗口近似查询算法。
表4-3 数量约束的窗口近似查询算法
续表
2.时间约束的空间近似查询(https://www.daowen.com)
由于查询处理的时间与查询结果的数据量是线性相关的,因此,可以把查询条件转换为时间约束的空间近似查询。时间约束的近似查询是以查询窗口作为空间条件进行近似查询,在该条件之外,加入时间条件作为限制,查询达到时间限制条件时终止查询操作。表4-4为时间约束的窗口近似查询算法。
表4-4 时间约束的窗口近似查询算法
3.误差约束的空间近似查询
同数量和时间约束的空间近似查询类似,误差约束的空间近似查询处理的基本思路为:线对象经过顶点采样算法生成二叉树类型的顶点层次结构之后,当需要处理近似查询时,在二叉树上运行权值优先广度遍历,同时在遍历树节点的过程中利用空间条件进行动态剪枝,即可按误差降序取出在特定窗口内的顶点。误差优先的广度遍历是近似查询的基础操作,表4-5为误差约束的窗口近似查询算法。
表4-5 误差优先的窗口近似查询算法
