摘要: 1. 研究动机和创新点
本文提出了一种在地理信息系统(GISs)中进行近似查询的方法。这里，用户并不需要精确的查询结果，而是希望能迅速地获得近似的结果，不希望结果集为空。我们的方法也适用于无法获得精确结果的情况，比如查询中缺少必要的地理概念或拓扑配置信息，或者查询的实例在地理信息数据库中不可用。在文中，我们研究了如何通过松弛化查询的约束来获得近似的结果。查询通过“地理图示查询语言”(GeoPQL) 1来表示。图形化配置使得用户可以根据自己的心理模型1，通过更自然的方式来描述查询。在某些情况下，查询约束的描述信息可能涉及数据库中不可用的地理概念或者拓扑配置。这个问题是严重的，因为系统将不可用，而且导致用户满意度严重受损。用户对于近似查询结果的需求情况已经在文献2中进行了实验。在我们的实验中，一些经验数据表明，相对于没有结果返回的情况，95%的用户更希望获得近似的查询结果。
我们主要关注那些与类别属性集合关联的地理概念，这些概念被称为符号化图形对象 (SGOs)。一个地理查询可以表示为一个SGO的集合以及它们之间的二元拓扑关系。近似查询的实现主要通过松弛化SGO的三个主要类别约束：拓扑、语义和结构。拓扑约束指的是SGO的几何类别（点、折线、多边形）之间的拓扑关系，语义约束指的是SGO的概念命名，而结构约束指的是与SGO关联的类别属性集合。
2. 方法概述 (包括实现环境和结果)
为了实现拓扑约束的松弛化，与文献345中提出的9-intersection模型类似，我们的方法将SGO的拓扑关系表示为内部、边界和外部节点的交集。根据文献6，我们定义了一个拓扑相似图，将SGO之间的所有配置实例通过最小拓扑距离彼此相连，每个配置确定一对几何类型以及它们的拓扑关系。我们对9-intersection模型进行了改进，原始模型只使用一个矩阵进行运算，我们的改进模型引入了三个矩阵来扩展被处理的SGO配置的集合。在拓扑相似图中，边用配置间的最小拓扑距离来标注，该距离是通过这三个矩阵为基础运算得出的。
对于语义约束，近似查询使用一个基于WordNet7构建的相似图来实现，WordNet是一个用于Internet上的英语词汇数据库。图中的边用被连接节点的语义相似度来标注，这些相似度使用Lin8提出的基于信息内容概念的概率方法来计算。这种方法克服了传统的通过边数目来衡量的方法的缺陷，最早由Resnik910提出，并已经在一个Is-a层级结构中被用来衡量概念的相似度11。如果一个查询中的概念和数据库不匹配，可以根据相似度将其替换为语义相似图中的相邻概念。
结构约束的松弛化是通过计算两个SGO的结构相似度来实现，而结构相似度是根据SGO的类别属性集合来计算的。具体的，定义一个结构相似图，结构相似度根据二部图12中的最大权重匹配问题对应的方法来计算。和语义约束的松弛化一样，属性之间的相似度，根据信息内容的方法，通过WordNet中的概念分类来计算。
最后，我们通过一个实验来评估了本文中提出的近似查询方法。我们确认了用户在精确查询会返回空结果集的时候倾向于使用近似查询，并通过人为判定的方法证实了文中提出的相似度衡量方法的正确性。实验验证了拓扑约束松弛化和结构约束松弛化，而没有涉及语义相似度约束松弛化，这是由于我们使用的Lin8提出的语义相似度衡量方法已经在该文中进行了充分的实验验证。我们的实验取得了0.86的拓扑关联度和0.84的结构关联度。
3. 结论-Conclusion
本文讨论了地理数据库的查询约束松弛化的问题。在本文提出的方法中，拓扑、语义和结构的约束可以根据相应的相似图进行松弛化处理，使查询系统提供近似查询结果，而不是返回空结果集合。近似查询的结果，通过将查询条件替换为最相近的配置或概念来获得。每个提供给用户的近似查询都包含了一个与原始查询的相似度指标。系统给出了一个可能的近似查询结果的列表，从与原始查询相似度最高的查询开始，直到取得了一个非空的且满足了用户需求的结果集为止。用户在拓扑、语义和结构这三个方面与系统进行交互，来指定他/她的偏好。GeoPQL提供了三个相应的滑块，来根据用户需求进行查询约束的松弛化。我们的实验说明我们的相似度方法与人工的相似度判断是高度相符的。
在未来的工作中我们将进一步扩展实验，来评估用户对于系统提供的近似查询可用性的满意程度。此外，我们将加强系统智能化，使得用户可以通过用户配置文件来对查询约束进行个性化的松弛化。
4. 贡献和意义
本文的贡献和意义包括：定义了一个基于图论的用于在地理信息系统中进行近似查询的方法，使得系统可以对查询的三种不同约束：拓扑约束、语义约束、结构约束进行松弛化处理；每个近似查询都与一个衡量其与原始查询相似度的指标相关联。该指标，对于拓扑约束，根据配置实例之间拓扑距离来计算，对于语义约束通过信息内容的方法来计算，对于结构约束通过使用二部图中最高权重匹配问题的方法来计算。实验表明我们提供的方法与人功的判断高度相符。