第15卷第2期 智能系统学报 Vol.15 No.2 2020年3月 CAAI Transactions on Intelligent Systems Mar.2020 D0:10.11992/tis.201808011 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20190524.0952.004.html 基于位置-文本关系的空间对象0p-k查询与排序方法 孟祥福，张霄雁，赵路路，李盼，毕崇春 (辽宁工程技术大学电子与信息工程学院，辽宁葫芦岛125105)】 摘要：针对普通的空间关键字查询通常会导致多查询结果的问题。本文提出了一种基于空间对象位置文本 相关度的to-k查询与排序方法，用于获取与给定空间关键字查询在文本上相关且位置上相近的典型空间对 象。该方法分为离线处理和在线查询处理2个阶段。在离线阶段，根据空间对象之间的位置相近性和文本相 似性，度量任意一对空间对象之间的位置-文本关系紧密度。在此基础上，提出了基于概率密度的代表性空间 对象选取算法，根据空间对象之间的位置-文本关系为每个代表性空间对象构建相应的空间对象序列。在线查 询处理阶段，对于一个给定的空间关键字查询，利用Cosine相似度评估方法计算查询条件与代表性空间对象之 间的相关度，然后使用阈值算法(threshold algorithm,TA)在预先创建的空间对象序列上快速选出top-k个满足 查询需求的典型空间对象。实验结果表明：提出的空间对象t©即-k查询与排序方法能够有效地满足用户查询需 求，并且具有较高的准确性、典型性和执行效率。 关键词：空间数据库；空间关键字查询：位置-文本关系：概率密度；代表性对象选取；to叩-k查询与排序 中图分类号：TP311.1文献标志码：A文章编号：1673-4785(2020)02-0235-08 中文引用格式：孟祥福，张霄雁，赵路路，等.基于位置-文本关系的空间对象to-k查询与排序方法J.智能系统学报，2020， 15(2):235-242. 英文引用格式：MENG Xiangfu,ZHANG Xiaoyan,ZHAO Lulu,et al.A location--text correlation-based top--k query and ranking approach for spatial objects[Jl.CAAI transactions on intelligent systems,2020,15(2):235-242. A location-text correlation-based top-k query and ranking approach for spatial objects MENG Xiangfu,ZHANG Xiaoyan,ZHAO Lulu,LI Pan,BI Chongcun (School of Electronic and Information Engineering,Liaoning Technical University,Huludao 125105,China) Abstract:Due to the large size of spatial databases,a common spatial keyword query often leads to the problem of too many answers.To deal with this problem,this paper proposes a location-text correlation-based top-k query and ranking approach for spatial objects,which aims to find the typical spatial objects with high text relevancy and location proxim- ity.This approach consists of offline processing and online query steps.The offline step scores the relationship between any pair of spatial objects by considering their location proximity and text similarity.Then,by using a probabilistic density-based representative spatial object selection method,a set of representatives over the spatial objects is selected to build a corresponding spatial object sequence.In the online query period,when a user issues a spatial keyword query, the location-text correlation between the query and representative objects is evaluated,and then,the top-k typical relev- ant objects can be expeditiously picked using the threshold algorithm (TA)algorithm over the sequences corresponding to representative spatial objects.The experiments demonstrate that the proposed top-k query and ranking approach can closely meet users'needs,with high precision,typicality,and good performance. Keywords:spatial database;spatial keyword query;location-text correlation;probability density;representative object selection;top-k query and ranking 收稿日期：2018-08-12.网络出版日期：2019-05-27. 基金项目：国家自然科学基金面上项目(61772249)：辽宁省自 随着Internet的普遍应用，对于兴趣点(point 然科学基金项目(20170540418)：辽宁省教育厅科学 研究项目(LJYL018). of interests,POIs,如餐厅、电影院、旅馆、旅游景 通信作者：孟祥福.E-mail:marxi(@126.com 点等)的空间关键字查询已成为当前空间数据库
DOI: 10.11992/tis.201808011 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20190524.0952.004.html 基于位置−文本关系的空间对象 top-k 查询与排序方法 孟祥福，张霄雁，赵路路，李盼，毕崇春 （辽宁工程技术大学 电子与信息工程学院，辽宁 葫芦岛 125105） 摘 要：针对普通的空间关键字查询通常会导致多查询结果的问题。本文提出了一种基于空间对象位置-文本 相关度的 top- k 查询与排序方法，用于获取与给定空间关键字查询在文本上相关且位置上相近的典型空间对 象。该方法分为离线处理和在线查询处理 2 个阶段。在离线阶段，根据空间对象之间的位置相近性和文本相 似性，度量任意一对空间对象之间的位置-文本关系紧密度。在此基础上，提出了基于概率密度的代表性空间 对象选取算法，根据空间对象之间的位置-文本关系为每个代表性空间对象构建相应的空间对象序列。在线查 询处理阶段，对于一个给定的空间关键字查询，利用 Cosine 相似度评估方法计算查询条件与代表性空间对象之 间的相关度，然后使用阈值算法（threshold algorithm，TA）在预先创建的空间对象序列上快速选出 top- k 个满足 查询需求的典型空间对象。实验结果表明：提出的空间对象 top- k 查询与排序方法能够有效地满足用户查询需 求，并且具有较高的准确性、典型性和执行效率。 关键词：空间数据库; 空间关键字查询；位置-文本关系；概率密度；代表性对象选取；top-k 查询与排序 中图分类号：TP311.1 文献标志码：A 文章编号：1673−4785(2020)02−0235−08 中文引用格式：孟祥福, 张霄雁, 赵路路, 等. 基于位置-文本关系的空间对象 top-k 查询与排序方法 [J]. 智能系统学报, 2020, 15(2): 235–242. 英文引用格式：MENG Xiangfu, ZHANG Xiaoyan, ZHAO Lulu, et al. A location-text correlation-based top-k query and ranking approach for spatial objects[J]. CAAI transactions on intelligent systems, 2020, 15(2): 235–242. A location-text correlation-based top-k query and ranking approach for spatial objects MENG Xiangfu，ZHANG Xiaoyan，ZHAO Lulu，LI Pan，BI Chongcun (School of Electronic and Information Engineering, Liaoning Technical University, Huludao 125105, China) Abstract: Due to the large size of spatial databases, a common spatial keyword query often leads to the problem of too many answers. To deal with this problem, this paper proposes a location-text correlation-based top- k query and ranking approach for spatial objects, which aims to find the typical spatial objects with high text relevancy and location proximity. This approach consists of offline processing and online query steps. The offline step scores the relationship between any pair of spatial objects by considering their location proximity and text similarity. Then, by using a probabilistic density-based representative spatial object selection method, a set of representatives over the spatial objects is selected to build a corresponding spatial object sequence. In the online query period, when a user issues a spatial keyword query, the location-text correlation between the query and representative objects is evaluated, and then, the top- k typical relevant objects can be expeditiously picked using the threshold algorithm (TA) algorithm over the sequences corresponding to representative spatial objects. The experiments demonstrate that the proposed top- k query and ranking approach can closely meet users' needs, with high precision, typicality, and good performance. Keywords: spatial database; spatial keyword query; location-text correlation; probability density; representative object selection; top-k query and ranking 随着 Internet 的普遍应用，对于兴趣点 (point of interests, POIs，如餐厅、电影院、旅馆、旅游景 点等) 的空间关键字查询已成为当前空间数据库 收稿日期：2018−08−12. 网络出版日期：2019−05−27. 基金项目：国家自然科学基金面上项目 (61772249)；辽宁省自 然科学基金项目 (20170540418)；辽宁省教育厅科学 研究项目 (LJYL018). 通信作者：孟祥福. E-mail：marxi@126.com. 第 15 卷第 2 期 智 能 系 统 学 报 Vol.15 No.2 2020 年 3 月 CAAI Transactions on Intelligent Systems Mar. 2020
·236· 智能系统学报 第15卷 的研究热点四。空间关键字查询条件的形式为： 含查询关键字的最终查询结果。该类方法的缺点 4{位置，} 是无法确定第1阶段产生的候选结果个数，当候 其中“位置”代表空间位置查询条件，可以是一个 选结果个数过少时，很可能会导致最终结果不能 空间点（通常用经纬度表示），也可以是一个空间 满足查询关键字的匹配需求，而候选结果过多 范围；“关键字”代表文本信息查询条件，通常用 时，又可能会导致计算资源的浪费。2)IR-tree索 若干关键字表示。空间数据库中的每个空间对 引9-o,1:该类索引将倒排文件集成到R-tree节点 象（也称为兴趣点）都包含2类信息：空间信息 中，当查询到来时，判断IR-tree节点与查询的位 (spatial information,.如经纬度)和文本信息(text in- 置距离以及该节点对应的倒排文件是否包含查询 formation,如POI的名称、设施、评论等文本描述 关键字。该类方法同时判断节点与查询的位置关 信息)。 系和文本匹配度，在很大程度上提升了查询效 由于空间数据库通常蕴含海量数据，因此一 率。该类方法的缺点是，对于满足查询位置要求 个普通空间关键字查询很可能会导致多查询结果 和（全部或部分）包含查询关键字的树节点都要 问题。例如，在Yelp网站上搜索“San Francisco” 进行遍历，从而得到候选结果集合，然后再按评 地理范围内的Chinese Restaurants'”,会返回ll08 分函数从中选取前k个综合分数最高的结果。 条查询结果。这种情况下，绝大多数用户期望空 3)Quad-tree索引4,1m:该类索引将倒排文件与 间数据库查询系统能够快速返回前k个与当前查 Quad-tree相结合，与IR-tree类似，在查询过程中 询在位置和文本上最为相关且具有代表性、典型 同时判断节点与查询的位置范围重叠程度以及节 性的结果。 点对应的倒排文件是否包含查询关键字。Quad- 近年来，有关空间关键字查询的研究工作在 tree索引的优点是区域搜索效率高，缺点是存储 些主流期刊和会议上涌现出来10。根据文献 代价高，树结构不平衡，top-k结果选取的耗时较 [2-3],这些查询方法可分为3类：1)布尔k近邻查 长。综上可见，给定一个空间关键字查询，现有 询6：该类方法用于检索文本描述信息中包含所 方法利用混合索引结构从空间对象集合中获取候 有查询关键字且距离查询位置最近的前k个空间 选结果，由于产生的候选结果数量通常多于最终 对象，查询结果按其对查询的位置相近性进行排 的top-k结果数量，并且在top-k结果选取中需要 序。2)top-k范围查询-8：用于检索位于查询区域 根据评分函数计算所有候选结果对象与当前查询 内且与查询关键字具有较高文本相似度的前k个 的位置与文本综合相关度才能确定最终结果，因 空间对象，查询结果按其对查询关键字的文本相 此topk选取效率仍有提升空间。此外，现有方法 似度进行排序。3)top-kk近邻查询B.9:该类方 按空间对象与查询的综合相关度获取top-k结果， 法根据空间对象的文本相似性和位置相近性进 结果之间往往比较相似，实际上用户希望看到既 行top-k检索和排序，查询结果按其对查询的位置 与查询相关且彼此之间又具有一定差异的代表性 相近性和文本相似度进行综合排序。上述3类方 查询结果。 法中，第3类是当前空间关键字查询最为常用的 针对现有空间关键字查询研究工作存在的问 方法。为了获取top-k查询结果，上述3类方法都 题，本文提出一种基于位置-文本关系的空间对 需要先从目标数据集中获取与查询位置相近且文 象top-k查询与排序方法，该方法可分为2个处理 本与查询关键字全部或部分匹配的候选结果，然 阶段：在离线阶段，计算空间对象集合中任意一 后再根据评分函数从候选结果中选取top-k个结 对空间对象之间的位置相近度和文本相似度，二 果。为了快速获取候选结果集合，上述方法通常 者结合构成空间对象的关系紧密度，然后根据空 采用空间索引与文本索引相结合的混合索引结 间对象之间的关系紧密度从空间对象集合中获取 构。空间搜索的索引技术主要有R-treel2、R* 少数代表性对象，并为每个代表性对象创建一个 tree和Quad-tree(四分树)等，其中R-tree是最 序列，序列中的元素是数据集中除该空间对象之 基本的空间索引结构。文本搜索的索引技术主要 外的所有空间对象，序列中的对象按其对代表性 有倒排文件(inverted file)、签名文件(signature 对象的关系紧密度降序排列。在线查询处理阶 file)和位图索引(bitmap)等。空间与文本索引相 段，对于一个给定的空间关键字查询，首先计算 结合的空间-文本数据混合索引结构可归为以下 该查询与每个代表性空间对象之间的关系紧密 几类：1)两阶段索引：该类索引先利用R-tree或 度，然后使用阈值算法(threshold algorithm,TA)在 Quad-tree获取与查询位置相近的候选结果，然后 预创建的序列上快速选出前k个与当前查询最为 再用倒排文件(inverted file)从候选结果中获取包 接近的空间对象，其中查询条件与代表性空间对
的研究热点[1]。空间关键字查询条件的形式为： q: {位置，＜关键字 1，关键字 2,···，关键字 m＞} 其中“位置”代表空间位置查询条件，可以是一个 空间点 (通常用经纬度表示)，也可以是一个空间 范围；“关键字”代表文本信息查询条件，通常用 若干关键字表示。空间数据库中的每个空间对 象 (也称为兴趣点) 都包含 2 类信息：空间信息 (spatial information，如经纬度) 和文本信息 (text information，如 POI 的名称、设施、评论等文本描述 信息)。 由于空间数据库通常蕴含海量数据，因此一 个普通空间关键字查询很可能会导致多查询结果 问题。例如，在 Yelp 网站上搜索“San Francisco” 地理范围内的“Chinese Restaurants”，会返回 1 108 条查询结果。这种情况下，绝大多数用户期望空 间数据库查询系统能够快速返回前 k 个与当前查 询在位置和文本上最为相关且具有代表性、典型 性的结果。 近年来，有关空间关键字查询的研究工作在 一些主流期刊和会议上涌现出来[2-10]。根据文献 [2-3]，这些查询方法可分为 3 类：1) 布尔 k 近邻查 询 [4-6] ：该类方法用于检索文本描述信息中包含所 有查询关键字且距离查询位置最近的前 k 个空间 对象，查询结果按其对查询的位置相近性进行排 序。2)top-k 范围查询[7-8] ：用于检索位于查询区域 内且与查询关键字具有较高文本相似度的前 k 个 空间对象，查询结果按其对查询关键字的文本相 似度进行排序。3)top-k k 近邻查询[3，9-11] ：该类方 法根据空间对象的文本相似性和位置相近性进 行 top-k 检索和排序，查询结果按其对查询的位置 相近性和文本相似度进行综合排序。上述 3 类方 法中，第 3 类是当前空间关键字查询最为常用的 方法。为了获取 top-k 查询结果，上述 3 类方法都 需要先从目标数据集中获取与查询位置相近且文 本与查询关键字全部或部分匹配的候选结果，然 后再根据评分函数从候选结果中选取 top-k 个结 果。为了快速获取候选结果集合，上述方法通常 采用空间索引与文本索引相结合的混合索引结 构。空间搜索的索引技术主要有 R-tree[12] 、R*- tree[13] 和 Quad-tree(四分树) [14] 等，其中 R-tree 是最 基本的空间索引结构。文本搜索的索引技术主要 有倒排文件 (inverted file)、签名文件 (signature file) 和位图索引 (bitmap) 等。空间与文本索引相 结合的空间-文本数据混合索引结构可归为以下 几类：1) 两阶段索引[15] : 该类索引先利用 R-tree 或 Quad-tree 获取与查询位置相近的候选结果，然后 再用倒排文件 (inverted file) 从候选结果中获取包 含查询关键字的最终查询结果。该类方法的缺点 是无法确定第 1 阶段产生的候选结果个数，当候 选结果个数过少时，很可能会导致最终结果不能 满足查询关键字的匹配需求，而候选结果过多 时，又可能会导致计算资源的浪费。2)IR-tree 索 引 [9-10, 16] ：该类索引将倒排文件集成到 R-tree 节点 中，当查询到来时，判断 IR-tree 节点与查询的位 置距离以及该节点对应的倒排文件是否包含查询 关键字。该类方法同时判断节点与查询的位置关 系和文本匹配度，在很大程度上提升了查询效 率。该类方法的缺点是，对于满足查询位置要求 和 (全部或部分) 包含查询关键字的树节点都要 进行遍历，从而得到候选结果集合，然后再按评 分函数从中选取前 k 个综合分数最高的结果。 3)Quad-tree 索引[14, 17] ：该类索引将倒排文件与 Quad-tree 相结合，与 IR-tree 类似，在查询过程中 同时判断节点与查询的位置范围重叠程度以及节 点对应的倒排文件是否包含查询关键字。Quadtree 索引的优点是区域搜索效率高，缺点是存储 代价高，树结构不平衡，top-k 结果选取的耗时较 长。综上可见，给定一个空间关键字查询，现有 方法利用混合索引结构从空间对象集合中获取候 选结果，由于产生的候选结果数量通常多于最终 的 top-k 结果数量，并且在 top-k 结果选取中需要 根据评分函数计算所有候选结果对象与当前查询 的位置与文本综合相关度才能确定最终结果，因 此 top-k 选取效率仍有提升空间。此外，现有方法 按空间对象与查询的综合相关度获取 top-k 结果， 结果之间往往比较相似，实际上用户希望看到既 与查询相关且彼此之间又具有一定差异的代表性 查询结果。 针对现有空间关键字查询研究工作存在的问 题，本文提出一种基于位置-文本关系的空间对 象 top-k 查询与排序方法，该方法可分为 2 个处理 阶段：在离线阶段，计算空间对象集合中任意一 对空间对象之间的位置相近度和文本相似度，二 者结合构成空间对象的关系紧密度，然后根据空 间对象之间的关系紧密度从空间对象集合中获取 少数代表性对象，并为每个代表性对象创建一个 序列，序列中的元素是数据集中除该空间对象之 外的所有空间对象，序列中的对象按其对代表性 对象的关系紧密度降序排列。在线查询处理阶 段，对于一个给定的空间关键字查询，首先计算 该查询与每个代表性空间对象之间的关系紧密 度，然后使用阈值算法 (threshold algorithm，TA) 在 预创建的序列上快速选出前 k 个与当前查询最为 接近的空间对象，其中查询条件与代表性空间对 ·236· 智 能 系 统 学 报 第 15 卷
第2期 孟祥福，等：基于位置-文本关系的空间对象opk查询与排序方法 ·237· 象之间的关系紧密度作为评分函数的权重，即当 12空间对象的文本相似度 前查询条件与某个代表性空间对象在位置和文本 给定一个空间对象o,其文本信息o.doc可由 上越接近，那么该代表性空间对象对应的序列对 对象0的名字、设施描述、用户评论所构成，本文 结果影响越大。该算法的优势在于：1)在线查询 利用jieba、wikipedia等工具先对空间对象的文本 处理阶段不需要检查所有与查询匹配的对象就能 信息进行关键字提取，进而o.doc将由一组关键 够快速识别出top-k结果。2)选取的top-k结果对 字集合表示，其中每个关键字都有一个权重w 象在全局中具有代表性，也就是典型化程度高。 (uo.doc),权重的计算方法采用传统的TF-IDF计 1 空间对象的位置-文本关系度量 算方法： w(tlo.doc)=tf(tlo.doc)*idf(t,O) (3) 本节分别讨论空间对象的位置相近度和文本 f(t,o.doc) 相似度的度量方法，二者的线性叠加构成了空间 式中：词频为ifo.doe)MaxFrequency.doc)表 对象之间的位置-文本关系紧密度。 示1在o.doc中出现的次数；MaxFrequency表示 表1给出了一个空间数据库实例，每行代表 在o.doc中关键字的最多出现次数；idft,O)=log 个空间对象。下文将以表1为例，阐述空间对 f0O+T其中f0)表示空间对象集合0中包含 象的位置相近度和本文相似度计算方法。 关键字1的对象数量；O1表示空间对象集合中的 表1空间数据库实例 对象总数。 Table 1 An instance of spatial database 在此基础上，给定一对空间对象(01,02)，其中 对象 纬度 经度 文本描述 每个对象的文本信息可转换成相应的向量表示， 0 116.36 39.91 泳池、wif、早餐 向量的维度是空间数据库中所有空间对象文本信 m 116.20 39.99 wif、早餐 息中包含的所有不同关键字个数。然后，利用 Cosine相似度评估方法得到一对空间对象的文本 03 110.5835.74 早餐、泳池、地铁 相似度，计算方法如下： 04 119.65 33.32 会议室、Internet、泳池 05 121.1642.58 Internet、接送机场、宠物 ∑，o,间 (4) 1.1空间对象的位置相近度 Simpoe(01,02)= 空间对象的位置信息通常由经纬度表示，现 有方法大多采用两个空间对象之间的欧氏距离来 式中：0，、02分别是对象01、02中关键字的向量 计算二者之间的位置相近度。给定一对空间对 表示。根据式(4)，数据集中任意一对空间对象之 象o.和o.它们之间的欧氏距离定义如下： 间的文本相似度都可以在离线阶段计算得到。表3 Doo）=∑do,oy (1) 给出了表1中所有对象的文本相似度。 k=1 其中n代表空间对象的空间维度。基于式(1)，空 表3空间对象的文本相似度 间对象0，和0，在位置上的相近度定义为： Table 3 The text similarity between spatial objects SimLoe(0:,0)=1-D(0:0)/MaxD (2) 02 0 0 05 其中MaxD代表所有空间对象之间的最大距离。 01 1.0000 0.9284 0.1713 0.0774 0.0000 式(2)得到的是一个归一化结果，即SimLO的值 02 0.9284 1.0000 0.0923 0.0000 0.0000 介于0和1之间。表2给出了表1中所有空间对 03 0.1713 0.0923 1.0000 0.0480 0.0000 象之间的位置相近度。 0.0774 0.0000 0.0480 1.0000 0.1751 表2空间对象的位置相近度 04 Table 2 The location proximity between spatial objects 05 0.0000 0.0000 0.0000 0.1751 1.0000 9 02 03 0a Os 1.3 空间对象的位置-文本关系紧密度 011.0000 0.9858 0.4343 0.4154 0.5640 空间对象0、0，在位置上的相近度和在文本 0.9858 1.0000 0.4407 0.4039 0.5559 上的相似度通过线性叠加构成了它们之间的关系 03 0.4343 0.4407 1.0000 0.2549 0.0000 紧密度，用Sim(op0)表示： Sim(o,0）=aSimLoe(o,0）+(1-a)Simpoe(o,0y）(5）) 04 0.4154 0.4039 0.2549 1.0000 0.2553 其中a是一个调节参数(a∈[0，l),a值越大，空间 05 0.5640 0.5559 0.0000 0.2553 1.0000 对象的位置相近度对总体紧密度的影响就越大；
象之间的关系紧密度作为评分函数的权重，即当 前查询条件与某个代表性空间对象在位置和文本 上越接近，那么该代表性空间对象对应的序列对 结果影响越大。该算法的优势在于：1) 在线查询 处理阶段不需要检查所有与查询匹配的对象就能 够快速识别出 top-k 结果。2) 选取的 top-k 结果对 象在全局中具有代表性，也就是典型化程度高。 1 空间对象的位置-文本关系度量 本节分别讨论空间对象的位置相近度和文本 相似度的度量方法，二者的线性叠加构成了空间 对象之间的位置-文本关系紧密度。 表 1 给出了一个空间数据库实例，每行代表 一个空间对象。下文将以表 1 为例，阐述空间对 象的位置相近度和本文相似度计算方法。 表 1 空间数据库实例 Table 1 An instance of spatial database 对象 纬度 经度 文本描述 o1 116.36 39.91 泳池、wifi、早餐 o2 116.20 39.99 wifi、早餐 o3 110.58 35.74 早餐、泳池、地铁 o4 119.65 33.32 会议室、Internet、泳池 o5 121.16 42.58 Internet、接送机场、宠物 1.1 空间对象的位置相近度 空间对象的位置信息通常由经纬度表示，现 有方法大多采用两个空间对象之间的欧氏距离来 计算二者之间的位置相近度。给定一对空间对 象 oi 和 oj，它们之间的欧氏距离定义如下： D(oi , oj) = ∑n k=1 d(o (k) i , o (k) j ) (1) 其中 n 代表空间对象的空间维度。基于式 (1)，空 间对象 oi 和 oj 在位置上的相近度定义为： SimLoc(oi , oj) = 1− D(oi , oj)/MaxD (2) 其中 MaxD 代表所有空间对象之间的最大距离。 式 (2) 得到的是一个归一化结果，即 SimLoc() 的值 介于 0 和 1 之间。表 2 给出了表 1 中所有空间对 象之间的位置相近度。 表 2 空间对象的位置相近度 Table 2 The location proximity between spatial objects o1 o2 o3 o4 o5 o1 1.000 0 0.985 8 0.434 3 0.415 4 0.564 0 o2 0.985 8 1.000 0 0.440 7 0.403 9 0.555 9 o3 0.434 3 0.440 7 1.000 0 0.254 9 0.000 0 o4 0.415 4 0.403 9 0.254 9 1.000 0 0.255 3 o5 0.564 0 0.555 9 0.000 0 0.255 3 1.000 0 1.2 空间对象的文本相似度 给定一个空间对象 o，其文本信息 o.doc 可由 对象 o 的名字、设施描述、用户评论所构成，本文 利用 jieba、wikipedia 等工具先对空间对象的文本 信息进行关键字提取，进而 o.doc 将由一组关键 字集合表示，其中每个关键字都有一个权重 w (t|o.doc)，权重的计算方法采用传统的 TF-IDF 计 算方法： w(t|o.doc) = tf(t|o.doc) ∗ idf(t,O) (3) tf(to.doc)= f(t, o.doc) MaxFrequency f(t|o.doc) idf(t,O) =log |O| f(t|O)+1 f(t|O) 式中：词频为 ； 表 示 t 在 o.doc 中出现的次数；MaxFrequency 表示 在 o.doc 中关键字的最多出现次数； ，其中 表示空间对象集合 O 中包含 关键字 t 的对象数量；|O|表示空间对象集合中的 对象总数。 在此基础上，给定一对空间对象 (o1，o2 )，其中 每个对象的文本信息可转换成相应的向量表示， 向量的维度是空间数据库中所有空间对象文本信 息中包含的所有不同关键字个数。然后，利用 Cosine 相似度评估方法得到一对空间对象的文本 相似度，计算方法如下： SimDoc(o1, o2)= ∑n i=1 o1[i]o2[i] √∑n i=1 o1[i] 2 ∗ √∑n i=1 o2[i] 2 (4) ⇀ o1 ⇀ 式中： 、 o2 分别是对象 o1、o2 中关键字的向量 表示。根据式 (4)，数据集中任意一对空间对象之 间的文本相似度都可以在离线阶段计算得到。表 3 给出了表 1 中所有对象的文本相似度。 表 3 空间对象的文本相似度 Table 3 The text similarity between spatial objects o1 o2 o3 o4 o5 o1 1.000 0 0.928 4 0.171 3 0.077 4 0.000 0 o2 0.928 4 1.000 0 0.092 3 0.000 0 0.000 0 o3 0.171 3 0.092 3 1.000 0 0.048 0 0.000 0 o4 0.077 4 0.000 0 0.048 0 1.000 0 0.175 1 o5 0.000 0 0.000 0 0.000 0 0.175 1 1.000 0 1.3 空间对象的位置-文本关系紧密度 空间对象 oi、oj 在位置上的相近度和在文本 上的相似度通过线性叠加构成了它们之间的关系 紧密度，用 Sim(oi , oj ) 表示： Sim(oi , oj) = αSimLoc(oi , oj)+(1−α)SimDoc(oi , oj) (5) 其中 α 是一个调节参数 (α∈[0,1])，α 值越大，空间 对象的位置相近度对总体紧密度的影响就越大； 第 2 期 孟祥福，等：基于位置−文本关系的空间对象 top-k 查询与排序方法 ·237·
·238· 智能系统学报 第15卷 反之，空间对象在文本上的相似度对总体紧密度 函数评估某个空间对象在整个对象集合中的概率 的影响越大。需要指出的是，利用式(5)得到的 密度，某个对象的概率密度越大，表明与其关系 空间对象之间的位置-文本关系紧密度在[0,1]范 紧密的对象越多，则该对象也就越有代表性，即 围内。表4给出了表1中所有空间对象的位置- 典型程度越高。本文采用概率密度估计算法从 文本关系紧密度（其中=0.5）0 空间对象集合中选取代表性对象。 表4空间对象的位置-文本关系紧密度 对于一个空间对象集合0={01,02，…，0n},对 Table 4 The location-text closeness between spatial objects 象o的概率密度，)可以表示为： 01 02 9 0a 0s 1 fo)=1G0.0= 1了e学 (7) 011.0000 0.9571 0.3028 0.2464 0.2820 n nv2元 02 0.9571 1.0000 0.2665 0.2020 0.2780 式中：do。0)是0，和0，的位置-文本距离（用1减 0 去空间对象之间的位置-文本关系紧密度)；G 0.3028 0.2665 1.0000 0.1515 0.0000 1 0.2464 0.2020 0.1515 1.0000 0.2152 (0,0)= 乃。学是高斯枝函数。 nV2m 050.2820 0.2780 0.0000 0.2152 1.0000 根据空间对象的位置-文本距离矩阵M(可从 所有空间对象之间的位置-文本关系紧密度 对象之间的位置-文本关系紧密度矩阵R转化而 可用一个n阶矩阵R表示（假设共有n个空间对 来)和概率密度估计方法，下面采用淘汰思想选 取代表性空间对象。该方法的基本过程如下： 象)，其中元素”代表了空间对象0，和0之间的 1)将空间对象集合0随机划分成若干小组， 位置-文本关系紧密度。由于矩阵R是一个对称 每个小组都包含1个空间对象，即将集合0划分 矩阵，因此仅存储上半矩阵即可。 成了n/u个小组，接着在每个小组中利用式(7)计 2top-k结果选取与排序方法 算所有空间对象的概率密度，选取每个小组中概 率密度最高的对象构成一个集合，然后从O中将 令g代表一个空间关键字查询，0是空间对 其他对象去除。 象集合，查询结果的top-k选取与排序问题定义 2)对于新得到的集合，重复上述过程，直到 如下： 空间对象集合O中只剩下一个对象为止，并将该 T&=arg max >Sim(q.o:) (6) 对象放入代表性对象候选集合中（上述过程记为 次选取过程)。 式中：「k是包含k个结果对象的有序列表；n表示 3)为了保证选取对象的准确性，需要将上述 数据集中空间对象的总数。top-k结果选取的目 选取过程重复执行m次（记为一轮），这样代表性 的是从数据集中快速获取与给定查询在位置和文 对象候选集合中最多会包含m个空间对象，接着 本上相关且具有代表性的前k个空间对象。 在最初的空间对象集合O上计算这m个对象的 本文方法分为3个步骤：1)从数据集中选取 概率密度，最后将具有最高概率密度的对象作为 少量代表性空间对象。2)为代表性空间对象创建 当前轮次的选取结果，并从O中将该空间对象去 序列，该序列是由数据集中其他对象与代表性对 除。上述整个过程重复1轮，这样就能得到I个近 象之间的位置-文本关系紧密度的降序排列。 似于准确解的代表性空间对象。 3)在线计算当前查询条件与所有代表性对象之间 该算法的时间复杂度为O(Imun)。在本文 的紧密度，然后在预先创建的对象序列上使用 实验部分，将重点比较在所提2种算法得到的代 TA算法快速获取top-k个结果对象。 表性对象序列上进行top-k结果选取的效果和 2.1选取代表性空间对象 性能。 选取代表性对象的基本思想：根据第2节的 2.2创建空间对象序列 空间对象之间的位置-文本关系评估方法，使用 对于每个代表性空间对象ō，为其构建一个 代表性对象选取算法获取l)个代表性空间对 序列τ，该序列中的元素是数据集中除该空间对 象，代表性空间对象集合用W,表示，代表性对象 象外的所有空间对象，这些对象按其对代表性空 用ō表示，即W,={ōi∈。 间对象的紧密度降序排列。如图1是一个包含 本文提出了一种基于概率密度优先选取代表 n个空间对象和3个代表性对象的空间对象序列 性对象的方法。该方法的基本思想是利用高斯核 示意图。权重是通过计算查询条件与代表性对象
反之，空间对象在文本上的相似度对总体紧密度 的影响越大。需要指出的是，利用式 (5) 得到的 空间对象之间的位置−文本关系紧密度在 [0, 1] 范 围内。表 4 给出了表 1 中所有空间对象的位置- 文本关系紧密度 (其中 α=0.5)。 表 4 空间对象的位置-文本关系紧密度 Table 4 The location-text closeness between spatial objects o1 o2 o3 o4 o5 o1 1.000 0 0.957 1 0.302 8 0.246 4 0.282 0 o2 0.957 1 1.000 0 0.266 5 0.202 0 0.278 0 o3 0.302 8 0.266 5 1.000 0 0.151 5 0.000 0 o4 0.246 4 0.202 0 0.151 5 1.000 0 0.215 2 o5 0.282 0 0.278 0 0.000 0 0.215 2 1.000 0 所有空间对象之间的位置−文本关系紧密度 可用一个 n 阶矩阵 R 表示 (假设共有 n 个空间对 象)，其中元素 rij 代表了空间对象 oi 和 oj 之间的 位置−文本关系紧密度。由于矩阵 R 是一个对称 矩阵，因此仅存储上半矩阵即可。 2 top-k 结果选取与排序方法 令 q 代表一个空间关键字查询，O 是空间对 象集合，查询结果的 top-k 选取与排序问题定义 如下： Γk = argmax Γ k∑ (k≪n) i=1 Sim(q, oi) (6) 式中： Γk 是包含 k 个结果对象的有序列表；n 表示 数据集中空间对象的总数。top-k 结果选取的目 的是从数据集中快速获取与给定查询在位置和文 本上相关且具有代表性的前 k 个空间对象。 本文方法分为 3 个步骤：1) 从数据集中选取 少量代表性空间对象。2) 为代表性空间对象创建 序列，该序列是由数据集中其他对象与代表性对 象之间的位置−文本关系紧密度的降序排列。 3) 在线计算当前查询条件与所有代表性对象之间 的紧密度，然后在预先创建的对象序列上使用 TA 算法快速获取 top-k 个结果对象。 2.1 选取代表性空间对象 ≪ o¯i Wl = {o¯i |i ∈ l} 选取代表性对象的基本思想：根据第 2 节的 空间对象之间的位置−文本关系评估方法，使用 代表性对象选取算法获取 l(l n) 个代表性空间对 象，代表性空间对象集合用 Wl 表示，代表性对象 用 表示，即 。 本文提出了一种基于概率密度优先选取代表 性对象的方法。该方法的基本思想是利用高斯核 函数评估某个空间对象在整个对象集合中的概率 密度，某个对象的概率密度越大，表明与其关系 紧密的对象越多，则该对象也就越有代表性，即 典型程度越高[18]。本文采用概率密度估计算法从 空间对象集合中选取代表性对象。 对于一个空间对象集合 O = {o1, o2,··· , on} ，对 象 o 的概率密度 f(oi ) 可以表示为： f(oi) = 1 n ∑n j=1 Gh(oi , oj) = 1 n √ 2π ∑n j=1 e − d(oi ,oj ) 2 2h 2 (7) Gh (oi , oj) = 1 n √ 2π ∑n j=1 e − d(oi ,oj ) 2 2h 2 式中：d(oi , oj ) 2 是 oi 和 oj 的位置−文本距离 (用 1 减 去空间对象之间的位置−文本关系紧密度)； 是高斯核函数。 根据空间对象的位置-文本距离矩阵 M(可从 对象之间的位置-文本关系紧密度矩阵 R 转化而 来) 和概率密度估计方法，下面采用淘汰思想选 取代表性空间对象。该方法的基本过程如下： 1) 将空间对象集合 O 随机划分成若干小组， 每个小组都包含 u 个空间对象，即将集合 O 划分 成了 n/u 个小组，接着在每个小组中利用式 (7) 计 算所有空间对象的概率密度，选取每个小组中概 率密度最高的对象构成一个集合，然后从 O 中将 其他对象去除。 2) 对于新得到的集合，重复上述过程，直到 空间对象集合 O 中只剩下一个对象为止，并将该 对象放入代表性对象候选集合中 (上述过程记为 一次选取过程)。 3) 为了保证选取对象的准确性，需要将上述 选取过程重复执行 m 次 (记为一轮)，这样代表性 对象候选集合中最多会包含 m 个空间对象，接着 在最初的空间对象集合 O 上计算这 m 个对象的 概率密度，最后将具有最高概率密度的对象作为 当前轮次的选取结果，并从 O 中将该空间对象去 除。上述整个过程重复 l 轮，这样就能得到 l 个近 似于准确解的代表性空间对象。 该算法的时间复杂度为 O(lmun)。在本文 实验部分，将重点比较在所提 2 种算法得到的代 表性对象序列上进行 top-k 结果选取的效果和 性能。 2.2 创建空间对象序列 o¯i τi 对于每个代表性空间对象 ，为其构建一个 序列 ，该序列中的元素是数据集中除该空间对 象外的所有空间对象，这些对象按其对代表性空 间对象的紧密度降序排列。如图 1 是一个包含 n 个空间对象和 3 个代表性对象的空间对象序列 示意图。权重是通过计算查询条件与代表性对象 ·238· 智 能 系 统 学 报 第 15 卷
第2期 孟祥福，等：基于位置-文本关系的空间对象opk查询与排序方法 ·239· 之间的紧密度获取的，每个序列左侧表示数据集 理步骤如下： 中除代表性对象之外的空间对象D,右侧表示空 算法1top-k结果选取与排序算法 间对象在该序列中对应的分数，该分数由对象在 输入代表性序列集合L,空间关键字查询 序列中的位置决定，计算方法为 4,topk中的k值 s(oT)=n-p(0:)+1 (8) 输出top-k结果对象 其中p(o,)表示对象0，在序列中的位置。 1)令B={}是一个缓存 空间关键 2)令L是一个大小为1的数组，存储每个序 字查询 列中最近一次检索得到的分数(score) 3)repeat 权重1 权重2 权重3 4)for each i∈{1,2，…，0do 5)从序列t:中检索下一个对象0，计算0在 代表性对 代表性对 代表性对 t:中的分数：s(o,q)=Sim(q,o)s(gr) 象1序列 象2序列 象3序列 6)用对象0在中的分数更新L中对应于 0 02 对象0的分数 7)利用随机访问方式获取0，在其他序列中的 0 0 0 分数，将所有检索到的分数加权求和，得到score (0,4) 02 -2 m-2 0分 2 8)按照降序方式，将插入到 B中的正确位置 44 9)end for 0(-2) 0(m-2) 0,(n-2) 2 lO)until B[]score≥ΣL[i 11)return B O(-1) O,(-1) 算法1的处理过程由以下3步组成： 图1代表性空间对象序列示意 1)循环访问每个代表性序列。在每次循环 Fig.1 Orders corresponding to representative objects 过程中，当一个空间对象0，在某个序列x:中被发 由于选取了I个代表性对象，因此将生成1个 现时，计算它在该代表性序列中的分数，计算公 代表性对象序列，这些序列用于使用TA算法的 式为 查询结果topk选取。 s(oj,q)=Sim(q.6)s(o) (10) 2.3top-k结果选取与排序 该分数由2部分构成：一部分是Sim(q,0),表 在代表性对象序列上，TA算法通过顺序访问 示查询条件q与序列t:对应的代表性空间对象 方式发现每个序列中的某个空间对象的排序分 ō之间的位置-文本关系紧密度；另一部分是 数，然后利用随机访问方式从其他序列中发现该 s(ox),表示对象o在序列t:中的排序分值。之 对象的排序分数，这些分数之和作为该对象在所 后，通过随机访问方式获取0在其他序列中的分 有序列中的总分数（注意，总分数是以查询条件 数，由式(9)可计算出对象0，对于查询q的综合 与该对象对应的代表性对象之间的位置-文本关 分数。 系紧密度作为权重系数，进行加权求和得到)，定 2)令s(omIx)为第m次循环结束后，在每个序 义如下： 列T中最后被访问对象的分数。TA算法阈值 threshold为第j次循环结束后数组L中的分数 score(g,o)= ∑sim(q,a)s(o,r,） (9) 之和。 式中：T:是对应代表性对象a的序列；Sim(q,)表 threshold=>Sim(q.6)s(o) (11) 示代表性对象ō：与查询q之间的位置-文本关系 紧密度。需要注意的是，在计算ā，与q之间的文 阈值threshold根据式(II)由算法自动计算得 本相似度时，转换成的向量的维度为查询q和所 到，每当进行新一轮循环（算法1中的3）10)时， 有代表性对象中包含的不同关键字总数。 算法1会重新自动计算一次阈值，当缓存B中存 基于上述思想，top-k结果选取与排序算法处 在k个总体排序分数都不小于当前阈值的对象
之间的紧密度获取的，每个序列左侧表示数据集 中除代表性对象之外的空间对象 ID，右侧表示空 间对象在该序列中对应的分数，该分数由对象在 序列中的位置决定，计算方法为 s(oi |τ) = n− p(oi)+1 (8) 其中 p(oi ) 表示对象 oi 在序列中的位置。 空间关键 字查询 代表性对 象2序列 代表性对 象3序列 代表性对 象1序列 O11 n−1 O12 n−2 O1 (n−2) 2 O1 (n−1) 1 权重1 权重3 n−1 n−2 2 1 n−1 n−2 2 1 权重2 O1 n O2 n O3 n O21 O22 O2 (n−1) O2 (n−2) O31 O32 O3 (n−1) O3 (n−2) 图 1 代表性空间对象序列示意 Fig. 1 Orders corresponding to representative objects 由于选取了 l 个代表性对象，因此将生成 l 个 代表性对象序列，这些序列用于使用 TA 算法的 查询结果 top-k 选取。 2.3 top-k 结果选取与排序 在代表性对象序列上，TA 算法通过顺序访问 方式发现每个序列中的某个空间对象的排序分 数，然后利用随机访问方式从其他序列中发现该 对象的排序分数，这些分数之和作为该对象在所 有序列中的总分数[19] (注意，总分数是以查询条件 与该对象对应的代表性对象之间的位置−文本关 系紧密度作为权重系数，进行加权求和得到)，定 义如下： score(q, oj) = ∑l i=1 Sim(q, o¯i)s(oj |τi) (9) τi o¯i Sim(q, o¯i) o¯i o¯i 式中： 是对应代表性对象 的序列； 表 示代表性对象 与查询 q 之间的位置-文本关系 紧密度。需要注意的是，在计算 与 q 之间的文 本相似度时，转换成的向量的维度为查询 q 和所 有代表性对象中包含的不同关键字总数。 基于上述思想，top-k 结果选取与排序算法处 理步骤如下： 算法 1 top-k 结果选取与排序算法 输入 代表性序列集合 L，空间关键字查询 q，top-k 中的 k 值 输出 top-k 结果对象 1) 令 B={ }是一个缓存 2) 令 L 是一个大小为 l 的数组，存储每个序 列中最近一次检索得到的分数 (score) 3) repeat 4) for each i ∈ {1,2,··· ,l} do τi τi s(oj ,q) = Sim(q, o¯i)s(qj |τi) 5) 从序列 中检索下一个对象 oj，计算 oj 在 中的分数： 6) 用对象 oj 在 τi 中的分数更新 L 中对应于 对象 oj 的分数 7) 利用随机访问方式获取 oj 在其他序列中的 分数，将所有检索到的分数加权求和，得到 score (oj ,q) 8) 按照降序方式，将插入到 B 中的正确位置 9) end for B[k]score ⩾ ∑l i=1 10) until L[i] 11) return B 算法 1 的处理过程由以下 3 步组成： τi 1) 循环访问每个代表性序列。在每次循环 过程中，当一个空间对象 oj 在某个序列 中被发 现时，计算它在该代表性序列中的分数，计算公 式为 s(oj , q) = Sim(q, o¯i)s(oj |τi) (10) Sim(q, o¯i) τi o¯i s(oj |τi) τi 该分数由 2 部分构成：一部分是 ，表 示查询条件 q 与序列 对应的代表性空间对象 之间的位置−文本关系紧密度；另一部分是 ，表示对象 oj 在序列 中的排序分值。之 后，通过随机访问方式获取 oj 在其他序列中的分 数，由式 (9) 可计算出对象 oj 对于查询 q 的综合 分数。 s(om|τi) τi 2) 令 为第 m 次循环结束后，在每个序 列 中最后被访问对象的分数。TA 算法阈值 threshold 为第 j 次循环结束后数组 L 中的分数 之和。 threshold = ∑l i=1 Sim(q, o¯i)s(om|τi) (11) 阈值 threshold 根据式 (11) 由算法自动计算得 到，每当进行新一轮循环 (算法 1 中的 3)~10)) 时， 算法 1 会重新自动计算一次阈值，当缓存 B 中存 在 k 个总体排序分数都不小于当前阈值的对象 第 2 期 孟祥福，等：基于位置−文本关系的空间对象 top-k 查询与排序方法 ·239·
·240· 智能系统学报 第15卷 时，算法终止。通过使用阈值threshold,使得第 用Jaccard系数进行评估： 1步无需遍历每个代表性序列中的所有对象就能 R(Rep,k)R(AIl,k) J(R(Rep,k).R(All,))= (12) 够提前结束算法执行，因此提高了执行效率。 R(Rep,)UR(AIl,k) 3)在所有被发现的空间对象中，输出前k个 Jaccard系数的值在[0，l]之间，值越高表明 具有最高总体排序分数的对象。 2个集合的重叠度越高，即top-k结果的准确性也 注意，当第2)步完成后，对于任意一个没有 就越高。 在循环访问中被发现的对象0，它的总体排序分 从数据集中随机抽取10个空间对象，再从每 数都将小于设定的阈值，即s(omq水threshold。 个空间对象的文本描述信息中随机抽取2-4个关 键字，最后将每个空间对象的经纬度信息和抽取 3性能实验分析 的关键字组合在一起形成空间关键字查询。此 3.1实验环境 外，用参数1表示代表性对象序列的个数（选取与 所有实验在Windows10操作系统、Intel i7 当前查询紧密度最高的前1个代表性对象对应的 3.1-GHz CPU和12GB内存的电脑上运行，使用 序列)，k表示返回的结果个数。在空间对象之间 下列真实数据来评估所提算法的性能和效果。 以及代表性对象与当前查询的位置-文本关系紧 数据集：测试数据使用Yelp数据集（该数据 密度计算中，式(5)的调节参数a设为0.5。图2 集来自Yelp数据集官网：http:www.yelp.com/ 给出了在Yelp数据集上分别使用本文方法（当 dataset),Yelp是美国最大的点评网站，包含了用 ={2,3,4,5,6}时)和IR-tree索引结构在不同k值 户签到信息、POI地点信息、用户评论信息等数 下得到的top-k结果的准确性对比。 据。实验截取经度在-115.0到-110.9之间，纬度 1.0r 0.9 -IR-tree +-=5 在32.3至35.6之间的53516个兴趣点作为分析 -=6 0.8 ◆月 数据。每个兴趣点都包含位置信息和文本信息， 0.7 想0.6 位置信息通过经度和纬度表示，文本信息由POI 0.5 哭0.4 的name、city、categories、postal_code、stars等属性 0.3 对应的信息构成。数据存放在文本文件中。测试 0.2 0.1 数据集的特点如表5所示。 102030405060708090100 表5测试数据集特点 Table 5 The properties of Yelp dataset 图2 利用本文方法和IR-tree索引得到的top-k结果准 特征 确性对比 Yelp Fig.2 Comparison for the precision of top-k results re- POI总数 53516 turned by using our method and IR-tree index 数据集中所有不同的关键字个数 94035 从图2可以看出：I)IR-tree方法得到的top 每个POI平均拥有的关键字个数 > k结果的准确性一直优于本文方法，top-10,20,…, 数据集中所有的关键字个数 658246 100的平均准确性达到66%。2)当={2,3}时，使 用本文方法得到的top-k结果的准确性较高，当 3.2topk结果的准确性和典型性测试 =3时准确性最高，top-10,20,…,100的平均准确 从数据集中获取前k个与给定查询最为相关 性为51%。但当代表性序列超过3个时，准确性 的空间对象，准确方法是计算给定查询与数据集 就会降低，原因是参与top-k结果选取的序列数越 中所有空间对象之间的位置-文本关系紧密度，然 多，序列对应的代表性对象与当前查询的紧密度 后再按紧密度大小选取出top-k个空间对象。因 越低，因此参与序列与真实结果序列的相关度就 此，本实验需要验证准确获取top-k个空间对象与 越低，进而导致op-k结果准确性就越低。 利用TA算法在代表性对象序列上选出的top 需要指出的是，虽然IR-tree方法的准确性一 k个空间对象之间的重叠程度，即本文top-k查询 直优于本文方法，但本文目的是在确保top-k结果 方法的准确性。这里用R(Rep,k)表示在代表性 具有一定准确性的前提下，同时具有更高的多样 对象序列上选取的top-k个对象；R(AIL,k)表示通 性和典型性。因此，还需测试本文方法得到的 过计算数据集中所有对象与给定查询之间的紧密 top-k结果与利用IR-tree索引得到的top-k结果， 度选取的top-k个对象。这两个集合的重叠度可 二者在典型程度上的差别。查询结果典型程度的
时，算法终止。通过使用阈值 threshold，使得第 1 步无需遍历每个代表性序列中的所有对象就能 够提前结束算法执行，因此提高了执行效率。 3) 在所有被发现的空间对象中，输出前 k 个 具有最高总体排序分数的对象。 注意，当第 2) 步完成后，对于任意一个没有 在循环访问中被发现的对象 on，它的总体排序分 数都将小于设定的阈值，即 s(on , q)<threshold。 3 性能实验分析 3.1 实验环境 所有实验在 Windows 10 操作系统、Intel i7 3.1-GHz CPU 和 12 GB 内存的电脑上运行，使用 下列真实数据来评估所提算法的性能和效果。 数据集：测试数据使用 Yelp 数据集（该数据 集来自 Yelp 数据集官网：http://www.yelp.com/ dataset），Yelp 是美国最大的点评网站，包含了用 户签到信息、POI 地点信息、用户评论信息等数 据。实验截取经度在−115.0 到−110.9 之间，纬度 在 32.3 至 35.6 之间的 53 516 个兴趣点作为分析 数据。每个兴趣点都包含位置信息和文本信息， 位置信息通过经度和纬度表示，文本信息由 POI 的 name、city、categories、postal_code、stars 等属性 对应的信息构成。数据存放在文本文件中。测试 数据集的特点如表 5 所示。 表 5 测试数据集特点 Table 5 The properties of Yelp dataset 特征 Yelp POI总数 53 516 数据集中所有不同的关键字个数 94 035 每个POI平均拥有的关键字个数 7 数据集中所有的关键字个数 658 246 3.2 top-k 结果的准确性和典型性测试 从数据集中获取前 k 个与给定查询最为相关 的空间对象，准确方法是计算给定查询与数据集 中所有空间对象之间的位置-文本关系紧密度，然 后再按紧密度大小选取出 top-k 个空间对象。因 此，本实验需要验证准确获取 top-k 个空间对象与 利用 TA 算法在代表性对象序列上选出的 topk 个空间对象之间的重叠程度，即本文 top-k 查询 方法的准确性。这里用 R(Rep, k) 表示在代表性 对象序列上选取的 top-k 个对象；R(All, k) 表示通 过计算数据集中所有对象与给定查询之间的紧密 度选取的 top-k 个对象。这两个集合的重叠度可 用 Jaccard 系数进行评估： J(R(Rep, k),R(All, k))= R(Rep, k)∩R(All, k) R(Rep, k)∪R(All, k) (12) Jaccard 系数的值在 [0,1] 之间，值越高表明 2 个集合的重叠度越高，即 top-k 结果的准确性也 就越高。 从数据集中随机抽取 10 个空间对象，再从每 个空间对象的文本描述信息中随机抽取 2−4 个关 键字，最后将每个空间对象的经纬度信息和抽取 的关键字组合在一起形成空间关键字查询。此 外，用参数 l 表示代表性对象序列的个数 (选取与 当前查询紧密度最高的前 l 个代表性对象对应的 序列)，k 表示返回的结果个数。在空间对象之间 以及代表性对象与当前查询的位置-文本关系紧 密度计算中，式 (5) 的调节参数 α 设为 0.5。图 2 给出了在 Yelp 数据集上分别使用本文方法 (当 l={2, 3, 4, 5, 6}时) 和 IR-tree 索引结构在不同 k 值 下得到的 top-k 结果的准确性对比。 10 20 30 40 50 60 70 80 90 100 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 k IR-tree l=2 l=3 l=4 l=5 l=6 准确率 图 2 利用本文方法和 IR-tree 索引得到的 top-k 结果准 确性对比 Fig. 2 Comparison for the precision of top-k results returned by using our method and IR-tree index 从图 2 可以看出：1)IR-tree 方法得到的 topk 结果的准确性一直优于本文方法，top-10，20，···， 100 的平均准确性达到 66%。2) 当 l={2，3}时，使 用本文方法得到的 top-k 结果的准确性较高，当 l=3 时准确性最高，top-10，20，···，100 的平均准确 性为 51%。但当代表性序列超过 3 个时，准确性 就会降低，原因是参与 top-k 结果选取的序列数越 多，序列对应的代表性对象与当前查询的紧密度 越低，因此参与序列与真实结果序列的相关度就 越低，进而导致 top-k 结果准确性就越低。 需要指出的是，虽然 IR-tree 方法的准确性一 直优于本文方法，但本文目的是在确保 top-k 结果 具有一定准确性的前提下，同时具有更高的多样 性和典型性。因此，还需测试本文方法得到的 top-k 结果与利用 IR-tree 索引得到的 top-k 结果， 二者在典型程度上的差别。查询结果典型程度的 ·240· 智 能 系 统 学 报 第 15 卷
第2期 孟祥福，等：基于位置-文本关系的空间对象op-k查询与排序方法 ·241· 评价标准为： ×10 5.0 2 4.0 IR-tree Typicality(T)= k (13) 式中：T代表top-k结果集合；k表示结果对象个 20 数；八o,)根据式(7)计算。该实验中令=10。top . k结果典型程度的计算范围按如下方法确定：取 本文方法和IR-tree方法得到的top-k结果中与给 102030405060708090100 定查询紧密度最低的对象作为阈值，高于该阈值 图4不同I和k值下利用本文方法和IR-tree的top-k查 的对象构成的集合就是计算topk结果典型程度 询响应时间 的对象范围。to叩-k结果的典型程度越高，说明结 Fig.4 Execution time of top-k query selection by using our 果对象越能体现整个相关结果集合的总体特征， method and IR-tree index under different values of/ 因此也就越能开阔用户视野和有助于用户对查询 and 相关结果集合的总体认知。典型程度比较的基准 从图4可以看出，当={2,3}时本文方法与 是在对应计算范围内，利用式(7)计算得到的典 R-tree索引的响应时间相近，并且当k≤40时，响 型程度最高的前10个对象的平均典型程度。图3 应时间要低于IR-tree,这也说明了TA算法在k值 给出了不同测试查询下本文方法和IR-tree索引 较小时具有优越的性能。此外，本文方法的响应 得到的top-k结果典型程度在基准下的对比。 时间随着k和1值的增加而逐渐增长，其原因是 1.0 当k和1增加后，算法需要处理的对象个数也会 0.9 Our method □IR-tree 增多，因此导致响应时间增加。 0.8 0.7 0.6 4结束语 0.4 0.3 本文提出了一种基于位置-文本关系的空间 0.2 对象topk查询与排序方法，目的是从空间数据库 0.1 中快速获取与查询位置和文本相关且具有代表性 23 4 5.6 7 8 9 10 查询 的top-k空间对象。实验结果表明，提出的top 图3。本文方法和R-tree得到的top-k结果典型程度 k查询与排序方法同时具有较高的准确性、典型 对比 性和执行效率，特别适用于大规模空间数据库的 Fig.3 Comparison for the typicality of the top-k results re- 空间关键字top-k检索。 turned by using our method and IR-tree index 本文方法与现存方法有2个方面不同：1)提 图3显示了本文方法得到的top-k结果的典 出了基于概率密度的代表性对象选取算法来获取 型程度一直明显高于IR-tree,原因是本文方法是 代表性空间对象，进而构建代表性空间对象序 从代表性对象对应的序列中获取结果，这些结果 列，为快速选取top-k结果提供基础。2)将阈值算 对象与代表性对象的紧密度较高，相应地典型程 法threshold algorithm(TA)算法应用到了对空间对 度也就较高，而IR-tree方法得到的top-k结果之 象的topk查询与排序中，在确保较高查询准确性 间通常比较相似，多样性和典型程度相对较低。 的前提下兼顾了查询结果的典型性，并且具有较 综合图2和图3还可以得出，本文方法在准确性 快的响应时间。下一步工作将研究如何将公路网 较高的前提下，在很大程度上提高了查询结果的 络(road network)应用于空间对象之间的距离计 典型程度，即结果对象更具代表性，能够更好地 算，以及如何进行查询结果的局部典型化和多样 满足用户对查询结果的相关性和典型性查询需求。 典型化选取。 3.3topk查询算法的性能测试 该实验的目的是测试本文提出的top-k查询 参考文献： 算法的响应时间。在该实验中，设置代表性序列 [1]QI Jianzhong,ZHANG Rui,JENSEN C S.Continuous 个数1分别为2、3、4和5，然后测试在不同k值下， spatial query processing:a survey of safe region based 分别使用本文方法和IR-tree索引获取top-k结果 techniques[J].ACM computing surveys,2018,51(3):64. 的响应时间（如图4所示）。 [2]CONG Gao,JENSEN CS.Querying geo-textual data:spa-
评价标准为： Typicality(T) = ∑k i=1 f(oi) k (13) 式中：T 代表 top-k 结果集合；k 表示结果对象个 数；f(oi ) 根据式 (7) 计算。该实验中令 k=10。topk 结果典型程度的计算范围按如下方法确定：取 本文方法和 IR-tree 方法得到的 top-k 结果中与给 定查询紧密度最低的对象作为阈值，高于该阈值 的对象构成的集合就是计算 top-k 结果典型程度 的对象范围。top-k 结果的典型程度越高，说明结 果对象越能体现整个相关结果集合的总体特征， 因此也就越能开阔用户视野和有助于用户对查询 相关结果集合的总体认知。典型程度比较的基准 是在对应计算范围内，利用式 (7) 计算得到的典 型程度最高的前 10 个对象的平均典型程度。图 3 给出了不同测试查询下本文方法和 IR-tree 索引 得到的 top-k 结果典型程度在基准下的对比。 1 2 3 4 5 6 7 8 9 10 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 查询 Our method IR-tree 典型程度 图 3 本文方法和 IR-tree 得到的 top-k 结果典型程度 对比 Fig. 3 Comparison for the typicality of the top-k results returned by using our method and IR-tree index 图 3 显示了本文方法得到的 top-k 结果的典 型程度一直明显高于 IR-tree，原因是本文方法是 从代表性对象对应的序列中获取结果，这些结果 对象与代表性对象的紧密度较高，相应地典型程 度也就较高，而 IR-tree 方法得到的 top-k 结果之 间通常比较相似，多样性和典型程度相对较低。 综合图 2 和图 3 还可以得出，本文方法在准确性 较高的前提下，在很大程度上提高了查询结果的 典型程度，即结果对象更具代表性，能够更好地 满足用户对查询结果的相关性和典型性查询需求。 3.3 top-k 查询算法的性能测试 该实验的目的是测试本文提出的 top-k 查询 算法的响应时间。在该实验中，设置代表性序列 个数 l 分别为 2、3、4 和 5，然后测试在不同 k 值下， 分别使用本文方法和 IR-tree 索引获取 top-k 结果 的响应时间 (如图 4 所示)。 5 10 20 30 40 50 60 70 80 90 100 0 1.0 2.0 3.0 4.0 5.0 k l=2 l=3 l=4 l=5 IR-tree 执行时间/ms 图 4 不同 l 和 k 值下利用本文方法和 IR-tree 的 top-k 查 询响应时间 Fig. 4 Execution time of top-k query selection by using our method and IR-tree index under different values of l and k 从图 4 可以看出，当 l={2, 3}时本文方法与 IR-tree 索引的响应时间相近，并且当 k≤40 时，响 应时间要低于 IR-tree，这也说明了 TA 算法在 k 值 较小时具有优越的性能。此外，本文方法的响应 时间随着 k 和 l 值的增加而逐渐增长，其原因是 当 k 和 l 增加后，算法需要处理的对象个数也会 增多，因此导致响应时间增加。 4 结束语 本文提出了一种基于位置-文本关系的空间 对象 top-k 查询与排序方法，目的是从空间数据库 中快速获取与查询位置和文本相关且具有代表性 的 top-k 空间对象。实验结果表明，提出的 topk 查询与排序方法同时具有较高的准确性、典型 性和执行效率，特别适用于大规模空间数据库的 空间关键字 top-k 检索。 本文方法与现存方法有 2 个方面不同：1) 提 出了基于概率密度的代表性对象选取算法来获取 代表性空间对象，进而构建代表性空间对象序 列，为快速选取 top-k 结果提供基础。2) 将阈值算 法 threshold algorithm(TA) 算法应用到了对空间对 象的 top-k 查询与排序中，在确保较高查询准确性 的前提下兼顾了查询结果的典型性，并且具有较 快的响应时间。下一步工作将研究如何将公路网 络 (road network) 应用于空间对象之间的距离计 算，以及如何进行查询结果的局部典型化和多样 典型化选取。 参考文献： QI Jianzhong, ZHANG Rui, JENSEN C S. Continuous spatial query processing: a survey of safe region based techniques[J]. ACM computing surveys, 2018, 51(3): 64. [1] [2] CONG Gao, JENSEN C S. Querying geo-textual data: spa- 第 2 期 孟祥福，等：基于位置−文本关系的空间对象 top-k 查询与排序方法 ·241·
·242· 智能系统学报 第15卷 tial keyword queries and beyond[C]//Proceedings of 2016 points and rectangles[C]//Proceedings of 1990 ACM SIG- International Conference on Management of Data.San MOD International Conference on Management of Data. Francisco,California,USA,2016:2207-2212. Atlantic City,New Jersey,USA,1990:322-331. [3]ZHENG Kai,SU Han,ZHENG Bolong,et al.Interactive [14]ZHANG Chengyuan,ZHANG Ying,ZHANG Wenjie,et top-k spatial keyword queries[Cl//Proceedings of the 31st al.Inverted linear quadtree:efficient top k spatial International Conference on Data Engineering.Seoul, keyword search[J].IEEE transactions on knowledge and South Korea,2015:423-434. data engineering,2016,28(7):1706-1721 [4]LU Ying,LU Jiaheng,CONG Gao,et al.Efficient al- [15]ZHOU Yinghua,XIE Xing,WANG Chuang,et al.Hy- gorithms and cost models for reverse spatial-keyword k- brid index structures for location-based Web search[C]// nearest neighbor search[J.ACM transactions on database Proceedings of the 14th ACM International Conference systems..2014.39(2):13. on Information and Knowledge Management.Bremen, [5]DE FELIPE I,HRISTIDIS V,RISHE N.Keyword search Germany,.2005:155-162 on spatial databases[C]//Proceedings of the 24th IEEE In- [16]LI Zhisheng,LEE K C K,ZHENG Baihua,et al.IR-Tree: ternational Conference on Data Engineering.Cancun, an efficient index for geographic document search[J]. Mexico,.2008:656-665. IEEE transactions on knowledge and data engineering, [6]LI Guoliang,XU Jing,FENG Jianhua.Keyword-based k- 2011,23(4):585-599. nearest neighbor search in spatial databases[Cl//Proceed- [17]HONG HJ,CHIU G M,TSAI W Y.A single quadtree- ings of the 21st ACM International Conference on Inform- based algorithm for top-k spatial keyword query[J].Per- ation and Knowledge Management.Maui,Hawaii,USA, vasive and mobile computing,2017,42:93-107. 2012:2144-2148 [18]HUA Ming,PEI Jian,FU A W C,et al.Top-k typicality [7]WANG Xiang,ZHANG Ying,ZHANG Wenjie,et al. queries and efficient query answering methods on large Skype:top-k spatial-keyword publish/subscribe over slid- databases[J].The VLDB journal,2009,18(3):809-835. ing window[J].Proceedings of the VLDB endowment, 2016,97):588-599. [19]FAGIN R,LOTEM A,NAOR M.Optimal aggregation al- [8]ZHANG Dongxiang,CHEE Y M,MONDAL A,et al. gorithms for middleware[J].Journal of computer and sys- Keyword search in spatial databases:towards searching by tem sciences,2003,66(4):614-656 document[C]//Proceedings of the 25th International Con- 作者简介： ference on Data Engineering.Shanghai,China,2009: 孟祥福，教授，博士生导师，主要 688-699. 研究方向为空间关键字查询、大数据 [9]CONG Gao,JENSEN C S,WU Dingming.Efficient re- 分析与可视化、机器学习算法。主持 国家自然科学基金项目2项、辽宁省 trieval of the top-k most relevant spatial web objects[J. Proceedings of the VLDB endowment,2009,2(1): 各类基金项目3项。发表学术论文 30余篇。 337-348. [10]CHEN Lei,LIN Xin,HU Haibo,et al.Answering why- not questions on spatial keyword top-k queries[C]//Pro- 张霄雁，工程师，主要研究方向为 ceedings of the 31st International Conference on Data En- 空间数据查询与分析、城市计算、机器 学习算法。主持辽宁省教育厅科研项 gineering.Seoul,South Korea,2015:279-290. 目1项。发表学术论文10余篇。 [11]KWON H Y,WANG Haixun,WHANG K Y.G-index model:a generic model of index schemes for top-k spa- tial-keyword queries[J].World wide web,2015,18(4): 969-995 [12]GUTTMAN A.R-trees:a dynamic index structure for 赵路路，硕士研究生，主要研究方 spatial searching[C]//Proceedings of 1984 ACM SIG- 向为空间数据查询与分析。 MOD International Conference on Management of Data. Boston,Massachusetts,1984:47-57. [13]BECKMANN N,KRIEGEL H P,SCHNEIDE R,et al. The R -tree:an efficient and robust access method for
tial keyword queries and beyond[C]//Proceedings of 2016 International Conference on Management of Data. San Francisco, California, USA, 2016: 2207−2212. ZHENG Kai, SU Han, ZHENG Bolong, et al. Interactive top-k spatial keyword queries[C]//Proceedings of the 31st International Conference on Data Engineering. Seoul, South Korea, 2015: 423–434. [3] LU Ying, LU Jiaheng, CONG Gao, et al. Efficient algorithms and cost models for reverse spatial-keyword knearest neighbor search[J]. ACM transactions on database systems, 2014, 39(2): 13. [4] DE FELIPE I, HRISTIDIS V, RISHE N. Keyword search on spatial databases[C]//Proceedings of the 24th IEEE International Conference on Data Engineering. Cancun, Mexico, 2008: 656–665. [5] LI Guoliang, XU Jing, FENG Jianhua. Keyword-based knearest neighbor search in spatial databases[C]//Proceedings of the 21st ACM International Conference on Information and Knowledge Management. Maui, Hawaii, USA, 2012: 2144–2148. [6] WANG Xiang, ZHANG Ying, ZHANG Wenjie, et al. Skype: top-k spatial-keyword publish/subscribe over sliding window[J]. Proceedings of the VLDB endowment, 2016, 9(7): 588–599. [7] ZHANG Dongxiang, CHEE Y M, MONDAL A, et al. Keyword search in spatial databases: towards searching by document[C]//Proceedings of the 25th International Conference on Data Engineering. Shanghai, China, 2009: 688–699. [8] CONG Gao, JENSEN C S, WU Dingming. Efficient retrieval of the top-k most relevant spatial web objects[J]. Proceedings of the VLDB endowment, 2009, 2(1): 337–348. [9] CHEN Lei, LIN Xin, HU Haibo, et al. Answering whynot questions on spatial keyword top-k queries[C]//Proceedings of the 31st International Conference on Data Engineering. Seoul, South Korea, 2015: 279–290. [10] KWON H Y, WANG Haixun, WHANG K Y. G-index model: a generic model of index schemes for top-k spatial-keyword queries[J]. World wide web, 2015, 18(4): 969–995. [11] GUTTMAN A. R-trees: a dynamic index structure for spatial searching[C]//Proceedings of 1984 ACM SIGMOD International Conference on Management of Data. Boston, Massachusetts, 1984: 47–57. [12] BECKMANN N, KRIEGEL H P, SCHNEIDE R, et al. The R* -tree: an efficient and robust access method for [13] points and rectangles[C]//Proceedings of 1990 ACM SIGMOD International Conference on Management of Data. Atlantic City, New Jersey, USA, 1990: 322–331. ZHANG Chengyuan, ZHANG Ying, ZHANG Wenjie, et al. Inverted linear quadtree: efficient top k spatial keyword search[J]. IEEE transactions on knowledge and data engineering, 2016, 28(7): 1706–1721. [14] ZHOU Yinghua, XIE Xing, WANG Chuang, et al. Hybrid index structures for location-based Web search[C]// Proceedings of the 14th ACM International Conference on Information and Knowledge Management. Bremen, Germany, 2005: 155–162. [15] LI Zhisheng, LEE K C K, ZHENG Baihua, et al. IR-Tree: an efficient index for geographic document search[J]. IEEE transactions on knowledge and data engineering, 2011, 23(4): 585–599. [16] HONG H J, CHIU G M, TSAI W Y. A single quadtreebased algorithm for top-k spatial keyword query[J]. Pervasive and mobile computing, 2017, 42: 93–107. [17] HUA Ming, PEI Jian, FU A W C, et al. Top-k typicality queries and efficient query answering methods on large databases[J]. The VLDB journal, 2009, 18(3): 809–835. [18] FAGIN R, LOTEM A, NAOR M. Optimal aggregation algorithms for middleware[J]. Journal of computer and system sciences, 2003, 66(4): 614–656. [19] 作者简介： 孟祥福，教授，博士生导师，主要 研究方向为空间关键字查询、大数据 分析与可视化、机器学习算法。主持 国家自然科学基金项目 2 项、辽宁省 各类基金项目 3 项。发表学术论文 30 余篇。 张霄雁，工程师，主要研究方向为 空间数据查询与分析、城市计算、机器 学习算法。主持辽宁省教育厅科研项 目 1 项。发表学术论文 10 余篇。 赵路路，硕士研究生，主要研究方 向为空间数据查询与分析。 ·242· 智 能 系 统 学 报 第 15 卷