空间查询处理技术综述

顾雨婷 金 冉, 韩晓臻 陈 刚 寿黎但

1(浙江万里学院大数据与软件工程学院 浙江 宁波 315100)2(浙江大学计算机科学与技术学院 浙江 杭州 310027)

0 引 言

随着定位服务LBS(Location Based Service)的快速崛起，越来越多具备无线通信功能的智能移动设备出现在我们的日常使用中[1]。智能手机等终端设备都部署了地理应用及定位系统[2]，使得无线数据服务成为了工业界和学术界研究的一大热点。空间查询处理技术作为一项用于处理LBS请求的重要技术[3]，近年来专家学者对这项技术的深入研究从未止步，且取得了众多喜人的研究成果。本文着重对现有的空间查询处理技术进行全面系统化的总结与综述。

1 问题描述

1.1 空间查询处理的相关概念

空间查询(Spatial Queries)是指利用空间索引技术，从海量的空间数据库中找出满足给定空间条件的空间实体。与传统查询不同的是，空间查询是由地理数据库支持的数据库查询。关于空间查询处理技术，大部分现有的研究都是基于欧几里德空间的，近年来，研究者考虑到了道路网络中的空间查询处理[4-8]。作为数据挖掘应用的核心，无线数据广播环境下的空间查询技术得到了国内外研究者的广泛关注。

在无线数据广播技术条件下进行的数据信息访问主要有两种基本方法：点对点访问(按需访问)和定期广播。对于点对点访问，移动客户端向服务器端递交查询，服务器端按需处理查询并通过预先建立的点对点信道将查询结果返回至移动客户端。文献[5,8]讨论了道路网络中基于点对点访问的空间关键字查询处理问题。然而，这种传统的用户与服务器的点对点通信存在网络超载和隐私泄露的缺点。

为了克服点对点访问的缺点，学者们开发了无线数据广播模式[9]，客户端通过调谐信道来检索数据查询所需的信息。定期广播通过避免上行链路传输来节省客户端的耗电量[10]，且服务器只需监控数据对象的信息即可满足任意数量的移动客户端查询需求[1]。无线广播模式具有高扩展性，适用于重载系统，能够有效保护客户端隐私。研究者对基于数据广播模式进行空间查询处理已做了深入研究[11-15]，但定期广播也存在按序访问和延迟较大的缺点。

1.2 无线广播系统的主要性能指标

在无线广播信道上检索信息时，服务器通过无线信道周期性的将数据广播给客户端，而移动客户端通过调谐信道来检索需要的信息并在本地进行查询处理。传统技术利用基于磁盘的索引[7,16-18]加速道路网络中的空间查询处理，这种索引模式用于点对点的随机访问方法，减少查询过程中的访问延迟。而无线广播模式支持顺序访问，相关学者研究引用定期广播的空中索引，将索引位于广播周期的数据前端来降低客户端查询时的调谐时间。

用于衡量客户端性能的有两个关键参数，即广播访问效率和能量消耗。为了降低能耗，移动用户端的设备通常存在休眠态和活动态两种工作状态。当广播信道暂未广播至客户端所需的数据，设备无需接收数据时处于休眠态，休眠态的能耗远低于活动态，因此可以大大降低客户端的使用能耗。访问延迟和调谐时间是无线广播系统的主要性能指标[19-20]。访问延迟表示从查询被调用到收到结果那一刻所经过的时间。调谐时间表示客户端收听广播信道所花费的时间[21]。

1.3 空间查询语言

查询语言是与数据库交互的主要手段，采用关系数据库的结构化查询语言(SQL)不支持空间数据类型和空间查询与分析。为了处理包含位置信息的空间数据及以GIS为代表的空间信息技术，研究者在空间数据类型和空间操作函数的基础上，对标准SQL进行扩展，实现了能够处理空间数据并进行空间分析的空间查询语言[22-24]。

2 空中索引技术

空中索引携带数据对象的相关信息，并将其广播至移动客户端，客户端通过检索空中索引来确定查询所需数据段到达的时间，并进行访问，空中索引技术通常用于节约移动客户端的能耗[1]。(1，m)索引方案[21]是无线广播周期中最常见的索引结构。如图1所示，(1，m)索引方案将整个广播数据段划分为m等份，并将索引信息放置在数据项的每个1/m分数之前进行广播[13,21,25]，索引在一个广播周期内广播m次，移动客户端可通过检索索引信息预测查询数据到达的时间，并在数据段到达时再调入广播信道。(1，m)索引方案中重复的索引信息延长了广播周期，所以需花费较长的时间来响应索引，增加了访问延迟，但是，它有效降低了查询的调谐时间。

图1 (1，m)索引方案

3 研究现状

空中索引用于定期广播的方法，移动客户端通过空中索引来检索用户查询所需的数据内容，数据检索是空间查询处理领域中的一个重要内容，检索的效率将直接影响到数据查询的效率。使用索引可有效减少访问延迟和调谐时间，从而降低客户端能耗，提高空间查询处理效率。针对无线广播环境下的空间查询处理，国内外有许多研究成果，大致可分为三类：欧式空间下的空间查询处理、道路网络环境下的空间查询处理以及无线广播环境下的空间查询处理。

3.1 欧式空间下的空间查询处理

早期的空间查询处理方法只考虑欧式空间中的查询，图2讨论了支持空间查询处理的多种索引结构。

图2 空间查询处理的索引结构分类

(1) 基于R树的索引 R树索引结构[26]是用于空间查询的基本索引结构，图3表示出了二维空间下的最小边界矩阵，图4则是它相对应的R数索引结构。文献[20]描述了在传统的顺序访问R树上进行精确的kNN搜索，并对已建立的kNN搜索算法进行优化。文献[27]提出的改进基于R树的kNN查询处理技术允许kNN搜索从广播周期的中间开始。R树的变体R*树[28]也是一种传统的空间索引，可以有效地支持无线广播环境中的范围查询，但无法进行类似于kNN查询[29]这类查询结果不确定的空间查询处理。另有学者研发了一种混合索引结构[30]，这种索引结构将倒排索引和R*树结构相结合用于处理空间关键字查询，且不同的组合方案能够处理相应的空间查询处理。文本优先的方案可用于处理范围查询和布尔kNN查询，空间优先方案用于处理范围查询和Top-k查询。文献[31-32]提出了基于R树变体的索引结构，这种索引结构在计算最小边界矩阵时合并相似文档，适用于处理范围查询和布尔kNN查询。另有D树[33]结构可用于处理无线广播环境中的NN查询。

图3 最小边界矩阵

图4 R树索引结构

(2) 基于网格的索引 在文献[34]中，Mouratidis等提出了适用于快照和持续查询的广播网格索引方法BGI，由于网格单元的尺寸小且能够有效更新查询对象，BGI将网格单元作为索引。文献[35]引入了一种称为网格分区索引的新型索引方法，网格分区索引是基于维诺图构建的，它在支持按需访问和周期性广播的模式下进行NN搜索[36]。另外，文献[37]讨论了基于网格的地理文本索引问题，且提出了两种基于网格单元的索引方案，即空间基本索引(ST)和文本基本索引(TS)。研究人员还提出了几种相似的网格索引[38-40]来处理空间查询处理工作。

(3) 基于空间填充的索引 基于空间填充的索引结构通常将倒排文件与空间填充曲线相结合，如希尔伯特空间填充曲线和Z曲线。文献[41]提出了一种倒排文件与希尔伯特曲线相结合的索引结构，且在文献[42]中提出的几种混合索引结构中，SFC-QUAD索引结构是最优的。这种索引结构将倒排文件与Z曲线结合在一起，通过遍历四叉树的方式获取Z曲线的顺序，并使用优化方法来压缩倒排文件，使得SFC-QUAD索引能够有效地处理范围查询。

(4) 其他类型的空间查询处理 文献[25]提出了一种通用的客户端-服务器体系结构，实用新型空间查询处理算法来支持无线广播环境中的移动连续最近邻查询(MCNNQ)。文献[43]讨论了给定移动的空间查询和关键字的Top-k空间关键字查询的处理问题。文献[44]讨论了给定具体位置、方向和关键字的方向感知空间关键字查询问题。文献[45-46]讨论了反向空间关键词最近邻查询，它返回最符合条件的k个答案。文献[47]和文献[48]分别介绍了一种新颖的空间关键字覆盖问题和级别感知集体空间关键字(LCSK)查询问题。

然而，上述方法只能在欧几里德空间中运行，但现实生活中对象的运动是受道路网络限制的，因此这些方法不能直接运用在真实道路网络中。

3.2 道路网络环境下的空间查询处理

道路网络是一个表示为G=(V,E)的二维空间，其中V是对象节点的集合，E是边的集合。每个节点v=(v.x,v.y)表示道路交叉点或路网中的对象节点的位置，每个e=(vi,vj,w)表示节点vi和vj之间的路段，其中w为边的长度。节点和边是道路网络的基本要素。

在传统的空间数据库中，道路网络中的空间查询处理已经有了很多的研究成果。文献[16]利用R树来存储数据对象以及路网中的道路交叉点和路段，同时提出了IER和INE两种算法来处理用户查询，查询效率取决于路网中的对象密度。道路网络的运行模式与普通地理空间系统不同，由于路网中对象受限于网络上的位置，M-Tree索引[49]能够索引任何度量空间中的数据，结合截断路网嵌入(tRNE)的M树索引可进行路网中的范围查询及kNN查询处理，适合于远距离查询处理的大型系统。

文献[18]提出了一种基于NVDs的VN3方法来处理kNN查询。另外，网络嵌入框架[7]、基于DS的方案[50]以及最短路径四叉树(SPQ)[17]都被用来处理kNN查询搜索问题。在道路网络中处理多个kNN查询，文献[51]提出了渐进技术，这种技术有选择性的将查询结果缓存在主存储器中，并将其用于查询处理。另外提出的六种缓存算法中，“懒惰”聚类方法在大多数情况下的性能是最优的。文献[52]讨论了空间网络数据库中基于组的k最近邻查询(GKNN)，使查询所获得的一组兴趣点到一组查询点的网络距离之和最小化。为了处理道路网络中在线LBS应用的kNN查询问题，研究人员将研究重点从改进查询处理时间转移到了用户查询的响应时间问题。文献[53]提出了一种新的查询框架，称为SHI。SHI框架中包含查询处理和列队处理的操作，逐组进行查询检索，减少用户查询的等待时间。文献[54]还研究了道路网络上反向空间和文本k最近邻(RSTkNN)查询问题，将网络邻近度和文本相关性结合，且提供了几种空间关键字修剪方法来过滤大量不合格对象，最小化搜索空间，将两种有效的验证技术集成到RSTkNN查询中。

但是，IER、INE和NVD三种代表性的方法都存在着低效率的问题。因此，文献[55]提出了一种单波前启发式搜索(SWH)的kNN算法，利用一种新的启发式功能，显著减少内存处理成本组件和空间网络访问成本。为了解决CkNN查询问题，研究人员提出了基于逐步增量网络扩展技术(PINE)的DAR算法和eDAR算法[56]。相比基于VN3的方法，eDAR能够花费更少的响应时间来进行最短距离计算和kNN查询。文献[57]中提出的IMA算法和GMA算法同样适用于处理道路网络中移动客户端的CkNN查询处理问题，且监测查询对象和查询点的移动，及时计算更新查询结果。这些方法会在客户端略微移动更新时返回两个重复的查询结果，一种包括修剪和精炼的方法[58]可解决这一问题，但这种方法存在客户端需以固定的速度进行移动的局限性。针对这一局限性，文献[59]提出了一种有效的方法来处理道路网络中以不确定速度移动的客户端的连续kNN查询问题。

随着基于位置的服务(LBSs)的快速发展，空间数据库作为LBSs的核心组成部分，文献[60]将位置相关信息和用户查询分别称为空间对象和位置相关空间查询(LDSQ)，并且提出了一种用于处理位置相关空间查询(LDSQ)的系统框架ROAD，能够有效降低网络遍历耗时。为了解决LBS在处理路网中空间查询处理所产生的用户位置隐私问题，需要基于网络的匿名化处理框架(NAP)[61]对用户的位置进行模糊处理，并在保证用户隐私的基础上实现低计算通信成本和查询处理的快速响应。

为了提高查询效率，许多研究人员开始设计分布式空中索引来优化路网中的空间查询处理。文献[62]中提出了一种将底层道路网络的网络维诺图(NVD)结构划分为一组网格单元并对网格单元进行编号的方法，并且基于这种方法讨论了基于NVD的分布式空中索引NVD-DI[13]来处理CN3B查询。当查询点附近存在足够多的数据对象时，对比高精度的网络距离范围检索，近似查询与精确查询具有一样甚至更好的效果，且查询处理的成本更低。文献[63]中提出了ARER和ARNE两种方法。ARER确定道路网络中静态点周围感兴趣对象的位置，通过减少查询预计算的次数尽快获取查询结果；ARNE则是在预定义的路径内确定兴趣对象的位置，从而排除位于下限与搜索范围之内的任何节点，减少预先计算和错误对象数量。

大部分研究者都关注在无向道路网络，文献[64]针对有向道路网络中的Top-k空间偏好查询进行研究，提出了一种名为PSA的偏好查询搜索算法，基于特征对象的修剪与分组最小化用于数据对象排名所耗费的查询处理成本，有效缩短查询处理时间。图5呈现了一个有向道路网络中的top-k空间偏好查询示例。另有研究者提出了一种新类型的查询，即反向Top-k布尔空间关键字(RkBSK)查询[65]，采用考虑空间和文本信息的修剪启发式算法来缩小检索空间。在网络环境中，空间对象Top-k查询算法的查询效率是衡量查询性能的重要指标。文献[66]对传统的基于Top-k空间数据的快照查询方法和连续查询方法进行了改进，采用了底层快照查询算法来解决单个关键字查询的空间问题，使该算法的通信消耗和通信频率均小于STM算法。

图5 有向道路网络中top-k空间偏好查询的示例

3.3 无线广播环境下的空间查询处理

无线数据广播是向道路网络中的客户端传播数据的有效策略。在无线移动环境中，由于低带宽，有限的能量和容量以及移动性，空间查询处理是一个具有挑战性的问题。由于无线广播环境具有较高的可扩展性，并且能够同时向大量移动客户端发送信息，学者们开始研究无线广播模式下基于位置信息的查询(LBQ)处理问题。

为了适应无线数据广播环境，文献[67]研究了通过R树索引在广播环境中处理NN搜索，而文献[27]提出了在广播R树上进行高效地kNN查询搜索。无线广播环境中的新索引ISW[37]通过合理的机制及预计算界限，可以有效处理基于ISW的kNN搜索、范围查询和RNN查询。文献[68]采用无线广播模型来提供路网中的LBSs，提出EB和NR两种方法支持最短路径计算，并在此基础上提出了一种称为BagIndex[69]的空中索引，用于道路网络中的最短路劲查询处理，有效降低客户端能耗。随着移动客户端数量的增加，空间查询处理对于可扩展性的要求越来越高，文献[70]采用无线广播模式令移动客户端收听广播并在本地处理查询。

另有研究人员提出了一种基于网格单元的非平面广播分布式索引GDIN[71]的数据调度方案。它能够使关注度高的查询对象在广播信道上高频率的出现，可用于窗口查询处理，使移动客户端只访问用户查询所需的数据项。基于最大边界矩阵的分布式空中索引DAIM[13]使用MaxBRs来过滤无线广播信道上的热门数据项，并在广播周期内重复热门数据，从而缩短广播周期的长度。网络分区索引NPI[1]将道路网络划分为多个区域，构建空中索引来携带每个区域的预计算信息，并且通过无线广播周期地广播至移动客户端，从而进行高效的空间查询处理。NPI的索引结构包含三个部分，如图6所示。

图6 网络分区索引(NPI)结构

但NPI并不是一个完全的分布式索引结构，针对NPI没有解决的带宽、移动性等问题，研究者基于NPI的空中索引提出了一种称为SAI[72-73]的空间空中索引，这种索引使用最优混合广播(OHB)调度和自适应协同缓存(ACC)，能够用于道路网络中的空间查询。SAI相较于NPI具有更高的查询性能，且降低了能源消耗和搜索空间。文献[74]又提出了一种基于NPI的混合空间空中索引(HSAI)，其中混合广播调度，基于自适应XOR的网络编码和自适应协作高速缓存能够有效地用于道路网络中的空间查询。

基于扩展的希尔伯特曲线，完全分布式空中索引IEI[75]划分底层路网传感器网络，可用于处理kNN查询、CkNN查询和范围查询。但是，当网格单元较大时，广播周期的帧数也会变多，IEI索引必须多次传输才能使移动客户端获取所查询的数据。由于适合广播环境的索引结构必须考虑数据传递的顺序，索引大小和选择性调整。文献[76]研发了一种基于网格的轻量级比特序列空中索引，称为二进制四叉树，该索引允许对数据进行顺序搜索和选择性调整，所提出的空间搜索算法在范围查询和k近邻查询中能够以最小的访问延迟和调谐时间提供准确的检索答案。

此外，研究人员针对传感器网络[77-82]也做出了许多相关的工作。在无线传感器网络中种构建空中索引的基本任务之一是确定传感器能够快速准确的参与区域查询操作，而大多数现有的研究工作仅仅集中于为单个属性的传感器构建空中索引。文献[83]提出了一种新的节能启发式密度聚类模型，用于构建一个多属性的空间索引树，这种索引结构称为MFSI树。它将多属性传感器的节点组织成树层次结构，可以有效地在索引树中进行多区域属性的聚合查询，利用MFSI树的多查询聚合技术可以显著降低能耗，延长网络生命周期。与此同时，现有的WSN中的带宽资源有限，根据数据存储模型的特征，基于数据属性的空中索引SIQ[84]主要用于查询WSN中的节点信息，SIQ只存储用于构建索引的叶节点，且SIQ使用的数据属性是空间索引的内容，故构建此类索引的成本较低，能够有效监控数据并进行多属性范围的查询操作。

近年来，如何提高空间查询效率、能耗最小化以及最大限度降低路线成本仍然是研究者们的关注热点[85]。为了解决无线广播环境下道路网络中的空间关键字查询处理问题，文献[86]提出了一种新的索引策略，即时空文本索引结构ST2I，它采用无上下文的文本映射算法对文本进行数字编码，减少内存占用和无关对象的检索数量，降低查询处理时间。文献[87-88]提出了两种近似算法和精确算法来处理道路网络上的集体空间关键字查询(CSKQ)问题。另外，文献[89]设计了一种四簇双滤波R树(QDR-Tree)的双层混合索引结构，用于处理属性感知空间关键字查询(ASKQ)问题。该索引基于层次聚类算法构建了四簇树(QC-Tree)，并使用kernel k-means聚类算法对关键字进行分类。

由于经济高效的云计算的出现，云计算可在服务器上虚拟化存储和计算资源，并向可信用户提供数据。基于MapReduce平台的真正的分布式空中索引方法M-Quadtree[90]和DIM[91]在MapReduce框架下构建了索引，满足了MapReduce的并行化要求，并在Hadoop平台上进行了查询与实验，有效减少调谐时间和访问延迟，极大地优化了查询的效率。

文献[92]设计了一种名为SKQAI的空中索引，它结合了路网加权四叉树、关键字四叉树和距离矩阵阵列，并提出了高效的算法用于处理布尔范围查询、Top-k查询和排序空间查询处理。文献[93]讨论了使用分布式R树索引的位置查询，它支持以并行方式执行查询，其性能优于空间R树索引。另外，在空间查询处理的应用场景中，我们不再只需要考虑单个用户，而是要考虑一组用户对于多个查询点的需求[94-98]。对于基于组的关键字感知路线问题(GKAR)查询问题，文献[99]提出了两种近似算法、两种精确算法以及一种贪婪算法来解决这个问题。一种面向数据的索引方法QUASII[100]通过逐步对数据进行排序的同时生成面向数据的层次结构，来减少数据反映时长并节约增量索引的成本。

3.4 空间连接查询

在空间数据库管理系统中，空间连接是一种重要操作，由于高复杂性和大量的空间数据，空间连接需要高处理成本。在欧式空间中，空间连接指的是在用户给定的两个或多个多维空间数据集中，检索出符合给出空间查询条件的一组空间对象对。而空间连接查询则是一种常见的多路查询，即从两个多维空间数据集中检索出满足空间谓词的空间对象，其中，空间谓词有如相交、相邻及包含等[101-102]。

在分布式空间连接查询领域，具有代表性的是二路连接查询与多路连接查询。目前，空间连接查询算法大致可以分为两类：基于直接连接的优化算法以及基于半连接的优化算法。文献[103]在半连接操作的基础上提出了一种SDD-1算法，该算法减少了数据查询的连接关系，从而降低连接查询时的网络传输数量。同样基于半连接操作的优化算法还有1-PSJ[104-105]等。另外，文献[106]提出的自适应多级算法以及文献[107]提出的站点依赖算法都是基于直接连接操作的优化算法，自适应多级算法利用平面扫描和双向节点的放大对距离对象进行快速剪枝，而站点依赖算法是对不同站点上符合用户查询条件的查询关系进行分片处理再将其合并。针对面向网络要素服务(WFS)的分布式连接查询，文献[108-109]分别介绍了哈希合并连接算法HMJ和对称哈希链接算法，将哈希表中的哈希值进行排序和连接。由于哈希连接算法需要花费较长时间进行排序，文献[110-111]都通过建立索引来优化空间连接查询。

4 研究展望

近年来，空间查询处理技术的发展取得了很大的进步，研究者们研发出了多种用于空间查询处理操作的高效空中索引以及相应的查询算法，但目前在空间查询这一技术领域内仍有许多问题需要进行改善，概括下来包括以下几个方面：

1) 传统多维数据索引的扩展性不够好，仅能够用于单服务器，在分布式空中索引的研究中需要支持多服务器的空间检索，进行并行构建，减少经典空间数据索引带来的空间冗余问题，改善数据量负载不平衡。

2) 基于线性化技术的空中索引可以对空间数据进行降维度操作，且支持高扩展性，并行度高，但该方法并不适合空间范围查询，在空间数据更新之后会出现数据不平衡的问题。

3) 针对有效处理多个查询的问题，以及一组查询用户的查询需求，需要研究的方向不仅包括查询区域和查询属性的重复，还包括解决值域重叠的问题。

4) 对于一些具备太多关键词的数据对象，研究的方向需要设计一个统一的成本函数来避免这一问题，并将成本函数与集体空间关键字查询处理相结合，扩展至其他的距离度量。

5) 不同空间查询算法的使用范围有限，将已经提出的查询算法扩展至其他查询类型，如天际线查询等也是一个很好的研究方向。

5 结 语

空间查询是从空间数据库中查找出满足用户条件的空间目标的过程，查找条件与空间位置有关。在许多应用领域，如GIS中，空间查询操作无处不在，且空间查询处理的性能是这些应用系统成功的关键所在。空中索引技术作为空间数据库的关键技术之一，其目的是为了在空间数据库中快速定位到所查询的数据对象，是快速、高效地查询、检索和显示空间查询处理结果的重要指标。

本文在对空间查询处理技术的相关概念和算法进行深入研究的基础上，总结了欧式空间、道路网络及无线广播环境下常见的用于空间查询处理的空中索引及查询算法，并详细描述了各类索引及算法的适用范围和优缺点。但是，对于移动客户端进行空间查询处理时所产生的访问延迟与调谐时间的平衡，仍需众多研究人员的不懈努力。