空间数据的近似查询：基于定性关系的新视角

### 空间数据的近似查询：基于定性关系的新视角 在空间数据处理领域，近似查询技术正逐渐从数据表示向查询结果问题转变。传统数据的基于查询的近似技术已被扩展到空间领域。目前，空间数据的近似查询方法主要分为三类：查询重写、基于偏好的查询和近似查询处理，其中大多数现有方法属于后两类。 #### 1. 从定性到定量的空间关系 为了将空间数据的定性关系转化为可量化的形式，最常用的方法是借助距离函数。给定一组定性空间关系 $G$，如拓扑关系，距离函数 $D_G$ 可用于计算 $G$ 中两个空间关系 $\theta_1$ 和 $\theta_2$ 之间的差异，其返回值在 0 到 1 之间，值为 0 表示 $\theta_1$ 和 $\theta_2$ 完全相同。 在相关研究中，针对拓扑和方向关系提出了多种距离函数： - **拓扑关系距离函数**： - 早期的一些方法基于拓扑关系的概念邻域图，定义了特定拓扑关系集合（如面 - 面关系）之间的偏序。 - 部分研究利用拓扑距离评估空间场景的相似性，同时考虑方向和距离关系。 - 还有研究使用拓扑距离定义模型，比较线和面之间的不同拓扑关系。不过，这些早期研究大多仅考虑相同维度对象对之间的相似性，未涉及多对象表示。 - 近期的研究将早期的距离函数扩展到与几何类型无关的拓扑或方向关系集合，基于关系的矩阵表示计算 0 到 1 之间的值。 - **方向关系距离函数**： - 有研究定义了两种方向关系的距离函数。一种用于单瓦片关系，对应概念图中连接两个方向的最短路径长度；另一种用于多瓦片关系，考虑目标对象在每个瓦片中的占比，但该方法未基于定义方向关系的模型。 - 另有研究提出的距离函数克服了上述问题。 基于选定的距离函数 $D_G$，可以定义关于查询关系 $\theta \in G$ 的空间对象对之间的距离函数 $d_{\theta}^G$： **定义 8（基于 $G$ 的空间距离）**：设 $G$ 是一组定性空间关系，$\theta \in G$，$f$ 和 $g$ 是两个空间对象，满足 $f\theta'g$，$\theta' \in G$，$D_G$ 是 $G$ 的距离函数。则基于 $D_G$ 相对于 $\theta$ 的 $f$ 和 $g$ 之间的 $G$ 基空间距离定义为：$d_{\theta}^G(f,g) = D_G(\theta,\theta')$。 **示例 11**：考虑为面定义的拓扑关系集合 $G = \{disjoint(d), touches(t), overlaps(o), within(i), contains(c), equals(e), coveredBy(b), covers(v)\}$，其中 $coveredBy$（$covers$）类似于 $within$（$contains$）但边界接触，而 $within$ 和 $contains$ 要求边界不接触。设 $D_G(\theta_1,\theta_2)$ 基于概念邻域图定义为图中 $\theta_1$ 和 $\theta_2$ 之间最短路径的边权重之和。例如，$D_G(d,d) = 0$，$D_G(d,t) = 1$，$D_G(d,e) = 10$。那么基于上述 $D_G$ 相对于不相交关系的 $f$ 和 $g$ 之间的 $G$ 基空间距离 $d_d^G(f,g)$，若 $f$ 和 $g$ 不相交则为 0，否则其值衡量不相交关系与 $f$ 和 $g$ 之间现有关系 $\theta'$ 的相似度。例如，若 $f$ 包含于 $g$，则 $d_d^G(f,g) = D_G(d,i) = 8$。 一般来说，基于 $G$ 的空间距离不具有对称性，也不满足三角不等式，并且空间、嵌入其中的对象与距离函数返回的值之间没有直接关系，这限制了对现有查询处理算法的优化。 #### 2. 基于定性关系的空间 Top - k 查询 利用上述定性空间距离，可以定义基于 $G$ 中关系的 Top - k 查询。以下是一些查询示例： - 假设主要城镇和河流都用多边形表示，使用拓扑距离函数 $d_o^G(o, Piave)$ 量化每个对象 $o$ 与皮亚韦河在重叠关系上的得分，找出与皮亚韦河重叠的前 100 个主要城镇。结果列表中，实际与皮亚韦河重叠的城镇应排在前面，接着是满足接近重叠拓扑关系的城镇，按得分排序。 - 使用方向距离函数 $d_{South}^G(o, Vicenza)$ 量化每个对象 $o$ 与维琴察在南方关系上的得分，找出威尼托地区位于维琴察南方的前 2 个市镇。结果列表中，罗维戈应排在首位，因为它位于维琴察的东南方，其次是维罗纳和帕多瓦中的一个。 这些查询可以基于以下定义的排名函数定义为 Top - k 查询： **定义 9（基于 $G$ 的排名函数）**：设 $f$ 是空间对象，$q$ 是查询对象，$d_{\theta}^G$ 是基于 $G$ 的空间距离。基于 $d_{\theta}^G$ 的 $G$ 基排名函数定义为：$\tau_{\theta}^q(f) =