2.1.2　空间查询

近年来随着地理信息系统[17]、计算机辅助设计、计算机图形学、基于位置的服务、超大规律集成电路、车辆导航系统、运输管理系统等应用需求的增长,空间查询与空间索引的研究一直是相关领域的热点主题,如计算机科学的数据库方向和数据挖掘方向、地理信息科学、计算几何等。特定的应用需求会产生新类型的空间查询,研究者提出新的空间索引及其算法以处理这些空间查询。不同的空间索引具有不同的适应性,其应用效果取决于空间查询的类型。

空间查询、空间数据分析与具体应用关系极为密切。具体的应用需求决定着空间数据管理的目标,同时决定了空间查询的模式与空间数据分析任务,进而决定着空间索引与查询算法的选择。图2-1为若干空间查询的资源消耗情况,可以看出,不同的空间查询在计算资源和I/O资源消耗上表现不同,其中,窗口查询消耗最多的I/O资源,但是具有较少的计算资源消耗。下面将从计算密集性、I/O密集性等维度来讨论空间查询的类型。

图2-1　空间查询的资源消耗情况

若将数据库的操作分为读/写两类,读/写数据的规模分为少量和大量两类。如果根据数据库的特点进行划分,可以分为简单操作与复杂操作,对于简单操作为主的数据库在实践中有一些值得注意的要点[27]。从地理空间科学的角度来考虑,空间数据库最常处理的查询之一是范围查询,其查询结果具有较大数据量,而其更新等操作则相对处理较小的数据量,因此空间数据库既包含简单操作,也包含复杂操作,读/写数据都较为频繁。对于执行关键字检索、属性检索的空间数据库,往往具有少量读写的特点;对于执行数据可视化类应用查询的数据库,则具有大量读,少量写操作的特点。本书所针对的全球精细尺度的地理要素数据库如OpenStreet Map,一方面需要处理空间范围查询,具有读取大量数据的特点;另一方面接受在线数据编辑与更新,具有实时操作的特点,既有大量复杂的读操作,也有大量复杂的写操作,类似于在线事务处理系统与数据仓库的混合体,因此对于其空间查询处理技术的研究,具有相当的挑战性。(https://www.daowen.com)

只包含空间条件的查询可以分为基于距离的查询和基于拓扑的查询。基于距离的查询包括空间范围查询(Range Query)、最近邻查询(Nearest Neighour Query)[28]、带约束的最近邻查询及同系列包含其他变化的查询类型[29-31];基于拓扑的查询包括最短路径查询(Shortest Path Query)[32-34]、最佳相遇点查询(Optimal Meeting Point Query)[35]、可达性查询(Reachability Query)[36]、距离保持子图查询(Distance-Preserving Subgraph)[37]等。空间范围查询是最为基础的空间查询,在二维情形下也被称为窗口查询(Windowing Query)。可以认为空间范围查询是范围查询(Range Query)在高维空间的推广,查询条件的略微变化会使范围查询有很多可能的情形,如三边范围查询(3-sided range Query)等。几乎所有的基本空间索引都是用于有效处理范围查询的,如R-tree系列[38-40]、四叉树系列[41]、KDBtree[42]、LSB-tree[43]、GiST索引[44]等,通常地理空间数据的维度不会太高,主要集中在二维到三维的范围内。理论上当维度增加时,大部分空间索引的性能会急剧下降,因此有部分空间索引是专为高维情形进行优化的,如UB-tree[45]以及X-tree[46]等。

除包含空间条件外,同时包含其他条件进行的联合查询是数据库领域近年的研究热点。查询类型主要包括空间关键词查询(Spaital Keyword Query)[31,47-49],最近邻关键字查询(m-Closest Keywords Query)[49,50]、空间天际线查询(Spatial Skyline Query)[51]等,这些查询往往同时运用空间条件和非空间条件对索引结构进行联合剪枝,以最快地减小候选集的大小,提高查询处理的速度。很多研究根据空间条件和其他搜索条件,如文本搜索条件等,来建立已有空间索引(如R树、四叉树等)的扩展,使之能够同时处理空间条件和非空间条件以最大效率地缩小搜索空间。

空间数据压缩及化简也是一项常见的应用。近年来,车辆轨迹化简是其中具有代表性的研究方向[52-55],主要讨论的是对于由GPSLogger设备所生成的轨迹数据,如何进行数据缩减。这些研究提出根据特定的查询类型来定义误差,并在顾及误差的情况下进行数据化简,通常采用顶点采样的方法,但也不回避引入新的顶点。大部分研究未讨论以下两个空间数据库应用中的重要问题:一是查询需要可视化的大量数据,二是数据更新。文献[56]对空间数据库进行采样以处理聚集查询,其主要思想是将采样从一般的数据库引入到空间数据库,然后用与采用相关的数据结构来管理和组织这些采样数据,主要方法为1/2采样,然后以扩展的R树组织采样数据。

由于空间网络数据规模的不断增长,近年来运用近似计算的思想对针对网络相关的查询进行近似处理也出现了很多成果,已有研究学者提出了利用特定损失函数对道路网络数据进行化简,并以简化的网络为基础进行相关查询的近似处理[33,57,58],以提高查询处理的实时性,同时有效约束处理过程中产生的误差,很有启发性。但是这些研究并未将窗口查询结果的规模控制作为目标。本书主要考查的空间查询类型是窗口查询,将地理要素的顶点采样结果作为窗口查询的结果,客观上达到了误差可控与时间可控的地理要素数据缩减,同时考虑空间数据库的数据更新及数据一致性保持等需求,在现有地理空间数据库的基础上构建为一个按顶点实时组织的地理要素近似查询引擎。