·1164· 智能系统学报 第15卷 的索引技术主要有倒排文件(inverted file)、签名 1相关工作 文件(signature file)和位图索引(bitmap)等。上述 文本索引以及空间-文本索引主要适用于查询关 随着移动网络的普遍应用，网络上出现了越 键字的严格形式匹配，但由于现实中文本表达形 来越多的空间Web对象(spatial web object)。一个 式多样，如果采用关键字严格形式匹配，可能导 空间对象通常包含位置信息（如经纬度）、文本信 致返回的查询结果太少或没有结果。针对上述问 息（如空间对象的名称、设施、类别等）以及数值 题，相关研究如文献[6-8]中提出了一些新的索引 信息（如价格、用户评分等），数值信息有时也归为 技术以处理文本中的拼写错误，然而这些方法并 文本信息。现有工作将数值信息作为文本关键字 没有考虑文本之间的语义相似/相关度。尽管最 来进行处理，但实际上数值信息的处理方法与文 近有少数工作研究了空间关键字查询的语义匹配， 本信息匹配的处理方法有本质区别（如文本信息 但空间对象除包含位置信息和文本信息外，还包 的主要处理方法是统计和字符串匹配，而数值信 含了价格、用户评分等数值数据。目前还没有相 息可以进行数值大小比较、数值计算等操作)。 关工作同时考虑空间对象与空间关键字查询在位 现有的空间关键字查询处理模式主要可以分 置、文本、语义和数值上的综合相关度，进而也就 为4类：布尔范围查询、布尔k近邻(kNN)查询、 没有同时支持上述综合查询的混合索引结构。 top-k范围查询以及top-kk近邻查询。上述四类 针对上述问题，本文工作的重点是建立一种 方法呈递进式发展，后者是对前者的改进。布尔 同时融合位置信息、文本信息、语义信息和数值 范围查询的缺点是不能控制查询结果规模，且没 信息的空间关键字查询处理模式，并提出一种有 有对查询结果进行排序；布尔k近邻查询是通过 效的混合索引结构来提高查询效率。 兴趣点与查询点之间的距离对查询结果排序，排 本文的主要贡献如下： 序前后与距离大小成反比。布尔范围查询和布 l)提出了基于Word Embedding技术对初始 尔k近邻查询方法都需要兴趣点的文本描述中包 查询关键字进行语义扩展的方法，能够为用户提 含所有查询关键字，这很可能导致查询不到结果 供语义相关的近似查询结果； 或只有少量查询结果，或是得到的查询结果距离 2)在文本信息匹配方面，考虑了查询关键字 查询点的位置很远。top-k范围查询和top-k近邻 可能会出现拼写错误情况，提出了基于编辑距离 查询模式不要求兴趣点的描述信息包含所有的查 的字符串相似度度量方法，尽量避免因查询关键 询关键字，查询结果也可以是仅包含部分关键字 字拼写错误而导致没有匹配结果的情况： 的查询结果。然而，top-k范围查询的排序方法仅 3)提出了基于Skyline的数值属性处理方法， 考虑了兴趣点的文本相关性而没有考虑位置相近 使得空间关键字查询处理模式能够处理数值属 性，top-kk近邻查询同时考虑了兴趣点与查询的 性，令查寻结果更能满足用户的个性化需求。 位置相近性和文本相关性，但没考虑语义相关性。 4)构建了一种新型的混合索引结构AIR 空间关键字查询o1山通常需要将空间索引和 Tree,该索引结构能够直接从每个节点中获取该 文本索引相结合起来构建混合索引结构，从而达 节点对应的数值属性的Skyline集合，并能同时对 到高效地检索空间对象的目的。当前主要的空间 位置信息、文本信息和语义信息进行索引。 数据混合索引结构可归结为表1所示的几类。 表1混合索引结构 Table 1 Hybrid index structure 索引名称 组合模式 优点 缺点 两阶段索引阿 R-tree,Inverted file 结构简单 存储代价高，无法确定第一阶段产生的 候选对象个数 IR'-tree R-tree+Signature 存储代价低、搜索效率高 查询关键字必须严格匹配 IR-tree R-tree+Inverted file存储空间小，提高了搜索效率，允许查询 未考虑查询的语义相关性 关键字部分匹配 bR*-tree间 R*-tree+Bitmap 存储空间小，关键字匹配效率高 关键字多，I/O代价高 Light--Weighted索lW R*-tree和Inverted 可扩展性较强，搜索效率高 存储代价高，频繁插入操作 fle分开存储 的计算代价过高 Quadtree索引 Quadtree+Inverted file 区域搜索效率高 树结构不平衡，存储代价较高 G--index索 聚类标准+聚类操作 通用性强 存储代价高，泛化计算代价高的索引技术主要有倒排文件 (inverted file)、签名 文件 (signature file) 和位图索引 (bitmap) 等。上述 文本索引以及空间−文本索引主要适用于查询关 键字的严格形式匹配，但由于现实中文本表达形 式多样，如果采用关键字严格形式匹配，可能导 致返回的查询结果太少或没有结果。针对上述问 题，相关研究如文献 [6-8] 中提出了一些新的索引 技术以处理文本中的拼写错误，然而这些方法并 没有考虑文本之间的语义相似/相关度。尽管最 近有少数工作研究了空间关键字查询的语义匹配[9] ， 但空间对象除包含位置信息和文本信息外，还包 含了价格、用户评分等数值数据。目前还没有相 关工作同时考虑空间对象与空间关键字查询在位 置、文本、语义和数值上的综合相关度，进而也就 没有同时支持上述综合查询的混合索引结构。 针对上述问题，本文工作的重点是建立一种 同时融合位置信息、文本信息、语义信息和数值 信息的空间关键字查询处理模式，并提出一种有 效的混合索引结构来提高查询效率。 本文的主要贡献如下： 1) 提出了基于 Word Embedding 技术对初始 查询关键字进行语义扩展的方法，能够为用户提 供语义相关的近似查询结果； 2) 在文本信息匹配方面，考虑了查询关键字 可能会出现拼写错误情况，提出了基于编辑距离 的字符串相似度度量方法，尽量避免因查询关键 字拼写错误而导致没有匹配结果的情况； 3) 提出了基于 Skyline 的数值属性处理方法， 使得空间关键字查询处理模式能够处理数值属 性，令查寻结果更能满足用户的个性化需求。 4) 构建了一种新型的混合索引结构 AIR￾Tree，该索引结构能够直接从每个节点中获取该 节点对应的数值属性的 Skyline 集合，并能同时对 位置信息、文本信息和语义信息进行索引。 1 相关工作 随着移动网络的普遍应用，网络上出现了越 来越多的空间 Web 对象 (spatial web object)。一个 空间对象通常包含位置信息 (如经纬度)、文本信 息 (如空间对象的名称、设施、类别等) 以及数值 信息 (如价格、用户评分等)，数值信息有时也归为 文本信息。现有工作将数值信息作为文本关键字 来进行处理，但实际上数值信息的处理方法与文 本信息匹配的处理方法有本质区别 (如文本信息 的主要处理方法是统计和字符串匹配，而数值信 息可以进行数值大小比较、数值计算等操作)。 现有的空间关键字查询处理模式主要可以分 为 4 类：布尔范围查询、布尔 k 近邻 (kNN) 查询、 top-k 范围查询以及 top-k k 近邻查询。上述四类 方法呈递进式发展，后者是对前者的改进。布尔 范围查询的缺点是不能控制查询结果规模，且没 有对查询结果进行排序；布尔 k 近邻查询是通过 兴趣点与查询点之间的距离对查询结果排序，排 序前后与距离大小成反比。布尔范围查询和布 尔 k 近邻查询方法都需要兴趣点的文本描述中包 含所有查询关键字，这很可能导致查询不到结果 或只有少量查询结果，或是得到的查询结果距离 查询点的位置很远。top-k 范围查询和 top-k 近邻 查询模式不要求兴趣点的描述信息包含所有的查 询关键字，查询结果也可以是仅包含部分关键字 的查询结果。然而，top-k 范围查询的排序方法仅 考虑了兴趣点的文本相关性而没有考虑位置相近 性，top-k k 近邻查询同时考虑了兴趣点与查询的 位置相近性和文本相关性，但没考虑语义相关性。 空间关键字查询[10-11] 通常需要将空间索引和 文本索引相结合起来构建混合索引结构，从而达 到高效地检索空间对象的目的。当前主要的空间 数据混合索引结构可归结为表 1 所示的几类。 表 1 混合索引结构 Table 1 Hybrid index structure 索引名称 组合模式 优点 缺点 两阶段索引[12] R-tree，Inverted file 结构简单 存储代价高，无法确定第一阶段产生的 候选对象个数 IR2 -tree R-tree+Signature 存储代价低、搜索效率高 查询关键字必须严格匹配 IR-tree R-tree+Inverted file 存储空间小，提高了搜索效率，允许查询 关键字部分匹配 未考虑查询的语义相关性 bR*-tree[13] R*-tree+Bitmap 存储空间小，关键字匹配效率高 关键字多，I/O代价高 Light-Weighted索引[14] R*-tree和Inverted file分开存储 可扩展性较强，搜索效率高 存储代价高，频繁插入操作 的计算代价过高 Quadtree索引 Quadtree+Inverted file 区域搜索效率高 树结构不平衡，存储代价较高 G-index索引[15] 聚类标准+聚类操作 通用性强 存储代价高，泛化计算代价高 ·1164· 智 能 系 统 学 报 第 15 卷