面向地理空间信息的轨迹模型及时空模式查询

轨迹数据处理与分析是目前空间信息和数据库等相关领域的研究热点之一。本文从Stop-Move轨迹模型出发,通过集成地理空间上下文信息来建模轨迹数据,并研究轨迹时空模式的查询处理技术。首先分析Stop/Move对象与点/线/面地理空间要素之间的时空关联关系,据此提出显式表达该关联语义的地理关联轨迹模型,在此基础上利用关系-对象数据库技术,为地理关联轨迹模型设计独立于应用的关系模式,接着定义轨迹时空模式查询,并提出基于地理关联轨迹关系模式的SQL处理框架,最后以典型性检索请求为例,讨论分析位置-时间、位置-顺序和位置-关系等三类轨迹时空模式查询的纯SQL处理技术,并以样例轨迹数据验证了本文方法的可行性。     

顾及轨迹压缩的车辆路径查询算法

基于位置服务技术的迅猛发展,产生了巨量车辆轨迹数据。为了有效压缩并查询大规模车辆轨迹数据,本文提出一种面向压缩车辆轨迹的路径空间查询算法。本文算法基于Stroke道路层次结构压缩轨迹空间数据,提取关键变速点压缩轨迹时间数据,并构建了一种用于建立轨迹空间和时间数据之间联系的哈希编码,从而实现车辆轨迹的时空数据集成压缩。利用后缀数组对车辆轨迹的基于Stroke路段的压缩编码构建空间索引结构,再以此为基础,设计了车辆轨迹所对应路径的点信息查询算法、相同子路径查询算法和相似路径查询算法。试验结果表明,针对原始轨迹点空间数据,本文的压缩编码方法压缩比可以达到97∶1,与常规的基于路段编码方式相比,本文压缩编码在车辆轨迹的点信息路径查询方面,查询效率可以提升约2倍;在车辆轨迹的相同子路径查询方面,查询效率可以提升约8倍;在车辆轨迹的相似路径查询方面,查询耗时增长率减少了50%。本文算法对于大规模车辆轨迹的数据管理具有十分重要的基础性作用。     

基于Phoenix的地理空间大数据管理系统

NoSQL数据库HBase已被众多应用系统作为存储和管理海量数据的解决方案,但HBase并未提供对地理空间数据的直接支持,因此提出了名为GS-Phoenix的地理空间大数据管理系统,GS-Phoenix构建在开源项目Phoenix和HBase之上。在插入空间数据时,GS-Phoenix自动以主键索引或二次索引方式生成基于空间填充曲线的空间索引。利用该空间索引,GS-Phoenix实现了矩形范围查询、不规则范围查询和k近邻(k nearest neighbors,k NN)查询等复杂空间查询所需的基本操作。GS-Phoenix利用用户自定义函数机制和服务器端排序机制将空间查询中的主要运算任务放置在服务器端,有效降低了客户端的计算负担。此外,GS-Phoenix还设计了基于数据空间分布统计的查询优化方法,进一步提高了空间查询效率。实验表明,GS-Phoenix能够在小规模的集群上实现17万/s左右的数据插入速率,常用的空间范围查询和k NN查询都可以在几百毫秒内完成,因此GS-Phoenix能够适用于各类具有高数据吞吐和实时空间查询需求的位置相关应用系统。     

基于Spark的城市居民出行时空特征快速提取

利用交通轨迹挖掘人类活动规律是实现智慧城市与生活的基础,然而常规方法已无法满足高效处理的大数据量要求。以海量出租车轨迹数据分析为例,设计了基于Spark平台的城市居民出行时空特征快速提取方法。借助Spark分布式计算框架,将核心算子匹配应用于二次排序、数据清洗及O/D点提取等预处理工作,并在时间分割和网格剖分统计的基础上完成时空特征提取。利用2014年8月份成都市出租车轨迹数据开展实验验证,结果表明,相较于传统单机环境,在确保准确性的基础上,该方法能够大幅提高特征提取的效率;集群节点一定时,数据规模越大优势越明显;数据规模足够大时,Spark集群节点数量越多,耗时越少。     

网格数据模型的行政区划演变展现方法

针对传统矢量数据模型在表达历史行政区划时空变化过程中存在数据结构复杂、处理算法难度大的问题,该文在中国历史地理信息系统(CHGIS)提出的“生存期”概念的基础之上,采用网格数据模型存储行政区划数据,将具有三维特征的时空数据存储于二维关系表中,建立包含全部时间序列和空间数据的行政区划时空数据库,并利用SQL语言查询行政区划数据的时空信息特征。结果表明,这种以形状相同、大小一致的网格单元作为行政区划数据载体的方法,结构简单清晰,操作便捷,利于查询显示和统计分析特定空间位置处历史行政区划演变的活跃程度及演变的规律特征。     

网格数据模型的行政区划演变展现方法

针对传统矢量数据模型在表达历史行政区划时空变化过程中存在数据结构复杂、处理算法难度大的问题,该文在中国历史地理信息系统(CHGIS)提出的“生存期”概念的基础之上,采用网格数据模型存储行政区划数据,将具有三维特征的时空数据存储于二维关系表中,建立包含全部时间序列和空间数据的行政区划时空数据库,并利用SQL语言查询行政区划数据的时空信息特征。结果表明,这种以形状相同、大小一致的网格单元作为行政区划数据载体的方法,结构简单清晰,操作便捷,利于查询显示和统计分析特定空间位置处历史行政区划演变的活跃程度及演变的规律特征。     

Geohash-Trees:一种用于组织大规模轨迹的自适应索引

蕴含着挖掘价值的轨迹数据分布在世界各地,且规模庞大。如何在全球范围内组织轨迹数据并支持高效范围查询成为难题。一种自适应索引组织框架被提出来管理查询全球范围大规模轨迹数据集,其基本思想为:针对不同轨迹数据集,根据Geohash编码,生成层数最深的Geohash格网覆盖住整个轨迹数据集范围;以格网作为根节点,生成Geohash-Trees;为了加快查询定位到对应索引,根据编码前缀相同的特点设计了字典查询树。Geohash-Trees是一种基于格网划分的空间索引,它能够根据轨迹密度自适应使用多种剖分策略划分空间,提高范围查询效率。为了支持索引动态更新,设计了增量插入和更新算法。同时,该索引被移植到商用数据库Oracle中,利用数据库性能高效管理查询轨迹数据。实验结果表明,该方法在范围查询以及占用空间等方面明显优于Oracle内置的R树索引。     

基于并行kNN的公路地理数据查询优化方法

根据公路工程地理数据的空间和属性特征,建立了一种倒排网格索引,通过坐标来反映空间对象在网格中的具体位置。重点探讨了k NN查询算法,对串行轮圈访问k NN算法进行了改进,打破了轮圈半径对其上一次遍历结果的依赖性,以网格边长递增的方式更新轮圈半径,并结合多线程技术实现了多个轮圈的并行访问。通过在模拟的海量公路空间数据集上的实验,从数据集规模、网格边长、k值选取等方面对比分析了两种算法的查询效率。结果表明,改进后的k NN算法对于大规模空间数据集的查询效率有很大提高。     

面向动态关联数据的高效稀疏图索引方法

为了高效组织管理日益增加的智能感知和关联关系数据,满足多层次任务对多模态场景数据多维特征计算和关联挖掘的需求,针对现有树结构外存索引方法存在的磁盘I/O密集、处理效率低、对关联关系支持弱的瓶颈问题,提出了一种时空关系稀疏图索引方法。设计了一种基于内存图模型的时空索引结构,将多模态场景数据抽象为图的节点和边,支持时间、空间以及关联关系的高效组织,并基于稀疏矩阵进行时空关系图索引的内存表达和存储;以多维树索引为例进行了索引构建以及多模式查询试验。试验结果表明,本文方法在索引生成、时空查询和复杂时空关系查询效率等方面均优于对比方法,支持动态关联的多模态场景数据实时高性能处理和低延迟访问。     

网络中移动对象的二维时空索引

基于2DSTMON(2-Dimensional spatio-temporal indexfor moving objects in network)二维时空数据模型,提出了一种新的二维网络中移动对象的时空索引2DSTI及其时空查询算法。这种二维时空索引机制简单且易于实现,支持当前轨迹数据和历史轨迹数据的大量时空查询操作。在此基础上,通过实验实现并验证了二维时空索引机制及其时空查询算法。     

浮动车轨迹点地图匹配及插值算法

针对带有定位误差和异常值的浮动车轨迹点数据,该文设计并实现了滑动窗口最优路径地图匹配算法,在综合考虑轨迹点的空间几何关系和路网拓扑关系基础上,为轨迹点匹配最优道路并纠正轨迹点误差。其次,针对稀疏且时间间隔不稳定的匹配后轨迹点,设计改进的Hermite插值法拟合车辆运动状态,并对稀疏轨迹点进行时序插值。利用南京市出租车轨迹点数据进行匹配算法与插值算法的验证,实验结果表明匹配算法具有较高准确性,插值算法能有效还原车辆行驶状态。     

地球剖分网格理论在影像处理中的应用

针对大区域遥感影像处理中数据组织和应用方面的技术难题,该文采用GeoSOT剖分网格体系理论的数据组织方法,建立影像型地理空间数据逻辑剖分与编码,同时提出了基于网格模板的影像按需快速拼接技术,依托空间剖分网格高精度的空间关系,直接从遥感影像中抽取所需的剖分面片进行几何拼图,实现了大区域遥感影像数据的快速组织和拼接,提高了数据浏览等应用的效率。在数据共享上,考虑到异构网络环境下数据实时共享的应用要求,设计了有限带宽条件下的智能传输策略。依托空间剖分网格天然的"多尺度、小面片"的特点,设计灵活的传输策略,在有限带宽网络条件下,以面片为单位,实现用户关心区域的目标信息的快速传输分发,改善数据传输效率和用户体验。     

多阶三角形数据结构的高阶Voronoi图算法研究

针对大多数传统高阶Voronoi算法复杂且运行效率低下,缺乏拓扑关系与多种邻近查询以及地理空间可视化交互与分析上的问题,该文借助Delaunay三角形天然优势,首先建立了一种k阶Delaunay三角形数据结构,利用k阶Delaunay三角剖分与k阶的Voronoi图存在的间接性对偶关系,提出了一种k阶Delaunay三角形数据结构的高阶Voronoi图的算法,并通过数据实验分析与对比,结果表明:该算法易于理解,程序设计简单易行,提高了运行效率,有效支持地理空间应用与几何学与拓扑邻近查询,满足实际应用的需要。     

地理要素的分布式空间近似查询处理方法

针对传统空间查询无法满足地理数据交互式可视化对处理时间要求的问题,以窗口查询为例,提出了一种空间近似查询处理方法。该方法包括预处理和查询两步:在预处理阶段,利用分布化的线简化算法对空间对象进行顾及误差的预处理采样,将采样过程及误差值用树型结构保存;在查询阶段,以豪斯多夫距离定义数据可视化的误差,进行误差可知的顶点即时采样与截取,从而实现针对可视化应用的高效的空间近似查询处理。在Hadoop集群上利用77GB的OpenStreetMap数据集进行了实验,证实了本方法的效力与效率。     

多维度轨迹数据的SQL时空查询方法

轨迹数据包含了时间、空间和身份属性等要素信息,数据量大且复杂,分析难度高。面对如此多维度并且数据量庞大的数据,分析前的数据抽稀、检索是必要的。通过SQL时空查询的方法进行轨迹数据的检索,选择合适的可视化方法,尽可能精准地筛选出兴趣轨迹数据,可以更大程度地支持大众用户对轨迹数据的分析需求。     

利用GPS轨迹二次聚类方法进行道路拥堵精细化识别

针对当前在精细识别道路拥堵时空范围方面研究的不足,提出一种利用GPS轨迹的二次聚类方法,通过快速识别大批量在时间、空间上差异较小且速度相近的轨迹段,反映出道路交通状态及时空变化趋势,并根据速度阈值确定拥堵状态及精细时空范围。首先将轨迹按采样间隔划分成若干条子轨迹,针对子轨迹段提出相似队列的概念,并设计了基于密度的空间聚类的相似队列提取方法,通过初次聚类合并相似子轨迹段,再利用改进的欧氏空间相似度度量函数计算相似队列间的时空距离,最后以相似队列为基本单元,基于模糊C均值聚类的方法进行二次聚类,根据聚类的结果进行交通流状态的识别和划分。以广州市主干路真实出租车GPS轨迹数据为例,对该方法进行验证。实验结果表明,该二次聚类方法能够较为精细地反映城市道路的拥堵时空范围,便于管理者精准疏散城市道路拥堵,相比直接聚类方法可以有效提升大批量轨迹数据的计算效率。     

基于多级信息网格的海量遥感数据存储管理研究

随着遥感探测技术的高速发展,空间信息呈爆炸式增长。针对目前现有遥感数据存储管理系统数据量大、数据来源丰富、查询检索慢等问题,本文提出了一种基于GeoSOT网格的遥感数据组织方案,并首次在关系型数据库中增加数组数据类型的剖分网格编码列,来存储遥感影像元数据中空间信息,对数据进行逻辑剖分索引,从而实现影像数据的统一存储与空间区域检索。试验选择Kingbase关系型数据库作为测试平台,通过模拟全球范围的影像数据,与Oracle平台进行对比试验。结果表明本文的检索效率具有明显优势,可有效提高遥感数据整合、检索效率,为现有遥感数据存储中心或管理系统提供了一种高效、可行的方案。     

一种集成R树、哈希表和B*树的高效轨迹数据索引方法

为兼顾时空索引方法的空间利用率、时间效率和查询种类,提出了一种新的轨迹数据索引方法——HBSTR树。其基本思想是:轨迹采样点以轨迹节点的形式成组集中管理,哈希表用于维护移动目标的最新轨迹节点,轨迹节点满后作为叶节点插入时空R树,另外采用B*树对轨迹节点构建一维索引,既有利于提升索引创建效率,又同时满足时空条件搜索和特定目标轨迹搜索等多种查询类型。为提升时空查询效率,提出了新的时空R树评价指标和节点选择子算法改进时空R树插入算法,同时提出了一种时空R树的数据库存储方案。试验结果表明,HBSTR树在创建效率、查询效率和支持查询类型等方面综合性能优于现有方法,支持大规模实时轨迹数据库的动态更新和高效访问。     

地球空间网格编码技术分析

地球空间网格是将地球空间区域剖分成不同尺度单元的空间参考系统。网格编码利用地理空间位置的结构化索引表达技术,将代码分配给地球空间网格系统的每个网格单元,实现网格位置的统一标识。对照统一规则递归剖分形成的多层次、多分辨率全球的地球空间网格系统编码的要求,本文在分析当前地球空间索引标识技术方法的基础上,探讨地球空间网格编码方案,以实现地球空间网格单元的统一标识,并可通过代码描述网格单元空间位置,反映网格单元间的空间关系。     

出租车数据的时间序列谱聚类分析

城市空间运行的出租车产生大量的OD数据,数据的时序呈现周期性特点,客观反映人们的出行行为模式,本文采用谱聚类算法对北京五环区域内各空间单元的出行特征及其相似性进行探究。由于空间单元的时空行为特征受空间邻域和功能区划的影响,研究添加邻域因子和功能区因子以改进时间序列的相似性度量方法,从而实现时间序列谱聚类算法的空间和功能区拓展,进而增加人们对不同时空条件下出行行为特征的了解,以便对不同空间单元提供差异性服务,如不同时段公交的发车频次、动态调整商场营业时间、不同时空环境出租车候车点的实时变换、调控和优化不同区域服务保障等,将有助于降低城市能耗,更加合理地利用资源,也有助于居民实现智慧生活。