基于四叉树的移动终端地图搜索算法研究与实现

胡 颖

（1.重庆市勘测院，重庆 400020）

基于四叉树的移动终端地图搜索算法研究与实现

胡 颖1

（1.重庆市勘测院，重庆 400020）

针对智能移动终端的GPS定位位置和用户在终端输入的搜索关键词，设计了一种综合性的空间关键词索引框架，该框架利用倒排索引进行文本索引，利用四叉树索引进行空间索引。基于该综合索引框架设计和实现了一种高效准确的POI搜索算法，该算法能够根据移动终端的位置和用户输入的搜索关键词，从数据库中获取到相关度尽量高的结果，从而提高地图搜索的准确度和效率。

空间索引；向量空间模型；空间关键词搜索

近几年来，移动终端的GPS功能迅速普及，在移动互联网爆发式增长的驱动下，互联网增加了空间的维度，研究显示，大约20%的网络搜索是和地理位置相关的。位置服务搜索采用关键词结合地理坐标的方式，帮助用户从空间数据库中找到相关的结果。空间数据中存储了许多具有坐标位置的POI，如商场、景点、宾馆、车站、餐馆等，同时还存储了一定描述性的文本信息。因此，空间搜索必须同时考虑搜索对象的空间坐标和文本信息，返回两个方面都符合用户查询要求的POI[1-2]。本文提出一种全新的索引框架，这种索引框架综合了文本检索的倒排索引和四叉树索引，并基于这个综合索引框架，设计了一种高效和准确地检索空间数据库中POI对象的算法。

1 文本相关度度量

在本文中，使用向量空间模型来计算搜索关键词和POI数据文本的相关性，并应用概率排序函数对搜索结果进行排序。向量空间模型的基本思想是将文本中出现的所有特征词构成一个n维的向量空间，然后利用余弦定理计算文本相似度。

本文使用中科院计算所的ICTCLAS分词工具将POI的文本内容进行分词，分词完成后，把文本表示为特征词权重的一个向量：

根据词频-逆向文件频率模型，一个词组在文件向量中权重就是局部参数和全局参数的乘积，经过综合考虑调整之后，特征词权重的计算公式为：

式中，tft,d为特征词t在文档d中出现的频率；是逆向文本频率为文本集合中的文件总数；是含有特征词t的文本数。

文本di和查询q之间通过余弦定理计算相似度。计算两个文档向量之间的夹角，通过余弦定理可知，夹角越小，余弦值越大，则文本向量之间的相关度越大。

下文中，利用式（1）计算搜索q和POI对象之间的文本相关度。

2 综合索引框架

四叉树是空间搜索的重要索引方法。其基本思想是将地理空间递归划分为不同层次的树结构。首先将已知范围的空间等分为4个相等子空间，如此递归下去，直至四叉树的层次满足要求后停止分割（图1、图2）。四叉树结构简单，并且当空间数据POI对象分布比较均匀时，具有较高的空间数据插入和查询效率[1,3]。

图1 空间划分平面图

图2 四叉树结构示意图

倒排索引是一种高效的文本索引方法。通过倒排索引，可以根据特征词快速获取包含这个特征词的文档列表。一个典型的倒排索引主要由词汇表和倒排列表两部分组成。词汇表是用来存放分词词典的，通常称存放词汇表的文件为索引文件；倒排列表是用来存放这个文件中对应词汇表中词汇出现的位置和次数的，存放分词位置的文件称为位置文件[4]。

在必须兼顾空间和文本索引的位置服务搜索领域，需要综合使用四叉树索引和倒排索引，本文据此提出一种新型的索引框架。

首先在空间数据库POI对象集合P上建立一颗四叉树，从根结点开始，将空间4等分，对于每个子空间，建立四叉树的第1层，接着继续4等分，这4个子空间得到更多更小的空间，直到划分达到一定的深度时停止；并为每一层的各个结点分别创建倒排文件，如表1所示。

表1 四叉树根结点和中间结点倒排文件

由于结点并没有对应一个具体的文档文件，结点文档是一个复合的概念，它覆盖结点在空间划分对应的矩形区域包含的所有POI对象中的文本文档，可以应用结点文档来评估以该结点包含的POI对象中所有文本和搜索关键词之间的文本相关度。每个特征词t在结点文档中的权重表示特征词t对于子树结点文档的最大权重。

在四叉树中，每个叶结点保存了该结点对应的最小外包矩形区域内所有POI对象的引用及其文本的标识符。

POI对象的访问入口包含指向空间数据库中某个POI点对象的指针，POI点所在的外包矩形以及对象文本文档的标识符。叶结点中还包含了指向POI对象文本的倒排文件的指针。

如表2所示，叶节点的倒排文件主要由所有特征词组成的词汇表和特征词对应的倒排列表两部分组成。每个倒排文件中的列表对应一个特征词t。列表中的内容是结点文本和权重组成的序列，在本文中权重为特征词在该文档中出现的次数。

在四叉树的每个结点建立对应的倒排索引文件之后，调用索引合并程序，将索引合并成一颗完整的四叉树，最终得到综合索引框架[5]。

3 搜索算法的计算过程

在综合索引框架下，采用最佳优先搜索策略遍历四叉树结点，搜索k个符合程度最高的搜索结果。

在搜索过程中，引入M（R，q）来表示搜索q到结点R之间的最小编辑距离，定义为：

其中，

当搜索算法访问到POI对象时，引入D（P，q）来评估搜索q和POI对象之间的编辑距离。

其中，

表2 四叉树部分叶结点倒排文件

空间关键词查询用q（q.loc，q.keyword）表示s，其中，q.loc表示发出查询的位置坐标；q.keyword表示关键词。与此类似，P.loc和R.loc分别表示POI点位和结点R的位置；P.doc和R.doc分别表示POI点位对象和结点R的文本文档。

式（2）、（3）中的参数α，取值在0～1之间，用于平衡空间距离和文本相关度。通过调整α参数，用户能够设置文本相关度和位置距离的偏好程度。DIS（R.loc，q.loc）和DIS（P.loc，q.loc）分别表示结点R、POI点P和搜索q点位之间的欧式距离，通过DISmax将欧式距离规范到区间DISmax表示空间数据库中两个POI对象之间的最大距离。

算法从四叉树根结点开始逐层访问四叉树，对于访问的每一个结点，算法根据其位置信息和文本相关度通过式（2）计算出综合的编辑距离值，插入优先队列，然后将编辑距离最小的结点作为下个将要访问的结点。直到访问叶结点内包含POI对象，通过D（P，q）算出POI点的编辑距离值，同样插入优先队列，逐次迭代，最终根据需要，从优先队列中取出前K个结果，便是最佳相关度的搜索结果[6]。

4 实验与分析

为了评价综合索引框架和算法的性能，通过实验对比了多种索引下查询的响应时间。

实验使用的空间数据库包含大约80万条POI数据，每条POI记录包含位置坐标和文本信息，对文本进行分词，建立词汇表大约包含特征词25万个。

四叉树空间划分最大深度取3，参数α取值0.5，也就是距离和文本相关度以各50%的权重进行对比，接着测试从0.1～0.9变化的情况。

实验环境：处理器为3.5GHz intel i7 CPU，内存16 G；操作系统Windows Server 2008 R2。

实验结果如下：

1）文本和空间权重相同，对于式（2）、（3），α取值0.5，测试结果如图3所示，通过使用综合索引前后对比，可以看出搜索效率有了很大的提升。在3种空间索引的结构上进行空间关键词查询，实验频率为每组数据100次。在这种方式下，能客观地获取3种索引结构的平均响应时间。通过响应时间的对比来评价索引效率。当空间数据集增大，综合索引的响应时间明显优于其他空间索引，通过对其进行剪枝操作，效率能够得到进一步提升。

图3 不同索引架构的响应时间

2）为了验证本文搜索算法的有效性，使用2种搜索方法对搜索结果进行排序，记录前5条查询结果，对用户群体进行了问卷调查，调查结果如图4，用户满意度达到了较高水平。

图4 搜索结果满意度评分

由以上实验可知，基于综合索引框架的算法提高了POI搜索的准确性和效率。

5 结 语

本文研究了基于四叉树和倒排索引的空间关键词查询算法，提出了一种新型的索引结构。这种索引结构能同时根据文本和空间特性对空间数据库中的POI数据集进行有效的组织。基于该综合索引结构，设计的高效的空间关键词搜索算法，在POI空间关键词搜索的准确度和效率方面有了显著的提升。

[1] 周巧临.PMR四叉树空间索引优化的应用研究[J].微计算机信息,2008,24(3)∶175-177

[2] ZHOU Y,XIE X,WANG C,et al.Hybrid Index Structures for Location-based Web Search [C].ACM International Conference on Information & Knowledge Management,New York,2005

[3] 蒋华.一种PMR四叉树空间索引效率分析模型的研究[J].计算机工程与应用,2006,42(35)∶166-168

[4] 杨建武,陈晓鸿.基于倒排索引的文本相似搜索[J].计算机工程,2005,31(5)∶1-3

[5] XIN C,GAO C,Jensen C S,et al.Collective Spatial Keyword Querying[C].ACM Sigmod International Conference on Management of Data, New York,2011

[6] XIAO C,WANG W,LIN X,et al.Top-k Set Similarity Joins[C]. IEEE International Conference on Data Engineering, Shanghai,2009

[7] Zobel J,Moffat A.Inverted Files for Text Search Engines[J]. ACM Computing Surveys,2006,38(4)∶38-56

P208

B

1672-4623（2016）05-0089-03

10.3969/j.issn.1672-4623.2016.05.028

胡颖，硕士，工程师，研究方向为地理信息工程。

2016-01-15。

项目来源：重庆市社会民生科技创新资助项目（CSTC2015shmszx40007）。