支持多子串近似匹配的空间关键词查询算法

张素智，丁温雪，徐家兴

(郑州轻工业学院 计算机与通信工程学院，河南 郑州 450002)



支持多子串近似匹配的空间关键词查询算法

张素智，丁温雪，徐家兴

(郑州轻工业学院 计算机与通信工程学院，河南 郑州 450002)

随着空间数据飞速增长，不仅POI(Point Of Interest)越来越密集，而且每个空间点的文本描述也越来越多，以往关键词近似查询算法中，不同长度的关键词需要不同的阈值相匹配，影响查询效率和查询结果.针对以上不足提出了支持空间多子串近似匹配的空间关键词查询算法，在该算法中不需要考虑阈值的改变，而是将编辑距离直接应用到索引结构中.通过真实数据进行实验，表明该算法在查询精准性和查询效率上都有较大的提高.

空间数据库；q-gram倒排索引；查询算法；RB-tree

近年来，越来越多的搜索引擎开始支持空间关键字查询[1]，使得越来越多的WEB资源开始拥有位置属性，例如：新浪微博中发布自己的地理位置信息、餐馆旅游景点的网页中会附带位置的信息以及签到功能等.随着基于位置服务[2]的快速发展，空间关键字渐渐的浮现在科技的最前沿.

空间关键字查询[3](Spatial Keyword Query)是处理空间数据的重要方法之一，现有的搜索引擎大多数都开始支持空间数据查询，通过输入的文本数据和空间约束作为查询条件，返回满足空间信息和文本数据的结果，并按照相对应的排序算法[4]把结果显示出来.空间数据飞速增长、用户要求不断提高、终端设备功能扩大以往的查询算法越来越不能满足用户的需求，如何在海量的空间数据中找到相对应的结果成为当前研究的热点.

本文将改进的支持多子串匹配q-gram倒排结构引入针对空间数据建立的空间索引结构当中，实现空间关键词的近似匹配，将空间距离和权值有效的结合起来，通过该索引结构不仅可以不用根据关键词的长度变化来改变阈值大小，而且可以对查询多关键词进行匹配，并根据该索引建立有效的Top-k查询方法.

1 相关知识和工作介绍

1.1 相关工作

Yao等[4]提出的MHR-tree，在这之前的索引结构只支持精确匹配查询，MHR-tree索引首次将近似串匹配(Approximate String Matching,ASM)引入空间查询当中；Alsubaiee等[5]提出了LBAK-tree内存索引结构，在Yao等的基础上确保索引代价和查询代价之间保持平衡；Wang等[6]提出的RB-tree将位图引入索引结果当中从而提高查询速率结果的准确性；Hu等[7]将近似匹配应用到周边查询.

这些算法都将近似匹配应用到空间关键字查询算法当中，确保查询的可用性，然而存在一些不足例如：①关键词长度变化使得阈值不能固定，阈值偏大可能造成查询结果的冗余，偏小不能保证结果的召回率.②查询空间空间数据信息人数增多，当要求频繁返回空间关键词时，上述算法不能保证时效性和准确性.本文提供支持多子串近似匹配的空间关键词查询需要面对一些挑战：首先，在阈值大小不变的情况下如何保持原有的匹配效果；其次，需要设计支持容错的相关函数，并返回用户高效的结果.

基于以上表述，本文的主要贡献如下：

1)首先设计支持多子串近似匹配的空间范围查询的索引结构.与以往的索引结构相比，在空间近似匹配中不需要根据关键词的长度来改变阈值的大小，而是将编辑距离融入倒排索引中，减少查询的时间复杂度和空间复杂度.

2)依据该索引结构提出高效的Top-k[8-10]算法.

3)通过真实数据进行仿真实验，用结果证明该算法的优越性和可行性.

1.2 相关知识

在研究领域中将查询的空间-文本双属性对象称为(Spatial-textual Object)，SKQ[11]中将包含查询的位置属性(o.loc)和文本属性(o.kws)作为查询条件，从空间数据库中返回满足位置属性o.loc以及与o.kws的文本信息的对象集合，并通过排序公式o.f排列输出.其中文本属性包含对象多个关键字(k1,k2,…,ki),这些关键字都是对位置信息的描述，关键词的错误输入、空间数据库[12]的存储误差都会导致数据不能有效的返回，q-gram[13]倒排索引的引入就是为了解决这些问题，提高空间数据查询的可用性.

2 支持多子串近似匹配空间索引结构建立

2.1 支持多子串匹配的q-gram索引结构

q-gram索引是将q-gram作为索引项的倒排索引结构，索引项为多个固定的长度为q的字符串,通过索引项与数据库中的文本数据进行匹配，并设定阈值大小，来对索引项进行近似匹配.但是查询空间关键词的长度不同，所设定的阈值大小不相同，本文对查询的空间关键词进行再处理，分割成等长的子串，对多个子串的编辑距离进行计算，最后把得到所有的子串哈希地址进行并集运算，得到最后的结果集.

给定q值，创建索引预处理过程如下：

第1步：设置哈希表HT，该表由长度为σq的数组组成，为更好的查询文本库中的文件位置和查询关键词近似串在T中的位置，设置文件顺序表FT.在文件顺序表中记录每个文件的路径和文件尾字符在T的位置.

第2步：建立词汇表，词汇表是T中所有不同q-gram索引集合，由于是基于R树建立的空间索引，所以采用哈希表对词汇表存储.并将文本库中字母表与整数进行一一映射，映射公式如下：

定义1 采用Karp-Rabin函数作为哈希函数，以此将任何长度的字符串映射成为唯一的整数.该公式如下:

(1)

其中：S就是长度为q的索引串，n=q，S[i]是索引串中第i个字符.H(S)就是S的哈希值.在连续的重叠q-1个字符子串的哈希值可以通过前一个哈希值计算出，既不用重复使用公式(1)，如式：

(2)

依据式(1)、(2)定位查询关键词在词汇表中的位置.并把索引串对应的位置添加到倒排索引当中.

第3步：建立倒排索引表.当文本库中的所有文件处理完成，索引建立成功.

2.2 任意多连续子串地址集合计算思想

例1 假设查询关键词的查询子串的长度为m,q-gram索引中存储了文本数据库T中所有长度为q的字符串位置集合，依据查询子串长度m不同，可将分为三种不同的方法进行讨论.

1)当m=q时，按照经典q-gram算法计算哈希值，找到与哈希值对应的倒排列表，查询串子串在文本库T中的位置集合.

2)当m>q时，由于查询子串长度大于索引项长度，所以需要多个索引项对子串分割.设查询子串为supermarket，q值为4，如图1， 该子串位置可由索引项‘supe’、‘rmar’、‘rket’确定.

图1 子串长度大于索引项长度的倒排地址Fig.1 The length of the string is longer than the index entry

算法思想：把查询子串进行拆分，使查询子串的长度和索引串长度相同，当mmodq≠0则在最后长度小于q子串向前重叠，在图2中索引串rmar与串rekt重叠一个字符r，记最后索引串位置为m-q.当mmodq=0时，按照原q-gram算法执行查询即可.

他把如何与老梅有染，又如何想和老梅分手，老梅不干，为了摆脱老梅，自己对老梅就下了毒。然后，拿走了她一些值钱的东西。

3)当m

构造式(2)得：

(3)

(4)

合并呈等差数列的倒排文件列表得到最后的地址集合M.

最后将构建的新的q-gram倒排索引引入支持空间关键词查询的RB-tree索引机构中，以此处理以往研究中阈值不确定的问题.

3 基于RB-tree的多子串查询算法

查询空间关键词最直接的方法就是按照关键词的编辑距离阈值以及相似度进行搜索匹配，然后根据空间距离远近进行排序，最初的空间关键字查询都是将空间数据的经度和纬度分开存储，查询时需要遍历所有的数据才能找到相应的位置，为此将支持空间关键词近似查询的RB-tree作为该算法索引结构，该索引树与IR-tree相似，将空间与文本两种属性有效的结合起来.

3.1 RB-tree索引

RB树是在R树的基础上加入两个位图长度位图LB和Gram位图来支持空间关键词的近似匹配，在该索引树中，SMS集合中的关键词，可以在LB的基础上进一步减枝，通过式(3)计算节点中关键词的Gram位图，一旦小于阈值，则直接抛出；在以N为根节点的RB树中，每一个节点不仅包括两个位图，为实现对关键词权值计算，在节点中增加倒排文件，该文件是由每个文档中的词频矩阵按照相关顺序排列的关键词集合.

RB树中每个非子节点Ni存储内容为(P，Ni.LB，Ni.GB，MBR，Ni.DI，Ni.CS).

其中P表示节点对应的磁盘位置；Ni.LB表示该节点的长度位图；Ni.GB表示Gram位图；MBR表示最小矩阵区域；Ni.DI表示该节点倒排文件；Ni.CS表示子节点相关信息.叶子节点Nj存储内容包括(P，MBR，Nj.DI)，在索引树当中，叶子节点的位图都是由关键词集合得来的，而父节点的位图是由子节点位图得来.

改进的支持多子串匹配的RB-tree结构如图2.

3.2 基于RB-tree的多子串查询算法

算法：基于改进RB-tree的Top-k算法

输入：空间查询词K，q-gram索引项长度q，i=0；

输出：空间查询词K在倒排索引中位置S，及Top-k结果

步骤1:计算查询关键词K长度m，对K按照索引项长度进行连续不重叠分割，获取多个等长度的索引项,如果最后索引项小于固定索引项长度q，对该索引项向前移动，如图1所示，直到索引项长度等于定长q，记最后一个索引项在K中的位置为m-q.

图2 改进支持多子串匹配的RB-tree结构Fig.2 Improved support structure of multi string RB-tree

图3 查询两次的q值分析Fig.3 q value analysis of query two times

步骤2:按照式(2)计算查询关键词中首个索引项在数据存储中哈希值，并将与该哈希值相对应的倒排索引作为结果集S1，i=0.

步骤4：合并步骤2和步骤3结果集，得结果集合S.

步骤5：对查询的结果进行排序，根据每个结果的权重值进行排序，得到最相关的前n个结果.

4 实验结果与分析

实验搭建环境为Inter(R)Core(TM) i5-4590CPU，4GB安装内存，使用WIN8操作系统，试验数据来自百度地图中获取购物中心及餐馆组成的11243个空间数据数据和396个不同的关键词集合.

实验过程中，首先对q值进行分析，当仅查询单次时，当索引项长度q与查询目标长度相同时，查询速度最快，本实验将对多次空间位置进行查询，并统计不同q值对搜索时间的影响，并用通过多次实验消耗时间的平均数来确定q值的选取.

首先，查询次数为2次时，选取查询关键词长度为7和10，如图3表示，随着q值不断增加，索引时间慢慢减少，这是因为随着索引项长度增加查询地址减少，并在查询词长度与q值相同时查询时间最短，当q值不断增大，消耗时间有有轻微上升趋势，当q值长度等于最长查询词时，时间消耗最小，这是因为地址集合的交运算大于地址集合的并运算.

然后对查询三次时的时间进行实验，如图4可看出，与查询两次影响相同，都是q值等于最长查询词时，查询时长最小，效率最高.因此，实验中q值设为9.本文的研究是支持多空间关键词Top-k查询算法，最后验证该算法的可拓展性，因为是基于RB-tree的改进，所以与原有的Top-k算法进行比较，如图5.

当k值较小时，改进算法的消耗时间与原有算法相近，但随着取值不断增大，改进算法查询效率高于原有算法.

5 结论

本文设计了支持多子串近似匹配的空间关键词查询算法，针对该算法，首先对RB-tree进行改进，在节点中加入支持多子串近似匹配的q-gram倒排索引，随后，在该索引结构基础上提出了相对应的Top-k查询算法，最后通过实验真实数据表明，该算法能够有效的支持空间关键词查询，并为以后的多空间关键词查询奠定一定基础.

图4 查询三次的q值分析Fig.4 q value analysis of query three times

图5 Top-k查询结果 Fig.5 Top-k query results

[1] LIU X P,WAN C X,LiIU D X,et al.Survey on spatial keyword search [J].Journal of Software,2016,27(2):329-347.

[2] 周傲英,杨彬,金激清,等.基于位置的服务：架构与发展[J].计算机学报,2011,34(7):1155-1171.

[3] 陈翀,陈楚南,孙未未.无线数据播环境下的空间关键字查询[J].计算机研究与发展,2013,50(S1):145-153.

[4] YAO B,LI F F,HADJIELEFTHERIOU M,et al.Approximate string search in spatial databases[C]//Proc of the ICDE,Washington:IEEE,2010:545-556.

[5] ALSUBAIEE S,BEHM A,LI C.Supporting location-based approximate-keyword queries[C]//Proc of the SIGSPATIAL GIS,New York:ACM Press,2010:61-70.

[6] WANG J B,GAO H,LI J Z,et al.An index supporting spatial approximate keyword search on disks[J].Journal of Computer Research and Development,2012,49(10):2142-2152.

[7] HU J,FAN J,LI G L,CHEN S S.Top-kfuzzy spatial keyword search[C]//Chinese Journal of Computers,2012,35(11):2237-2246.

[8] ZHANG D X,TAN kL,TUNG A.Scalable top-kspatial keyword search[C]//Proc of 16th Int Conf on Extending Database Technology(EDBT2013).New Work:ACM,2013:359-370.

[9] SILBERSTEIN A S,BRAYNARD R,ELLIS C,et al.A Sampling-Based Approach to Optimizing Top-kQueries in Sensor Networks[J].Icde,2013:68-68.

[10] ROCHA-JUNIOR J，GKORGKAS O,JONASSEN S,et al.Efficient processing of top-kspatial keyword queries[C]//LNCS 6849:Proc of the 12 th Int Symp on Spatial and Temporal Databases(SSTD2011).Berlin:Springer,2011:205-222.

[11] 李艳红,李国徽,张聪.路网中空间关键字连续k近邻查询算法研究[J].华中科技大学学报(自然科学版),2013,41(12):54-58.

[12] 张榆,马友忠,孟小峰.一种基于HBase的高效空间关键字查询策略[J].小型微型计算机系统,2012,33(10):2141-2146.

[13] 孙德才,王晓霞.一种支持多种子近似串匹配的q-gram索引[J].计算机科学,2014,41(9):279-284.

责任编辑：时 凌

Support Multi Approximate String Matching Keywords Space Query Algorithm

ZHANG Suzhi，DING Wenxue，XU Jiaxing

(School of Computer and Communication Engineering,Zhengzhou University of Light Industry,Zhengzhou 450002,China)

With the rapid growth of spatial data,POI (Points of Interest, referred to as POI) is becoming more and more intensive, and the text description of each spatial point is also gradually increasing. In previous key words approximate query algorithm, the key words of different length match with different thresholds,which affect the efficiency of query and query results. In view of the above problem is proposed to support multi space on the approximation space of keyword matching query algorithm, in this algorithm, it is not needed to consider the change of threshold, because edit distance is directly applied to the index structure. The simulation results show that the proposed algorithm can improve the accuracy and efficiency of query.

spatial database;q-gram inverted index;query algorithm;RB-tree

2016-08-16.

国家自然科学基金项目(61201447).

张素智(1965- )，男，博士，教授，主要从事Web数据库、分布式计算和异构系统集成的研究.

1008-8423(2016)03-0241-05

10.13501/j.cnki.42-1569/n.2016.09.001

TP301

A