空间数据查询处理技术详解

### 空间数据查询处理技术详解 #### 1. 天际线定义与查询处理挑战 天际线定义在道路网络环境中已有相关研究，但由于其与图数据库关联较大，暂不深入探究。在查询处理方面，top - k 运算符虽能返回小结果集，但需指定排序函数，这并非易事；而天际线运算符虽避免了排序函数的指定，却会产生较大结果集，即便对于二维感兴趣属性，结果集也可能非常庞大。并且，这两种运算符在处理连接操作时都颇具挑战。 #### 2. 近似查询处理（ApQP） ##### 2.1 ApQP 概述 近似查询处理（ApQP）是指使用专门的查询处理算法来执行本质上昂贵的传统或宽松查询（如连接或 top - k 运算符）。这些算法会根据可用数据和资源自动应用最小程度的宽松处理，以高效计算出与用户请求相似的非空结果。ApQP 适用于数据量大、异构，资源有限或查询复杂的环境。与查询重写（QR）方法不同，ApQP 不改变查询本身，而是修改其执行方式以获得近似答案。 ##### 2.2 传统 ApQP 技术的四种方法 - **修改现有算法**：通过引入较弱条件来修改现有处理算法以生成近似结果。例如，将相等检查替换为相似性检查以提高质量，或在分支限界方法中使剪枝条件更具选择性，从而减少对原始数据集的访问，提高时间效率。 - **提供新算法**：有时将 ApQP 问题重新表述为非近似操作的组合。例如，字符串属性的近似连接可简化为聚合集交集。 - **使用启发式方法**：提供启发式方法以降低给定算法的计算成本。通过利用数据属性（如寻找局部最优解）有效探索解空间，遗传算法就属于此类方法。 - **修改输入数据集**：当处理给定域的值或整个对象集成本过高时，引入近似表示（如概要或小波）来修改输入数据集，并提供特定的查询处理算法来处理这些新数据集。 ##### 2.3 空间数据的 ApQP 技术 对于空间数据，也提出了代表上述四种方法的 ApQP 技术。这些技术用于处理如多路空间连接（即两个以上地图的连接）和基于距离的查询等昂贵操作。由于空间数据处理依赖于索引结构（如 R - 树），这些结构也得到了扩展以支持近似处理。在第四种方法中，由于处理空间值的计算复杂度高，通常会引入对象精确几何形状的近似表示，这与传统的近似数据表示（如最小边界矩形 MBRs）不同，且一般无法精确检测查询结果。 #### 3. 空间 Top - k 查询 ##### 3.1 Top - k 排序函数 在空间数据领域，主要有三种排序函数： - **Top - k 空间偏好查询**：选择 k 个最佳空间对象，其得分量化了对象空间邻域内特征的质量。得分计算基于邻域条件（范围条件或最近邻条件）和特征数据集，通过聚合各特征集的得分得到对象的总得分。例如，“检索威尼托地区得分最高的 2 个主要城镇，得分计算为 25 公里内湖泊的最大面积”。 - **Top - k 有影响力的站点**：基于双色反向最近邻（bichromatic RNN）问题，站点的得分是其影响集内对象权重的总和。例如，查询威尼托地区最有影响力的 k 家医院，医院的影响力由其周边市政当局的居民总数决定。 - **Top - k 空间连接**：基于空间对象对之间的交集数量计算得分。例如，对河流和市政当局数据集进行 top - k 空间连接，可返回穿越最多市政当局的河流或被最多河流穿越的市政当局。 |排序函数类型|定义|示例| | ---- | ---- | ---- | |Top - k 空间偏好查询|$\tau_{\theta}(p) = agg\{\tau_{\theta_i}(p) \vert i \in [1,m]\}$|检索威尼托地区得分最高的 2 个主要城镇，得分计算为 25 公里内湖泊的最大面积| |Top - k 有影响力的站点|$\tau(p) = sum\{\omega(o)\vert o 属于 p 的影响集\}$|查询威尼托地区最有影响力的 k 家医院，医院影响力由周边市政当局居民总数决定| |Top - k 空间连接|$\tau(o) = card\{o'\vert o' \in (A\cup B - C), o 与 o' 相交\}$|对河流和市政当局数据集进行 top - k 空间连接，返回穿越最多市政当局的河流或被最多河流穿越的市政当局| ##### 3.2 Top - k 查询处理算法 传统数据的排序函数单调性假设可通过特定阈值优化 top - k 查询处理，但该方法不适用于空间数据。空间数据通常需基于索引（如 R - 树）进行访问，且排序函数依赖于空间关系，因此设计了新的优化方法。在计算 top - k 结果时，通常会维护以下结构： - 队列 Q：用于存储到目前为止生成的 top - k 结果，按得分值排序。 - 阈值 ρ：表示 Q 中的最低得分值，即基于已访问对象的 k 个最高得分的下界。 - 特定数据结构：用于高效计算对象得分。 主要有两种访问方式： - **传统访问**：通常以深度优先或广度优先的方式访问空间索引。例如，top - k 传统访问算法（TV）基于深度优先搜索，在访问过程中计算叶节点指向对象的得分，若得分大于或等于 ρ，则更新 Q 和 ρ。 ```python # 算法 1：top - k 传统访问（TV） def TV(N, Q, ρ): for e in N.entries: if not N.is_leaf: N_prime = e.child_node TV(N_prime, Q, ρ) else: score = compute_score(e) if score >= ρ: update_ ```