空间数据的近似查询技术

# 空间数据的近似查询技术 ## 1. 引言 空间数据与传统的非地理参考数据相比，具有内在的复杂性，从一开始就需要在处理中使用近似技术。在早期的地理信息系统（GIS）中，近似主要涉及数据采集和数据表示。例如，在制图学中，矢量地图的比例尺意味着它所包含的空间对象具有一定的空间精度，这种精度会影响数据处理，因为用户查询的结果虽然计算精确，但总是以一定的精度级别呈现。 在现代GIS中，尽管精度问题尚未完全解决，但为了在返回精确结果的同时提高查询性能，近似处理本身也成为了热门话题。通常的查询处理技术需要将任意几何数据近似为更简单的对象，如矩形或凸多边形，然后对这些简单对象进行索引，并分两步回答查询： 1. **过滤阶段**：根据简化的几何形状过滤空间数据，以检测哪些对象很可能满足查询条件，返回一个包含精确答案的近似结果。 2. **细化阶段**：考虑精确的几何形状，细化第一步得到的结果，向用户返回查询的精确答案。 近年来，环境和应用的快速发展彻底改变了数据集合的查询处理方式，也导致了对传统和空间数据近似概念的重新诠释。在新环境中，数据往往是异构的，其特征高度可变。空间数据的异构性通常是由于在表示同一地理区域的数据时采用了不同的分辨率或精度级别。这些数据通常由不同的机构在不同的时间收集和处理，需要一起处理，因此需要适当的集成方法。 此外，数据的异构性和可变性使得查询规范成为一个问题，因为用户可能无法完全准确地指定查询，即使数据来自单一来源。在分布式架构中，这些问题更加明显，因为输入数据可能来自多个不同的来源，格式不同，并且由具有不同性能和可用性的系统提供。在这些情况下，数据集成和查询的资源通常不足以在合理的时间和空间内获得精确的响应。 在上述所有情况下，仅从查询执行中获得精确答案是过于雄心勃勃的，因为在这些情况下，经常会发现不一致或模糊的数据，很难准确描述我们正在寻找的内容，并且可能无法在合理的时间内获得精确计算的资源。因此，需要在查询规范和处理中考虑数据的异构性、用户的有限知识和资源，以获取一个宽松或近似的解决方案，同时提高用户满意度。 ## 2. 空间数据和查询的背景知识 ### 2.1 空间数据库模型 基于当前GIS支持的空间关系模型，空间数据库通常可以表示为一组表（以下称为特征表或地图）。每个表包含值的元组，也称为特征或空间对象，每个值属于一个特定的域。除了字符、字符串、整数和实数等原子域之外，OGC标准的简单特征模型中描述的空间域通常也可用。OGC的基本几何类型包括： - **点（Point）**：零维几何对象，表示坐标空间中的单个位置。 - **曲线（Curve）**：一维几何对象，通常存储为点的序列，曲线的子类型指定了点之间的插值形式（例如，LineString使用点之间的线性插值）。 - **表面（Surface）**：二维几何对象，简单表面可能由一个与一个外部边界和0个或多个内部边界相关联的单一补丁组成。多边形（Polygon）是表面的一种特殊类型，其边界是LineString实例。 ### 2.2 运行示例 为了说明相关技术，我们以意大利北部威尼斯周边地区（威尼托）的数据库为例，该数据库包含省份、市镇、河流、湖泊和主要城镇等信息。每个特征集都表示为一个地图，数据库的空间内容如图所示。数据通过引入六个不同的地图（表）进行建模，每个地图都有一个具有空间域的几何属性。具体如下： - **MitPr**：包含以多边形表示的省份。 - **MitRv**：包含以线表示的主要河流。 - **MitLk**：包含以多边形表示的湖泊。 - **MitTw0和MitTw2**：分别以点和多边形表示主要城镇。 - **MitMp**：包含以多边形表示的市镇。 特征表除了几何属性外，还可能包含其他描述性信息。例如，MitLk中的每个湖泊可以表示为一个具有两个属性的元组：一个表示湖泊名称，另一个表示其空间范围。 ### 2.3 空间关系 空间数据通常通过空间关系相互关联，拓扑、方向和基于距离的关系几乎涵盖了实际系统中通常可用的所有空间关系类型（尽管OGC标准仅支持拓扑和基于距离的关系）。 - **拓扑关系**：是地理应用中最常用和已知的关系，基于在同胚变换（即不切割或折叠空间的拉伸或收缩变换）下不变的属性。根据Egenhofer等人的定义，并考虑OGC标准，拓扑关系可以通过9 - 交集模型正式定义。在9 - 交集模型中，每个几何对象A由三个点集表示：其内部$A^◦$、外部$A^-$和边界$∂A$。两个几何对象A和B之间的二元拓扑关系的定义基于每个几何组件的9个交集。拓扑关系可以表示为一个3x3矩阵，称为9 - 交集矩阵： \[ R(A,B) = \begin{pmatrix} A^◦ \cap B^◦ & A^◦ \cap ∂B & A^◦ \cap B^- \\ ∂A \cap B^◦ & ∂A \cap ∂B & ∂A \cap B^- \\ A^- \cap B^◦ & A^- \cap ∂B & A^- \c