首页 >
论文范文 >
自然科学论文 >
自然科学综合论文 >
测绘学论文 >
适用于海量时空数据的多维检索方法的研究
摘要：针对当前常规方法无法满足大数据量存储与快速索引的问题,该文在分布式数据库HBase的基础上,设计了一种面向海量时空数据的多维检索策略。首先利用三维时空格网分割编码;然后将格网编码、感兴趣维度属性与HBase行键进行融合,设计了一种“时空+”可定制的多维索引结构,并给出了相应的检索策略和算法,较好地实现了多维数据的快速检索。基于2014年8月份成都市出租车轨迹数据的实验结果表明,相较于传统方法,所提方法能大幅度提升多维数据检索的效率,数据规模为1亿行时,耗时比达到319.79倍,且数据规模越大优势越明显;与Geohash空间降维编码相比,检索命中率明显提高,耗时明显减少。
加入收藏
移动互联网、卫星导航定位、基于位置的服务技术的普及产生了海量的时空数据[1,2,3],为城市交通态势感知、车辆行进路线规划、居民出行特征分析等提供了足够的数据支持[4]。与此同时,其多源异构、巨量增长的特征对数据存储及索引方法也提出了更高的要求[5,6]。
在时空数据索引方面,学者们提出了许多有效方法,包括基于版本的HR-tree和MV3R-tree索引[7],通过扩展时间维的TB和STR多维索引树[8],集成多种索引方法的HBSTR-tree[9]等,但仍然面临着索引创建效率低、未顾及数据存储、数据结构单一等问题。HBase[10]作为Hadoop大数据处理框架下的成熟开源数据库,兼顾异构数据快速索引与分布式存储,为海量时空数据的多维检索提供了解决思路。文献[11]基于HBase提出了UQE-Index索引结构,支持高吞吐的写入和多维查询,但结构设计复杂,维护困难。开源项目Hindex[12]实现了HBase多维数据的快速索引能力,但构建复杂,且对HBase原生机制侵入性大。文献[13,14,15]基于HBase采用Geohash编码和时间组合索引,但由于Geohash自身的局限性,使得在进行时空数据检索时效率受到了一定影响。
本文设计了一种基于HBase的海量时空数据多维检索方案,利用三维时空格网对数据进行剖分,融合格网编码及多维条件属性,生成HBase原生行键(rowkey)索引,结合相应的检索策略,实现海量时空数据的高效存储和多维检索。
1、索引构建及多维数据检索算法
1.1格网划分及索引结构设计
1.1.1三维时空格网划分
格网划分方法广泛应用于空间索引、影像金字塔、矢量切片等领域[16],可以实现对海量数据的快速存储和索引。如图1所示,本文利用“时间-经度-纬度”三维规则格网,对海量时空数据进行等间隔划分,为每个格网赋予唯一编码,编码长度根据实际分割情况确定。若格网原点坐标为(T0,Lon0,Lat0),则时空数据点(T,Lon,Lat)所在格网编码CTCLonCLat计算方法为:
式中:ΔT、ΔLon、ΔLat分别为时间、经度、纬度维度方向的间隔。需要注意的是,由于编码长度为定长,需要根据预设长度以0前置补齐。
图1三维规则格网划分示意图
1.1.2“时空+”索引结构设计
目前以三维时空检索、四维“时空+目标”检索为代表的多维检索需求愈发广泛,而HBase本身是一个稀疏、多维度、排序的映射表,由若干行组成,数据模型可以抽象为<行键:列族:列限定符:时间戳,值>,检索时虽然通过前4个参数定位数据,然而高效的关键在于行键(rowkey)相关算法的实现,为此,本文设计了灵活的“时空+”行键索引结构,在保留HBase原生机制的前提下,提升时空数据多维检索的效率,索引结构如图2所示。
图2“时空+”行键索引结构
Fig.2“Spatio-temporal+”RowKeyIndexStructure
由于HBase行键匹配顺序是从前往后,由高位到低位,位置越靠前对于检索的影响越大。考虑到时空检索的频率,本文将三维时空格网编码置于索引结构的高位,并在其后可定制追加多个感兴趣维度,最后以随机编码作为结尾保证行键唯一性。这样的行键结构设计首先保证了时空检索的效能,之后由于追加维度的存在,可以实现以时空维度为基础的多维数据索引。
1.2数据检索策略
结合设计的“时空+”多维索引结构和HBase的运行机制,本文设计了相应的数据检索策略,如图3所示。
图3数据检索策略
1)首先连接HBase表并输入检索条件,包括时空范围和其他维度检索需求。
2)根据输入条件计算检索覆盖的三维格网及编码,结合其他维度条件共同确定行键集合。
3)由于行键依字典序排列,其可能不唯一且不连续,因此在检索时需要对行键分组,确定每组起止行键值。
4)对行键组依次进行数据检索,采用外部过滤器对索引数据进行精确过滤,并将结果保存。
5)判断行键组是否遍历完毕,如果没有,则重复步骤4);如果遍历完毕,则检索完毕,输出结果。
1.3多维数据检索算法
依据提出的数据检索策略,以圆形区域的时空数据检索应用为例,对检索算法进行详细阐述。设定背景为:检索T0～Tk时间范围内,以(Lonc,Latc)点为中心,半径为r范围内的数据集合。算法步骤如下。
1)计算圆形区域最小外接矩形。根据中心点坐标及查询半径计算最小外接矩形范围,左上角坐标为(Lonl,Latl),右下角坐标为(Lonr,Latr),如图4所示。
2)格网覆盖计算。利用式(1)根据时空范围确定时间维所覆盖的格网CT0～CTk,外接矩形左上和右下顶点所处的格网坐标(CLonl,CLatl)和(CLonr,CLatr)。
图4圆形区域覆盖格网
3)构建行键索引并确定分组。如图5所示,行键索引主要由固定部分、可定制部分两个模块组成。固定部分为三维时空格网编码模块,用于时空检索;可定制部分为追加的一个或多个其他感兴趣维度的索引,如图5所示,Dnm代表追加的第n个维度的第m种属性。起止行键组则根据索引字典序确定。
图5起止行键组生成示意图
4)数据提取与精过滤。由于格网粒度的原因,根据行键提取的结果包含了部分无用数据,因此根据检索条件添加数据过滤器进行精确过滤,包括时间维度上利用时间戳进行精确圈定,空间维度上通过距离与半径r的比对判定等。
5)循环遍历行键组直至结束,输出结果。
2、实验结果与分析
2.1实验数据与环境
为了验证所设计方法的可行性,本文以2014年8月4—5日成都市13000余辆出租车06:00:00—24:00:00的轨迹数据为数据源,数据规模约为5000万行(2.5GB)/d,数据格式为{TargetID,Lontitude,Latitude,Status,Time},对本文设计的多维检索策略进行对比验证。
在实验环境方面,本文利用VirtualBox搭建7台虚拟机作为实验平台,配置均为单核4GB内存,操作系统均为CentOS6.5,Hadoop版本为2.7.5,HBase版本为1.4.0,zookeeper版本为3.4.10,Java开发包版本为jdk1.8.0_162,程序开发平台采用IntelliJIDEA2017.3.4x64,算法使用Java编写实现。
2.2时空检索效能分析
为验证方法在时空检索方面的正确性和效率,本文以成都市三环以内作为研究区域,(30.594099°,103.98316°,1407103200)作为三维格网原点,取ΔLat为0.00135415°、ΔLon为0.00180182°、ΔT为1h进行三维时空格网剖分和编码。
2.2.1时间维编码影响分析
为了验证时间维编码的影响,以(30.661285°,104.067273°)为原点,半径为200m的圆形区域作为待查询的空间范围,以2014年8月4日10:00:00作为起始时间,分别对10、30、60以及90min等不同的时间范围进行实验,对比分析本文编码方法和无时间维编码(仅保留空间维)两种情况下检索效能的不同,其结果如图6和表1所示。
图6时间编码对数据检索时间的影响对比
表1时间编码对检索数量及结果的影响
如图6所示,含时间编码的检索耗时明显要少,因为时空编码是对数据进行3个维度的切分,时间维的存在能在空间维索引之前,直接将数据检索范围锁定在包含时间范围的格网内,避免检索其他无用数据。此外,无时间维的方法在不同的时间间隔下检索耗时不变,这是由于查询的空间区域不变,其检索的数据范围也没有发生变化。本文方法在10、30、60min时耗时基本不变,而90min时耗时发生增长,这是所设定的时间维粒度为1h所致,因此前3种情况所覆盖的时间格网一致,检索数据范围也相同,而90min情况多覆盖了一个时间格网,造成了检索数量的提升。表1的检索数量以及命中率两个指标验证了理论分析的正确性。
2.2.2空间编码影响分析
为了验证空间编码的影响,以2014年8月4日10:00:00—11:00:00作为查询的时间范围,对以(30.661285°,104.067273°)为原点,半径分别为100、200、500以及1000m的圆形区域进行检索实验,对比分析本文格网编码方法、Geohash空间降维编码方法[15]以及无空间维编码(仅保留时间维)的检索效能。
实验结果如图7所示,无空间维索引方法耗时最多,相较于前者,Geohash方法有明显的性能提升,而本文方法优势最为明显,耗时最少。结合表2分析,虽然3种方法检索结果均完全一致,但无空间维索引方法的命中率明显远低于另外两种,原因在于本文方法和Geohash方法都对空间维进行了分割和编码,检索时能够通过空间维的编码索引,避免检索目标范围之外的大量无用数据。此外,虽然Geohash方法也取得了一定的效果,但当Geohash编码和HBase检索机制结合应用时,它的编码索引命中范围仍然比目标区域要大很多,而本文方法中格网编码与位置结合更为紧密,检索时的命中率更高,耗时也更少。
图7不同编码方式下检索时间对比
表2不同空间维情况下检索结果对比
2.3多维检索效能分析
为验证本文方法的正确性以及在多维条件检索时的效能,本文以“时空+目标”四维条件检索为例,在1000、2000、5000以及1亿行4种不同数据规模下,对本文方法(时空格网编码+目标编码)以及传统方法(无行键索引,遍历检索)开展实验,检索条件为:目标编号为6804,起止时间为2014年8月4日10:00:00—11:00:00,空间范围为以坐标(30.661285°,104.067273°)为原点,半径为500m的圆形区域。实验结果如图8所示。
图8不同数据规模下多维检索耗时对比
由图8结果可知,多维检索(时空+目标)的情况下本文方法的检索耗时远比传统方法要少。结合表3的实验结果,随着数据规模的增大,虽然两种方法耗时都随之增加,但从耗时比来看,本文方法优势始终存在且不断扩大,并当数据规模为1亿行时,耗时比达到了319.79倍。从检索数量以及命中率可以看出,这是由于传统方法采用遍历检索,检索命中率较低;而本文通过多维索引直接快速定位数据,大幅度缩小了检索范围,提升了检索效率。另外,由于传统方法采用遍历的方式,其结果数量可以作为参考标准,通过对比不同数据规模情况下本文方法与传统方法的检索结果数量发现,本文方法的查全率为100%,证明了本文方法的正确性。
表3实验结果对比3结束语
针对海量时空数据背景下,多维数据检索较慢的难题,结合HBase的索引机制,设计了“时空+”可定制多维数据索引结构,并针对时间维、空间维、数据规模的影响开展了对比分析实验。结果表明:
1)在海量数据背景下,本文方法不但能够准确地检索数据,并且与传统方法相比,能大幅度降低耗时。另外,随着数据规模的增大,优势会愈发明显。
2)索引结构上,时间维和空间维均发挥了重要作用,并且与现有的Geohash空间降维算法相比,本文方法与HBase相结合时,能够更加快速、精确地命中数据。
3)本文方法能够在时空检索的基础上满足多维检索需求,定制灵活且性能良好。
综上,本文设计的方法具有较为明显的优势,在保证准确性的前提下,不仅时间效率高,且能够适应海量数据的增长。然而,由于受索引结构以及检索机制的影响,本文方法在随机检索任意一个或多个维度时效能不高,后续将通过研究增加辅助索引的方式解决相关问题。
参考文献：
[1]王家耀,武芳,郭建忠,等.时空大数据面临的挑战与机遇[J].测绘科学,2017,42(7):1-7.
[2]王家耀.时空大数据及其在智慧城市中的应用[J].卫星应用,2017(3):10-17.
[3]高强,张凤荔,王瑞锦,等.轨迹大数据:数据处理关键技术研究综述[J].软件学报,2017,28(4):959-992.
[5]叶李.移动对象数据库查询及处理技术研究[D].成都:电子科技大学,2011.
[6]尹章才,李霖.基于快照-增量的时空索引机制研究[J].测绘学报,2005,34(3):257-261,282.
[9]龚俊,柯胜男,朱庆,等.一种集成R树､哈希表和B*树的高效轨迹数据索引方法[J].测绘学报,2015,44(5):570-577.
[15]房俊,李冬,郭会云,等.面向海量交通数据的HBase时空索引[J].计算机应用,2017,37(2):311-315.
[16]吕亮,施群山,蓝朝桢,等.基于轨道约束的空间目标球面格网索引及区域查询应用[J].计算机应用,2017,37(7):2095-2099.
赵英豪,吕亮,徐青,施群山,卢万杰.一种面向海量时空数据的多维检索策略[J].测绘科学,2020,45(06):199-204.
基金:国家自然科学基金项目(41701463,41371436);河南省科技攻关计划项目(172102210.
分享：
泛在测绘被定义为用户在任何地点、任何时间，认知环境与人产生关系时使用和构建地图的活动和能力[1]。泛在测绘服务于近乎实时定位的大众行业，时空位置信息是这类应用的数据基础，除了专业的测绘数据，一些非专业的包含空间位置的众包数据也逐步成为测绘行业应用的重要数据来源。
2023-10-30
近年来，随着无人机、大数据、人工智能等技术的发展，快速、高精度的空间大数据处理模式已被广泛应用。摄影测量作为空间大数据的重要采集方式自然存在大量社会需求，同时这对摄影测量人才的数量和技术也提出了更高的要求。基于此，高校对于摄影测量人才的培养也必须顺应社会需求发展，即在摄影测量学课程设计方面需要进行改革和创新。
2023-09-05
房产测量主要是利用测绘技术和方法，采集和表达房屋物权的有关信息，为房屋产权、产籍和物业管理、房地产开发利用、交易、征收税费及城镇规划建设提供数据和资料。随着我国经济不断发展，城镇居民住宅逐渐增多，对房产测量的精度与效率提出了更高的要求。本文针对目前房产测量的局限性，提出了利用三维激光扫描技术实现大面积房产测量平面图绘制的方法。
2023-08-30
为促进无人机航测技术在电网工程建设中的应用，分析了无人机摄影测量系统的组成、特点、应用范围与作业流程，介绍了其在电网工程建设中的应用，包括在线路规划与地形图测量、电网应急救灾、电力巡线、电力线上异物处理中的应用。但受技术因素的影响，无人机在空中运行过程中仍然存在姿态不稳定、飞行时间偏短、航拍面积较小等问题。
2022-04-08
现阶段民用基础地理信息数字成果可以通过转换、融合的方式，生产出满足军方使用的成果数据，但这种方法耗时长，成本高。从推进双方成果深度融合的角度出发，应从标准化的视角，建立标准化融合工作机制，构建军民通用的测绘地理信息标准体系，推动基础类标准的融合，尝试成果类标准的研制。推进军民基础地理信息数字成果及标准融合有利于统筹军民测绘力量。
2022-01-21
在智慧城市这一概念提出之后，三维GIS技术的应用越来越充分，也达到了更好的实践效果。三维GIS是当下和未来GIS技能发展趋势的主要方向，它使空间信息不再局限于二维平面内。文章从三维空间数据库模型、物联网、三维可视化、互联网＋GIS等方面对三维GIS技术及其在智慧城市中应用进行综合分析，为城市管理提供了新思路。
2021-12-25
作为国民经济和社会发展支柱型产业之一，矿业起到基础性的支撑作用。作为矿山开采的基础条件，测绘质量提升属于行业重点探究的一个课题。无人机属于现阶段一种新颖的数据采集载体，与传统人工方式相比，存在着工作质量高、效率高、操作简单、机动性高等相关特点[1]。同时，无人机测绘技术将地面的地物、地貌空间具体状况体现出来，能够满足大比例尺成图要求。
2021-12-16
促使智慧城市智能服务的领域不断延伸。智慧城市建设具有系统性和复杂性，其涵盖电力工程、交通工程、经济建设等多个方面[1]。因此，通过在智慧城市测绘中应用地理信息系统，构建信息联通平台，能够在很大程度上突破地理条件和环境因素的影响，为城市建设服务提供有效的数据支撑，使智能化服务更加符合社会发展的需求。
2021-12-15
土地资源调查管理是政府的主要工作内容之一，高效的土地调查与管理，有利于实现土地资源的合理分配和高效利用，缓解我国土地资源短缺的压力。遥感技术以宏观、综合、动态、快速、准确的优势为国土资源管理与调查提供了先进的探测与研究手段，通过遥感技术可以获取高质量可靠的土地信息，为相关部门后续的土地规划利用奠定基础，实现国家土地资源的信息化、智能化管理。
2021-12-15
随着信息化进程与城市规划设计速度的不断加快，我国的城市建设已经向着＂智慧城市＂的方向进行发展。＂智慧城市＂已经成为当前我国城市建设的目标之一，为了更好地实现这一目标，必须要合理利用当下相关信息化技术与设备，不断推进我国城市化发展进程。在对国土空间进行规划的过程中，利用先进的信息测绘技术以及定位系统，可不断提高国土空间规划的科学性与准确性。
2021-12-15
人气：2953
人气：2279
人气：2270
人气：2268
人气：2225
我要评论
期刊名称：测绘科学
期刊人气：5361
主管单位：国家测绘地理信息局
主办单位：中国测绘科学研究院
出版地方：北京
专业分类：科学
国际刊号：1009-2307
国内刊号：11-4415/P
邮发代号：2-945
创刊时间：1976年
发行周期：月刊
期刊开本：大16开
见刊时间：一年半以上
影响因子：0.713
影响因子：0.000
影响因子：0.000
影响因子：1.236
影响因子：0.000
科普杂志阅读、期刊信息查询、论文下载、文献查询、原创文章检测等多项服务。
服务热线
您的论文已提交，我们会尽快联系您，请耐心等待！
你的密码已发送到您的邮箱，请查看！
2020-06-17
252
上传者：管理员
