4.6 研究现状及关键技术

在大部分基于路网的空间关键词查询研究中，路网以有向图的形式表示，即 G=(V,E)，其中 V 表示路网中的交叉结点或者根据计算需要人为引入的结点；E 表示连接结点与结点之间的有向边。城市空间文本数据则由大量带有位置属性和文本属性的空间文本对象（Spatio-Textual Objects）组成。空间文本对象可以是物理世界中的实体对象，如商店和公共设施；也可以是各类和实体对象相关联的虚拟对象，如针对实体对象的广告和网络评论。每个空间文本对象表示为 o=(loc, t), 其中 loc 是对象的空间位置 ( 即经纬度 )、t 是对象的文本描述。基于路网的空间关键词查询则结合路网和大量的空间文本对象提供各类查询服务。

基于路网的空间关键词查询的具体查询种类很多，大致可以分为两大类，即通用查询和复杂查询。通用查询主要包括布尔范围查询、布尔 kNN 查询和top-k 查询。具体地，布尔范围查询查找给定范围内包含查询关键词的所有空间文本对象；布尔 kNN 查询查找包含查询关键词并且网络距离最近的 k 个空间文本对象；top-k 查询查找网络距离和文本相似性综合最优的 k 个空间文本对象，其中文本相似性采用信息检索模型计算，如 TF-IDF 模型。

复杂查询主要包括倒转查询[12,18] 、连续查询[14-15]和组合查询[14,19] 。其中，倒转查询查找那些范围查询或者 top-k 查询中包含给定查询对象的对象；连续查询中查询位置不断变化，需要实时更新位置变化后的查询结果；组合查询则要求查询结果包含多类查询对象，同时优化这些对象之间的距离。此外，结合传统的路径查询和关键词查询，可以定义大量路网特有的查询，如基于关键词的最优路径查询[2] 。

实现快速有效的基于路网的空间关键词查询处理需要解决一系列的挑战，主要包括：

● 城市空间文本数据的规模大：城市空间文本数据的规模很大，因为它包含各类带有空间位置信息的数据。如何将这些数据组织存储起来，建立有效的索引结构，并利用索引结构实现快速的查询处理是所有大数据查询面对的主要挑战之一。

● 数据异构性：在基于路网的空间关键词查询中，涉及文本数据、空间数据和图数据等数据类型。这些类型的数据的处理方式存在很大的差别，很难用一个通用的模型来消除这种差异性。

● 大量的网络距离计算：由于查询基于路网结构，所以需要大量的路径计算。与计算两点之间的欧式距离相比，计算两点之间的网络距离的复杂度要高很多。这就增加了实时处理基于路网的空间关键词查询的难度。

● 存在大量 NP 难的查询问题：在已有的基于路网的空间关键词查询中，有很大一部分查询问题是 NP 难的。这就意味着在现有的算法复杂性体系下无法设计具有多项式时间复杂度的查询算法。如何在保证查询质量的前提下有效处理这类查询 , 是基于路网的空间关键词查询研究中的一个难点。

为了减少这些挑战，现有研究工作采用的主要技术包括：

(1) 先进的索引技术为了减少大规模数据带来的时间和空间开销，索引技术是最主要的手段。在基于路网的空间关键词查询中，需要用到图索引技术、文本索引技术、空间索引技术以及空间文本混合索引技术。将这些索引技术融合起来，为查询提供统一的索引机制是解决基于路网的空间关键词查询问题的核心思想。

(2) 快速查询处理技术设计高效的查询处理算法是基于路网的空间关键词查询最主要的任务。一方面，在查询处理过程中，利用构建的索引结构加快查询的处理速度，同时优化查询的处理流程可以在很大程度上降低数据搜索的范围，进而减少计算量。另一方面，利用先进的网络距离计算技术（如 CH [21] 和SILC [22] ）可以加速最短路径计算，从而降低整体的查询处理时间。

(3) 剪枝技术在复杂的查询处理中，剪枝技术始终扮演者重要的角色，因为它可以显著加快查询处理的进度。好的剪枝技术需要在查询处理的过程中生成好的上下界，即与真实值比较接近。在基于路网的空间关键词查询中，通过利用路网中距离之间的三角不等关系、欧式距离和网络距离之间的关系，同时结合具体的查询目标，可以生成较优的上下界，从而有效去掉大量的非最优解，达到优化查询速度的目的。