面向复杂地理实体快速查询的空间语义模式图构建及搜索方法

主题：主题：12. 地理信息与人工智能 面向复杂地理实体快速查询的空间语义模式图构建及搜索方法面向复杂地理实体快速查询的空间语义模式图构建及搜索方法 呙维，佘冰，刘异，朱欣焰，王绪滢 武汉大学测绘遥感信息工程国家重点实验室，湖北 武汉，430070，guowei-lmars 摘要：摘要：本文实现了一种面向复杂地理实体快速查询的空间语义模式图构建及搜索方法， 该方法从位置概念查询的认知分析展开， 定义模式图的组成， 进而讨论了模式图的构建和查 询过程。通过将语义与空间联合索引， 减少了“由底向上”多属性联合查询的排列组合， 降低了效率损失。实验验证了该方法的有效性。 关键词关键词: :位置概念查询；模式图构建；语义与空间索引；节点遍历 1 1 绪论绪论 1.1 1.1 研究背景研究背景 传统的文本相似性方法不能充分利用语义匹配中的结构与词汇类别等信息。实际位 置描述中的省略性、模糊性等情况易导致组合爆炸的问题，造成效率损失。当前空间数 据的检索查询分为根据空间范围检索和根据关键词与空间的联合检索。 前者包括四叉树、 R 树等，这种方法利于空间数据的快速检索。但其语义过滤过程较为简单，因此很容易 被人忽略。后者常用于查找最邻近的空间对象，其中空间检索一般用 R 索引或格网索 引，文本索引一般为倒排形式。但这种方法未利用到由语义匹配产生的位置概念层次语 义特征，不适合包含复杂层次结构的位置描述解析。为了实现位置概念描述与实体的对 应， 需结合语义搜索与空间约束进行空间过滤。 位置概念具有概念和空间关系的关联性、 关联关系的网络性及表述形式的层次性。为了获取位置描述对应的位置概念对象，需要 利用位置概念的语义信息，包括组成形式、层次结构及关联关系。因此为了建立高效的 查询检索，需要一种能快速获取经匹配后的位置描述对应的位置概念对象机制。因此本 文将语义与空间联合索引， 实现了一种面向复杂地理实体快速查询的空间语义模式图构 建及搜索方法，进而减少了“由底向上”多属性联合查询的排列组合，降低效率损失。 2 2 实现方法实现方法 本文采用如下技术方案：首先分析自然语言位置描述的语义组成，形成位置概念模 式，进而建立位置概念模式定义图，将规则匹配的位置本体实例进行模式拆解和入库， 形成基础位置概念模式图。 然后自动化构建中间层模式代表对象， 补全位置概念模式图。 最后提供了一种位置概念模式图搜索方法。 位置概念多字段联合检索依赖于对位置概念建立关系数据表表达。其以主键关联来 表示层次型的关联关系，并依赖于属性索引和递归的 SQL 查询。但这种自底往上的形 式未能充分利用位置描述的组合特征进行表达和检索， 也未能融合位置概念的关联特征。 而模式图本质上是一种语义与空间的联合索引机制， 其将位置概念的语义信息融合到不 同的模式表达中，空间特征则用以辅助查询过滤。 位置概念的组合特征可以总结为位置概念的表达模式。例如，对于一条标准的地址 “武汉市青山区钢都花园 123 街坊 55 门号 1 栋”，其完整的地址结构如图 1 所示。对其 可以有若干种描述形式： ADMCity 武汉 FeaWord 市 ADMCounty 青山 FeaWord 区 ADMTown 钢都 FeaWord 花园 Character 5 Character 5 NumAbc 55 ADMCityName 武汉市 ADMCountyName 青山区 ADMTownName 钢都花园 FeaWord 123街坊 GeneralNum 55 AdsFeaWord 门号 NumAbc 1 Character 1 ComGName 武汉市青山区钢都花园 ResidAreaName 123街坊 FirstGradeBuildingAds 55门号 BuildingNum 1 AdsFeaWord 栋 ADMAds 武汉市青山区钢都花园 CommunityAds 123街坊55门号 SecondGradeBuildingAds 1栋 AddressName 武汉市青山区钢都花园123街坊55门号1栋 图 1 位置概念语义构成示例 -“武汉市青山区钢都花园 123 街坊 55 门号 1 栋” （1） 武汉青山钢都 123 街坊 55 门号 1 栋 （2） 武汉钢都 123 街坊 55 门号 1 栋 （3） 青山区钢都花园 123 街坊 55 门号 1 栋 （4） 青山区钢都 123 街坊 55 门号 （5） 青山区钢都花园 123 街坊 （6） 钢都花园 123 街坊 1 栋 （7） 青山钢都 （8） 这些表述形式反映出概念的子部分可能的组成形式，一种组合形式对应一种模式。 位置概念具有层次型特征，如地址对象中“钢都花园 123 街坊 1 栋”对应“钢都花园 123 街坊”等若干组合， 每种组合对应一个模式节点。 模式节点可能包含多个位置概念对象， 如“钢都 123 街坊”对应的模式节点，可能包含位于钢都 123 街坊下的若干地址对象。某 一模式节点也可能包含分布于多个区域的若干对象，如“陈家湾 12 号”，可能对应分布 在若干区的多地址子集。 模式将查询对象进行了封装，并实现了将实际对象和代表模式的分开存储。只有查 询时对模式检索，实际定位时才获取其对象。如图 2 所示为模式图组成及层次示意。模 式节点中包含组合的编码，对应的位置概念对象及综合后的空间特征。对应于同一位置 概念的模式基于关联性形成模式节点网络。 将经由位置描述匹配后形成的位置概念虚拟 对象进行递归分解查询， 通过子概念的模式编码的组合搜寻各层符合的模式节点返回给 上层，获取顶层对应的模式节点及对应位置概念数据库中的位置概念对象。 1 23 address(c(15) 位置概念 对象数据库 ADMAds ADMAdsCommunityAds CommunityAds ADMCounty ADMCounty 模式节点 数据库 FeaWord FeaWord Character Character address(a (12)_c(15) address(a (17)_c(15) address(a (12)_c(15)_d(100) address(a (12)_c(15)_d(120) address(a (17)_c(15)_d(100) 匹配树匹配树 12 17 4 56 admads(a (170) admads(a (170) admads(a (170)_b(120) admads(a (170)_b(120) 15 comm(a (170) comm(a (170) FeaWord FeaWord ADMCity ADMCity 200 admcity(200) admcity(200) a(12) a(17) c(15) d(100) d(120) 模式图模式图 SecondGradeBuildingAds SecondGradeBuildingAds 100120 second(c (270) second(c (270) second(c (260) second(c (260) 统计特征 空间特征 对象对象 对象对象 图 2 模式图组成及层次示意 其中一个模式节点 p 由一个七元组构成，形式为： p = (c,i,m,n,g) （式 4-1） 其中 c 代表模式节点编码，i 代表模式节点 ID, L 代表模式节点的一阶子节点集合， R 代表模式节点的强对应位置概念对象集合, m 代表该模式对应的全部位置概念对象数 目，n 代表该模式所包含的全部子模式数量，而 g 代表模式的空间外包矩形。 模式图的构建采用如下技术方案： 首先模式分解位置概念对象并逐级构建模式节点， 根据模式存储和查询策略利用模式节点的关系压缩模式图；进而更新模式的空间、统计 特征及关联关系，相似性度量并实现模式节点中位置概念的重排序。 模式分解查询的过程是通过利用子概念的模式编码组合搜寻符合的模式节点返回 给上层，进而获取顶层模式节点和位置概念数据库中的位置概念对象。 3 3 实验实验结果结果与与分析分析 本文的实验部分基于算法效率对比基于模式的方法和基于多字段联合检索的位置 概念查询 （MF-LCS） 的形式。 将数据分成三种情况， 各随机构造 200 个位置概念对象： （1） 标准形式：位置概念的成分完整，即保留入库时的结构； （2） 省略形式：位置概念存在部分缺失，随机置空； （3） 错置形式：位置概念中存在概念的成分错误，随机置换； 实验基于江岸区地址库及全市 POI，包含 71992 条地址、51606 条 POI。模式图采 取 Redis 内存数据库， MF-LCS 采取 PostGreSQL 数据库， 并对应位置概念类别表构造子 概念字段的联合 B-tree 索引。表 1 为复杂位置概念存储数量及模式数量。 表 1：PFS 与 MF-LCS 对比实验存储位置概念 类型 对象数量 模式数量 类型 对象数量 模式数量 ADMAds 73269 75526 FirstGradeBuildingAds 7446 7094 ADMCityName 344 674 GeneralNum 3714 2461 ADMCountyName 18 36 NumAbc 2624 2624 ADMTownName 188 372 POI 51606 559454 ADMVillageName 3525 6589 ResidAreaName 851 1482 AddressName 73269 370800 RoadAds 28401 29046 BuildingNum 352 350 RoomNum 4 4 ComGName 341 703 SecondGradeBuildingAds 356 350 CommunityAds 5907 5631 TraCityRoadName 1722 2956 图 6 和 7 显示了两者对于地名和 POI 在不同形式下的耗时对比。从中可以看出，在 处理层次形式简单的位置概念对象时，MF-LCS 的效率更高，而当有省略和错置情况发 生时，模式查询形式则体现出其优势。但对于地址这种复杂层次关系，如图 8 所示，其 在三种形式下的效率都显著低于 PFS。 二者的另一区别在于位置概念关联的融入， 如 “走马岭学校” 中 “走马岭” 是地名， 对应 POI 中的模式子部分组成是 b(910) 。 “学校”是通名(CommonName)，其在 POI 中 的模式子部分组成是 c(212697)。 而经模式分解查询， 走马岭学校(poi(b(910)_c(212697) 并不存在，如表 2 所示。 表 2 模式关联查询输出示例：走马岭学校 模式编码 位置概念匹配构成 名称 poi(b(910)_c(212801) (POI(ADMTownName(ADMTown走马 岭),(CommonName小学),(Qualifier中心) 走马岭中心小学 poi(b(910)_c(212967) (POI(ADMCityName(ADMCity武汉),(FeaWord 市),(ADMTownName(ADMTown走马 武汉市走马岭中学 岭),(CommonName中学) 图 4 PFS 和 MF-LCS 效率对比图：地名 图