移动网络的普遍应用和空间Web对象的大量出现，使得空间关键字查询成为LBS(location-based system)的重要支撑技术。现有的空间关键字查询处理模式主要有top-k范围查询(top-k range query)和top-k k近邻查询(top-k kNN query)，这两类查询处理模式主要是根据空间对象与空间关键字查询之间的文本相似度和位置相近度构建结果评分函数，进而利用文本和空间混合索引技术提高查询效率。现有的空间数据和文本信息相混合的空间−文本索引技术主要有IR-Tree^[1]、IR²-Tree^[2]、QuadTree^[3]、R*-Tree^[4]、S2I^[5]等；文本搜索的索引技术主要有倒排文件(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所示的几类。

近年来，AirBnB、TripAdvisor、hotels.com、Craigslist、Yelp以及Zillow等LBS系统，都存在布尔或分类属性，也包括大量数值属性。但是在大多数情况下，这些数值属性一般被离散化和转换为分类属性^[16]，然而这样的处理并不能满足用户的查询需求。Liu等^[17]提出的IRS-Tree是一种拥有Synopses的倒排R-Tree的混合索引结构，能够有效处理一组位置敏感等级查询。然而，基于IRS-Tree的查询算法要求提供数值属性的精确范围，故数值属性的精确匹配也可能会导致过少甚至没有查询结果返回。针对IRS-Tree存在的问题，本文利用Skyline方法^[18]，对兴趣点的数值属性进行处理，将处于被支配地位的元组从Skyline中删除，使查询结果更满足用户的个性化需求。

文本之间的语义相关性度量方法可大致分为3类：第一类是通过使用本体来定义术语/概念之间的距离，进而定义拓扑相似性估计语义相似性；第二类是使用如向量空间模型等统计手段估计语言单元(例如单词、句子)之间的语义相关性；第三类是采用概率主题模型对文本信息进行语义近似处理。词嵌入方法是近年来自然语言理解领域出现的新方法，该方法是自然语言处理(NLP)中的一组语言建模和特征学习技术的集合名称，其中词汇表中的单词或短语映射到实数向量。从概念上讲，它涉及从每个单词具有多个维度的空间到具有更低维度的连续向量空间的数学嵌入。生成这种映射的方法包括神经网络、单词共现矩阵上的降维^[19-21]、概率模型^[22]、可解释知识库方法^[23]以及单词出现上下文的显式表示^[24]，单词和短语嵌入作为底层的输入表示。该方法已经被证明可以提高NLP任务的性能，比如语法分析和情感分析^[25]。本文通过Skip-gram模型^[26]的Word Embedding技术对查询条件进行语义近似扩展，即根据查询关键字，利用Skip-gram技术生成与其语义相关的关键字信息。Skip-gram模型的训练目标是找到对预测句子或文档中的周围单词有用的单词表示。给定一系列训练单词w₁，w₂，···，w_T，Skip-gram模型可以预测出这些单词的上下文关系，从而实现语义近似查询，Skip-gram结构如图1所示。

Skyline查询技术是一种典型的偏好查询方法，由于它具有从多维数据集中提取用户感兴趣信息的能力，因此受到了广泛研究。Skyline在涉及多准则决策的应用中被广泛使用^[27]，进一步应用到top-k查询^[28-29]、偏好收集和最近邻搜索^[30]。Skyline是指在数据集中不受任何其他元组支配的元组集合^[18]。如果q在至少一个维度上优于p，并且在所有其他维度上不比p差，则称q支配p。此外，如果一对元组p和q都不支配彼此，则元组p和q都应该在Skyline中。例如，一个客户想要寻找一个度假村，假设他综合考虑3个条件：价格、酒店级别和停车位数量。价格低，级别高，停车位多无疑是更好的选择。因此，如果p在Skyline中，则没有其他的不在Skyline中的q都比p拥有更高的价格、更低的级别、更少的停车位。因此Skyline方法在对查询结果进行个性化处理方面具有很大的优势。然而，Skyline方法只能对数值属性进行计算，并不能对文本信息等其他非数值属性进行处理。故本文在处理查询结果的过程中利用Skyline方法来对数值属性进行处理，从而实现个性化查询的目标，使其更加满足用户的需求。

2 问题定义和解决方案 2.1 问题定义

本文先通过一个例子说明要解决的问题。图2给出了9个空间对象，空心圆代表空间对象，每个空间对象包含的文本关键字和数值属性信息如表2所示。

对于一个给定的空间关键字查询q(图2中的三角形表示)，目的是寻找距离查询位置最近，提供“chicken”食品，具有“价格低”、“噪声小”且“不拥挤”等特点的“KFC”店。如果进行严格的文本匹配，则没有满足条件的对象。但实际上，KFC与McDonald语义相似，故o₂、o₄、o₇可作为考虑对象；进而，这三者相比，o₄距查询位置最近，o₇在数值属性上优于o₄，o₇在价格属性上优于o₂，但o₂在噪声和拥挤度上明显优于o₇。在这种情况下，如果用户对价格的在意程度较低，则三者中最优的查询结果应该是o₂，反之，最优的查询结果应该是o₇。由此可见，空间对象中包含的数值信息以及用户对数值信息的重视程度，对于空间关键字查询也至关重要，并且其处理方法与文本关键字的匹配处理方法完全不同。

给定一个空间数据集O={o₁, o₂,…,o_n}，O中的每个对象o_i由一个三元组(λ, K, A)表示，其中o_i.λ是对象o_i的位置信息，o_i.K是o_i中的文本关键字集合，o_i.A是o_i中的数值属性集合，o_i.A中的o.a_i标准化到[0,1]之间。假设这些数值属性的值越小越好，如：噪声低、价格低等。如果数值属性值越高越好，例如：环境氛围、评分等信息，则可以通过a_i=1−a_i将其转换。查询q由三元组(λ, K, W)表示，其中q.λ是查询条件的位置信息，q.K是查询关键字集合，q.W是不同数值属性的权重的集合和用户对于这些数值属性的偏好，q.w∈q.W, q.w≥0 (i=1,2,···,|q.W|)并且 $\displaystyle\sum\limits_{i = 1}^{|q.W|} {q.{w_i}} = 1$ 。为每个数值属性赋权重而不是限定属性的精确查询范围，目的是为了实现数值属性上的模糊查询。

2.2 解决方案

本文提出的解决方案如图3所示，可分为2步：

1)对于用户发起的查询q=(λ, K, W)，根据离线阶段计算的语义相关性和字符串相似度，将满足条件的关键字拓展到查询关键字的集合中；

2)构建AIR-Tree混合索引结构，对查询条件与数据库中的空间对象进行位置相近性、文本相似度和数值接近度的计算，根据最终得分筛选出最符合用户需求的top-k个结果。

3 查询与结果的相关性评估

查询条件与空间对象的相关性，主要包括位置相近度、字符串相似度、语义相关性、文本相似度和数值接近度。

3.1 位置相近度

给定一个查询q与空间对象o，它们的位置相近度计算方法如下：

${S_D}\left( {q{\rm{,}}o} \right) = 1 - \frac{{{\rm{dist}} (q.\lambda ,o.\lambda )}}{{{D_{{\rm{Max}}}}}}$

(1)

式中：dist(q.λ,o.λ)为空间对象o与查询q的欧氏距离；D_Max为所有对象集合O中的最大距离。

对于表2中的空间对象，可以计算出对象集合O中的最大距离D_Max为92.1394，故查询位置与所有空间对象之间的距离分别为：0.6728、0.9248、0.6713、0.9313、0.6729、0.0000、0.9278、0.6367、0.6365。

3.2 字符串相似度

查询q与空间对象o中文本信息的字符串相似度可通过式(2)计算：

${S_F} = 1 - \frac{{{\rm{ld}} (q.s,o.s)}}{{\max ({\rm{len}} (q.s),{\rm{len}} (o.s))}}$

(2)

式中：ld(q.s,o.s)为q与o对应关键字之间的编辑距离；len()是求字符长度的函数；max(len(q.s), len(o.s))为q与o对应关键字长度的最大值。

对于查询条件“KFC, chicken”，假设用户输入的是“KCF, chicken”，则其字符串相似度为0.8182。

3.3 语义相关度

首先通过Skip-gram模型的Word Embedding技术对查询关键字进行扩展。Skip-gram模型的训练目标是找到对预测句子或文档中的周围单词有用的单词表示。给定一系列训练单词w₁，w₂，···，w_T，Skip-gram模型的目标是最大化平均对数概率，即

$\frac{1}{T}\sum\limits_{t = 1}^T {\sum\limits_{ - c \leqslant j \leqslant c,j \ne 0} {\log p({{{w}}_{{{t}} + {{j}}}}|{{{w}}_{{t}}})} } $

(3)

式中c是训练上下文的大小(可以是中心词w_t的函数)。较大的c导致更多训练示例，因此可以以训练时间为代价来获得更高的准确性。基本的Skip-gram公式使用softmax函数定义p(w_t+j |w_t)，其中softmax函数为

$p({{{w}}_{{O}}}|{{{w}}_{{I}}}) = \frac{{\exp ({{v'}}{{^{\rm{T}}_{{{{w}}_{{O}}}}}}{{{v}}_{{{{w}}_{{I}}}}})}}{{\displaystyle\sum\limits_{w = 1}^W {\exp ({{v'}}{{^{\rm{T}}_{{w}}}}{{{v}}_{{{{w}}_{{I}}}}})} }}$

(4)

式中： ${{{v}}_{{{{w}}_{{I}}}}}$ 和 ${{{v}}_{{{{w}}_{{O}}}}} $ 是w的向量表示的输入和输出向量；W是词汇表中的单词个数。由于其计算代价▽lg p(w_O|w_I)正比于W，该数一般情况下很大(10⁵~10⁷)。

虽然噪声对比度估计(noise comparison evaluation, NCE)可近似地最大化softmax的对数概率，但是Skip-gram模型只关心学习高质量的向量表示，因此只要向量表示保持其质量，就可以自由地简化NCE。负采样(NEG)的目标函数为

$\log \sigma ({{v}}{_{{{{w}}_{{O}}}}'^{\rm T}}{{{v}}_{{{{w}}_{{I}}}}}) + \sum\limits_{i = 1}^k {{{\rm E}_{{{{w}}_{{i}}}\sim{P_n}({{w}})}}} [\log \sigma ( - {{v}}{_{{{{w}}_{{i}}}}'^{\rm T}}{{{v}}_{{{{w}}_{{I}}}}})]$

(5)

NCE和NEG均将噪声分布P_n(w)作为一个随机参数。文献[26]研究了P_n(w)的多种选择，发现unigram分布U(w)提高到U(w)^3/4/Z时在NCE和NEG的每个任务上都明显优于unigram和均匀分布。因此本文也采用该值作为P_n(w)的默认值。

为了解决罕见词和频繁词之间的不平衡，本文采用了一种简单的下采样方法：将训练集中的每个单词w_i丢弃，丢弃概率的计算公式为

$P({{{w}}_{{i}}}) = 1 - \sqrt {\frac{t}{{f({{{w}}_{{i}}})}}} $

(6)

式中：f(w_i)为单词w_i的频率；t为所选阈值，一般在10⁻⁵左右。该下采样公式能够对频率大于t的单词进行下采样，同时保留频率的排序。

对于图2中的例子，利用词嵌入技术得到的扩展关键字查询为{Chicken，KFC，McDonald}。进而，如果空间对象的文本中也包含了Chicken或McDonald，其在语义上也与初始查询关键字十分相关，因此也可能是候选查询结果。

3.4 文本相似度

空间对象o与查询q的文本相似度评估的基本思想是，先将空间对象文本和查询关键字进行向量化处理，分别用V_o和V_q表示，再利用Cosine 相似度方法计算文本相似性，计算方法为

${S_T}\left( {o,q} \right) = \frac{{\displaystyle\sum\limits_{i = 1}^n {{{{V}}_{{o}}}[i] \cdot } {{{V}}_{{q}}}[i]}}{{\sqrt {\displaystyle\sum\limits_{i = 1}^n {{{{V}}_{{o}}}{{[i]}^2}} } \cdot \sqrt {\displaystyle\sum\limits_{i = 1}^n {{{{V}}_{{q}}}{{[i]}^2}} } }}$

(7)

现有的空间关键字查询仅在形式上匹配关键字，通常仅考虑文本相似度而未考虑查询与文本的语义相关度和拼写错误的情况。

对于表2中的空间对象，可以分别计算出查询关键字与其文本相似性为：0.0000、0.4082、0.0000、0.4082、0.0000、0.3333、0.4082、0.0000、0.0000。

3.5 Skyline

假设关系D有n个元组和m+1个数值，令Α={A₁, A₂,···, A_m}，t[A_i]为属性A_i上元组t的值。假设对于每一个属性，在支配关系dominate中的值有一个关于偏好的总的排序(例如，a>b表明值a优于值b)。一个元组t∈D支配另一个元组t'∈D，由 $t > t'$ 表示，当且仅当 $\forall A \in A$ , t[A]≥t'[A]和 $\exists A \in A$ , t[A]>t′[A]。另外，如果一个元组t∈D与另一个元组t′∈D是不可比的，则表示为t~t'，当且仅当 $t\not> {t'}$ 且 ${t'}\not> t$ 。

Skyline S是D中不被其他元组支配的元组集合。对于图2中的对象o₂、o₄、o₇，其数值属性可分别表示为{0.2，0.6，0.4}，{0.5，0.3，0.6}，{0.3，0.3，0.5}。若属性值越小越好，则由于o₇的第一、三个属性优于o₄，第二个属性与o₄的相等，可判断o₇支配o₄，再比较o₂、o₇，可知o₂的第一、三个属性优于o₇，第二个属性次于o₇，故o₂和o₇是不可比的，故都应该加入S中。

3.6 评价函数

本文首先使用式(2)对查询条件与空间对象关联的文档中的关键字进行字符串相似度计算，若查询关键字与文档中的关键字高于给定的字符串相似度阈值τ，则将该关键字扩展到查询关键字的集合中。字符串相似度计算的目的是解决由于查询关键字拼写错误而导致空查询结果的情况。

其次，根据离线阶段计算的语义相关性将满足给定阈值的关键字拓展到查询关键字的集合中，从而进行语义近似扩展。目前，普遍采用的空间对象o与查询q的相关度计算方法为

${S_1}\left( {q,o} \right) = \alpha \cdot {S_D}\left( {q,o} \right) + \left( {1 - \alpha } \right) \cdot {S_T}\left( {q,o} \right)$

(8)

式中α为调节参数。为了不失一般性，本文将其设置为0.5。

本文在此基础上加上了数值属性对查询结果的影响，所采用的空间对象o与查询q之间数值属性的相关度计算方法为

${S_2}\left( {q,o} \right) = 1{\rm{ - }}\sum\limits_{i = 0}^{|q.{W_i}|} {\left( {q.{W_i} \cdot o.{a_i}} \right)} $

(9)

式中：权重数组q.W_i是查询q对空间对象o的数值属性的看重程度；|q.W_i|是权重个数(也就是数值属性个数)；o.a_i是空间对象o的数值属性值。

最后使用评价函数，即用式(10)来计算最后的综合得分：

$S\left( {q,o} \right) = \beta \cdot {S_1}{\rm{ + }}\left( {1 - \beta } \right) \cdot {S_2}$

(10)

式中β为调节参数，本文设置为0.85。

4 查询匹配算法 4.1 索引结构

本文提出的索引结构主要分为语义层、AIR-Tree索引层。语义层首先使用式(2)计算查询q与空间对象关联文档集合中的关键字之间的字符串相似度，如果文档中的关键字与查询关键字的字符串相似度高于给定阈值，则对查询关键字进行扩展。然后，语义层首先通过Word Embedding技术，找到语义相关的关键字，然后对查询关键字进行语义扩展。扩展的查询关键字同时包含了字符串相似和语义相关的关键字。

在AIR-Tree索引层中，构建了一种新的索引结构(AIR-Tree)，即在IR-Tree的基础上为每个节点增加了AttrFile文件，见图4。AIR-Tree的每个节点记录了以该节点为根的子树中所有对象的空间信息、文本信息概要(从节点文本信息中抽取的关键字集合)、数值属性元组信息及指针，如图4所示。AIR-Tree中每个节点的信息分为3个部分：前两部分是两个指针，分别指向包含该节点所有关键字的倒排文件(InvFile)和数值属性文件(AttrFile)，第三部分是该节点中的实体集合(Entries)。每个非叶子节点和叶子节点都可能包含多个条目，对于叶子节点，它当中的每一个条目由一个四元组构成，形式为<O, R, t, a>，其中O代表空间对象，R代表该对象的最小外接矩形(MBR)，t是该对象的文本信息标识符，a是该对象的数值属性元组的标识符；对于非叶子节点，它当中的每一项也由一个四元组构成，形式为<p_N, R, p, a>，其中，p_N是该节点中孩子节点N的地址，R是指能够包含该节点下所有孩子节点的MBR，p是该节点的文档标识符，文档包含了该节点下所有子节点的信息概要，a是该节点的数值属性标识符，包含了该节点下所有子节点的数值属性元组的Skyline集合。

在查询过程中，利用算法1中AIR-Tree索引结构对POI兴趣点的位置信息、文本信息以及数值属性进行top-k查询。首先使用式(8)计算出与查询条件中位置信息以及关键字信息的相关度，其次使用式(9)计算出数值属性相关性，再使用式(10)计算出最后综合分数，最后按照综合得分对查询结果进行排序，使其筛选出最符合用户需求的前k个结果，从而使得查询结果更个性化。

4.2 相关算法

本节给出AIR-Tree索引中用到的函数以及算法。首先，需要在离线阶段计算AIR-Tree每个节点所对应的Skyline集合，实现方法如算法1所示。

算法1　skyline(L)

输入　数值属性列表L；

输出　数值属性列表L。

1)对L按照第一个属性的值从小到大排序

2)令i = 0

3) for每个在L列表中的元素元组t

4) while i<t.size() do

5) if t[i]<=t₁[i] then /*将t[i]与L中其他元组t₁的第i个元素t₁[i]相比*/

6) L.remove(t₁) /*将其他元组t₁从列表中移除*/

7) i += 1

8) else

9) L.remove(t)

10) return L

算法1可以为用户提供独立于其他数据项的数据项。在查询过程中，数值接近度S₂由Skyline和用户指定的权重决定，从而决定着哪个分支被选中而加快查找速度。对于一个给定的数值属性列表L，根据其第一个属性的大小正序排序。L中的每一个元组的值都会被逐列比较，如果一个元组的每一列都比其他元组的该列大，则将该元组从L中移除，直到不再存在这样的元组为止。

对于一个给定的空间关键字查询，利用AIR-Tree索引结构获取候选查询结果的实现算法如算法2所示。

算法2　候选集结果生成算法search(q, k, α, β, W[i])

输入　数据集D，扩展后的查询条件q，返回结果个数k，调节参数α，β，权重数组W[i]；

输出　候选集列表R。

1) R←ϕ，最大堆H←ϕ，h_E←ϕ

2) H.add(r) /*r为根节点*/

3) while H≠ϕ并且R.size()<k do

4) N=H.poll()

5) if N is an object then

6) R.add(N)

7) S = 1

8) else

9) for entry e in N

10) h_E.add(e)

11) if q.K中包含h_E.getId().getKeyword() then

12)用式(8)计算位置信息与关键字信息之间的耦合相关度的分数S₁

13) for每个h_E.getId()

14)根据节点的AttrFile，将其数值属性的元组信息添加到候选元组列表c_t列表中

15) s_t←skyline(c_t) /*计算skyline元组列表s_t的Skyline集合*/

16) for 每个在s_t中的元素t

17) ${S_2}\left( {q,o} \right) = 1{\rm{ - }}\displaystyle\sum\limits_{i = 0}^n {\left( {W[i]*t[i]} \right)} $

18)利用式(10)计算出S

19) H.add(h_E)/*H按照S排序*/

20) return R

算法2用于查找top-k个最符合用户需求的候选集。首先，使用离线阶段训练好的Word Embedding技术和字符串相似度计算方法对查询关键字进行扩展，然后使用离线阶段构建好的AIR-tree来查找与查询条件最接近的空间对象。首先，根节点r被添加到最大堆H中，如果该节点是空间对象(即叶子节点)，则将其添加到R中，S设置为1。否则，即为中间节点，然后中序遍历该树，将其孩子节点添加到h_E中。如果h_E中的叶子节点包含扩展后的查询关键字，则使用式(8)计算S₁，根据其AttrFile，将其数值属性的元组信息添加到候选元组列表s_t中，计算s_t的Skyline集合，对于每个在s_t中的元素t，使用式(9)计算S₂。最后使用式(10)计算最终得分S。最后，将h_E添加到H中，并且迭代，直到H为空或者R中元素个数大于k。

算法1的复杂度分析：令n=H.size()，m=s_t.size()，则由以上算法分析可得其时间复杂度为O(kmn)，其中k表示查询结果个数。

5 效果与性能实验评价

本节主要通过在真实数据集上进行实验来验证本文所提出算法的性能。

5.1 实验设置

本实验通过Pytorch实现Word Embedding，其中负采样随机采样数量K为100，指定周围单词数C为3进行预测，迭代轮数为2，每轮迭代1个batch的数量为128，词汇表的大小设置为30000，学习率为0.000 1，词向量维度为100作为超参数。从文本文件中读取所有的文字，通过这些文本创建一个vocabulary，由于单词数量可能太大，故只选取最常见的30 000个单词，同时添加一个<unk>单词表示最不常见的单词。本文使用Adam作为优化器来优化模型。

本文利用Skip-gram模型的词嵌入技术在Yelp数据集上进行训练，可以得到查询关键字与其语义相关的关键字，如表3所示。

根据表3的结果可以判定Word Embedding技术有较好的语义近似处理能力。

本实验所使用的第1个数据集为从Yelp商户点评网站上抓取的真实的POI数据集，Yelp是美国著名商户点评网站，其网站包含了各地餐馆、购物中心、酒店等各个领域的商户信息以及用户评价和签到时间等信息。将这些真实POI数据处理成174567个兴趣点，使得每个POI兴趣点都有一个ID、位置信息(以经纬度的形式表示)、文本信息、数值属性。将位置信息作为空间信息，用户评论信息和category作为文本信息，随机产生的5个0~1之间的随机数作为数值属性。

第2个数据集来自基于位置的服务平台Foursquare。数据清理后，数据集包含215614个与地理位置相关的对象、关键字列表以及数值属性的标准化值。每个空间对象包含经纬度信息、关键字信息，如牛排、披萨、咖啡等，以及4个数值属性，即价格、环境、服务和评级。

参数的默认值在表4中给出。在实验过程中，通过改变一个参数的值，固定其他参数的值来研究该参数对实验结果的影响。所有实验都采用Java实现，电脑配置为CPU i7-8700K3.7 GHz，32 GB内存，Ubuntu 18.04.1操作系统。

5.2 实验结果与分析

本节主要研究在相同数据集上，表4中各参数分别对AIR-Tree、IR-Tree以及IRS-Tree在查询效率和查询效果上的评估。“索引(Y/F)”表示该索引结构在Yelp/Foursquare数据集上进行的实验。

5.2.1 查询效率方面的实验

1) k对查询响应时间的影响

该实验的目的是通过设置k的值为10~60来观测查询结果个数对系统响应时间的影响。从图5可知，在相同的数据集上无论哪种算法，k值越大，系统响应时间越久。这是因为k值越大，越多的候选对象被索引，返回越多条与查询条件相近的POI空间对象，因此查询时间越久。此外，IR-Tree的查询响应时间最短，因为它既没有考虑数值属性，也没考虑拼写错误的情况，更无需考虑与查询关键字语义相关的关键字查询，因此查询时间最短；其次是AIR-Tree，原因是它需要利用Skyline查询方法对数值属性进行处理；耗时最久的是IRS-Tree，因为它要求数值属性的精确范围来完成查询匹配，增加了查询成本，故耗时最久。综上所述，当k值增大时，AIR-Tree索引的查询效率较高，相比于IRS-Tree提高了3.6%。

由于在Foursquare和Yelp上的实验结果相差甚微，故本节剩余部分只展示在Yelp数据集上的实验结果。

2) |o.A|对查询响应时间的影响

该实验的目的是通过改变数值属性的个数来验证其对查询响应时间的影响。本文通过改变|o.A|的值从1~5来观测其对查询响应时间的影响，如图6。实验结果表明，随着数值属性个数的增加，查询时间也逐渐增加。这是由于AIR-Tree在查询结果中需要对数值属性的元组进行Skyline计算，在最坏情况下，Skyline方法几乎会将每个元组中的每个元素进行比较，因此数值属性个数越多，越耗费时间。IRS-Tree比AIR-Tree耗时，因为IRS-Tree在处理数值属性时，考虑数值属性的精确范围，若范围设置过大，则会非常耗时。综上可见，当数值属性的个数增多时，AIR-Tree查询效率最佳。

3) |q.K|对查询时间的影响

该实验的目的是通过设置查询关键字的数量从1~7来观测其对查询响应时间的影响。由图7可知，查询响应时间与查询关键字的个数成正比增长。因为无论哪种索引结构，当查询关键字增多时，则索引到的包含查询关键字的对象越多，因此查询时间会增加。

4) |D|对查询时间的影响

该实验的目的是通过设置数据集大小从1, 2,···, 200000来观测数据集大小对查询响应时间的影响。从图8可知，查询响应时间随着数据集的增加而增加。这是因为数据集越大，需要索引的对象越多，并且在处理数值属性的过程中可能需要耗费更多的时间。

5.2.2 效果方面的实验

1) |D|与构建索引时间的关系

该实验的目的是测试在相同数据集上，通过改变数据集的大小，从1, 2,···, 200000来比较以上几种算法构建索引所用时间，以评价其性能。由图9可知，索引构建时间与数据集的大小成正比。其中构建IR-Tree所用时间最少，这是因为IR-Tree与AIR-Tree、IRS-Tree相比，不需要构建AttrFile文件和synopses，因此其索引构建时间最短。而IRS-Tree需要将synopses Tree与其他索引结合来完成查询，故其索引构建时间最长。

2) τ与查询准确率的关系

AIR-Tree是一个高维近似查询索引，对于一些给定的查询q可以得到一些语义相关结果。本文使用准确率P来评估查询效果，计算公式为

$P = \frac{{|I(q) \cap R(q)|}}{{|I(q)|}}$

(11)

式中：I(q)是距离查询q最近的top-k个对象的理想集合；R(q)是本文提出算法所返回的结果集。这里，为了获取更具有鲁棒性的准确率，将返回结果数设置为100。由图10可知：当τ<0.55时，准确率随着字符串相似度的增大而增大；当τ≥0.55时，准确率不再发生改变并保持在85%左右。

3) k与查询准确率的关系

通过设置k来查看其对查询准确率的影响，本文设置k区间为[10, 100]，步长为10。由图11可知，本文所提算法AIR-Tree较IR-Tree、IRS-Tree分别在准确率上提高了10.14%和16.15%。

6 结束语

针对现有空间关键字查询处理模式仅支持位置相近和文本匹配，但未考虑语义信息，且不能处理数值属性的问题，提出了一种支持语义近似查询处理的空间关键字查询方法。本文研究了通过Word Embedding中的Skip-gram模型来实现空间对象的语义近似查询的方法，并且利用Skyline查询方法实现了查询结果的个性化。实验结果表明，本文提出的算法不仅支持空间关键字的精确匹配，支持语义近似查询和形式上的近似匹配，且能处理文本信息中的数值属性，这样更符合用户查询要求，在一定程度上提高了用户体验以及满意度。

在未来的工作中，将会利用深度学习的方法研究路网上的移动对象的集合关键字查询。