GeoHash、Google S2和Uber H33种全球地理格网编码方法对比分析

地理格网编码是高效管理、分析和查询海量地理空间位置数据并提供信息服务中非常重要且基础的工作。GeoHash、Google S2和Uber H3是目前商业应用上3种较常用的地理格网编码方法,该文从地理编码的基本概念及其演变过程出发,介绍当前地理编码所涉及的地理格网剖分和编码运算方法,然后从算法概况、编码方式、编码层级及其对应空间范围等方面对3种方法进行阐释,最后从正多面体选择、剖分单元、填充曲线、编码层级、邻域查询与邻域距离类型和算法应用优缺点等方面进行对比分析,以深入挖掘3种方法的应用价值和前景,可为基于地理位置大数据的研究与应用提供借鉴。

基于GeoHash编码的候选路段检索方法

地图匹配是生活中常用的位置服务和轨迹挖掘的基础,其首要环节是获取轨迹点的候选路段。在候选路段检索时,传统路网网格划分方法存在不相关路段冗余或者忽略正确进行候选路段的问题,导致地图匹配效率较低、匹配质量下降。针对这些问题,提出了一种基于GeoHash编码的候选路段检索方法。采用GeoHash编码将城市道路路网数据进行分块并编码,建立路网的网格索引,结合设置误差圆快速获取候选路段集,并通过地图匹配验证效果。结果表明,当全球导航卫星系统(GNSS)轨迹点的误差圆半径为200 m时,匹配精度最高,匹配正确率高于95%。该方法有效提高了候选路段检索的效率,并在保证匹配质量的同时,提升了地图匹配整体效率。

基于区块链的车联网群智感知位置隐私保护方法

针对车联网群智感知位置隐私泄露和用户参与任务公平性的问题,提出了一种基于区块链的车联网群智感知位置隐私保护方法(location privacy protection method based on blockchain and crowdsensing, LPPMBC)。将分布式的区块链引入车联网群智感知位置隐私保护方法中,消除第三方服务平台对参与用户数据的控制;通过保序加密和Geohash编码相结合,为参与工人提供多级别的位置隐私保护,确保参与工人位置隐私的保密性;通过Haversine公式进行感知位置验证,防止工人通过非感知区域数据获得非法奖励,保障感知数据的质量。仿真结果表明,LPPMBC能够更好地权衡感知数据质量与工人隐私保护关系,保障用户参与任务的公平性,提高用户参与任务的积极性。

基于Geohash的面数据区域查询

鉴于Geohash编码的全球唯一性、多层次递归性和一维的特性,以及Geohash目前通常只用于邻近点数据的空间查询而鲜用于面数据空间查询的现状,提出了一种基于Geohash的面数据区域查询方案,描述了对面数据和查询区域的处理方法。主要思路是将面数据关联到若干Geohash单元网格,并在数据库中保存网格的Geohash编码与面数据的对应关系,查询时将查询区域根据规则对应到最多4个Geohash编码,再根据编码查询与区域相交的面数据。通过对比试验可知,在数据量较大且查询区域较小的情况下,基于Geohash编码的面数据查询效率较基于经纬度和R-树的查询效率高,在海量空间数据检索上具有一定应用价值。

Geohash编码抗k近邻攻击的脆弱性分析

Geohash编码作为一种降维技术目前已应用于空间数据库和空间数据引擎中,但其安全性还有待进一步研究。文章关注Geohash编码存在的安全漏洞,从理论上分析了此种降维技术产生推理通道的原因,并提出一种基于k近邻查询的加密Geohash字段重构算法,通过观察大量k近邻查询响应中的明文信息进行统计推断并重构出加密Geohash的原始值。对加密兴趣点数据库进行重构实验,实验表明,观察到的查询响应数量越多,重构值的精确度越高。在Geohash编码精度为30 bit的情况下,当观察到100000到3000000次查询响应时,重构值与原始值平均误差为0.074%到0.015%。该实验揭示了Geohash编码在抵抗k近邻查询推理攻击方面的脆弱性及形成机理,将促进相关地理信息系统行业的安全应用与研究。

基于 GeoHash 算法的煤场车辆运输管理系统设计

在我国煤炭工业与国际接轨的趋势下,煤场车辆运输管理系统的重要性日渐凸显。为了提高煤场车辆运输管理的有效性,保障煤场车辆运输管理工作的有序开展,采用GeoHash算法对煤场车辆运输管理系统进行优化设计。本课题对GeoHash算法作用机制等进行了深入探究,并对系统性能进行个体测试与比较分析。结果显示,基于GeoHash算法的煤场车辆运输管理系统具有较高的工作效率,能快速对运输管理任务作出响应;在不同煤场及工作范围内,该系统用时均显著低于基于其他算法的煤场车辆运输管理系统。表明本课题所设计的系统具有优越的工作性能,可为煤场车辆运输管理工作提供助力。

基于GeoHash和B+树的环卫车调度算法

随着社会的快速发展,垃圾存量急剧上升,环卫车容易出现混装混运、调度困难等问题。为了解决相关问题,论文基于GeoHash编码和B+树设计了一种新型的环卫车调度算法。该算法能适用于传统的垃圾清运模式下的环卫车调度和垃圾分类下的垃圾清运模式的环卫车调度,通过利用GeoHash编码对环卫车的位置进行编码,随即使用B+树对垃圾存量、路径等相关数据进行筛选,选择合适的环卫车进行调度。该算法能对环卫车搜寻精度进行设置且能对环卫车位置信息进行保护。

一种面向相似查询的轨迹索引方法

轨迹数据具有重要的应用价值,轨迹索引技术得到广泛的研究与关注。传统索引方法存在节点重叠、缺乏动态划分空间能力和丢失大量原始信息等问题,为此提出一种面向相似查询的轨迹索引方法GeoSAX。该方法将原始轨迹分成若干等长子段并采用基于Geohash的空间编码;对编码后的整条轨迹设计了基于HBase存储的索引架构;实现相似轨迹查询。GeoSAX不仅节点间没有重叠,还能依据数据量的大小对空间动态划分,同时保留指定精度的轨迹信息。在真实的航运和出租车数据集上进行的对比实验表明,与传统方法相比GeoSAX具有更好的轨迹查询性能。

一种轻量级高效的位置服务隐私保护模型

针对基于位置服务中用户位置信息和查询信息隐私易被泄露的安全威胁问题,基于Geohash地理信息一维编码、利用Mem Cached快照缓存和分布式服务器集群技术、加密和认证技术,构建了一个位置服务隐私保护模型,并加以仿真实现。经过仿真实验和数据测量,该模型达到了k-匿名效果,且避免了用户稀疏问题和连续查询带来的易被结合用户背景知识进行关联攻击的问题,也具有较好的性能表现。

基于HBase的电磁侦察大数据存储设计

随着电磁侦察数据的积累,使用传统关系型数据库存储海量历史数据逐渐表现出不易扩展、查询缓慢、查询方式不贴近业务需求等问题,需要一种新的满足电磁侦察大数据特点的分布式数据存储方案。针对电磁侦察数据的特点和典型应用的查询需求,探讨了电磁侦察大数据的存储方案,并提出了基于分布式列式数据库(HBase)的电磁侦察大数据存储设计方法。利用HBase分布式、可伸缩、可扩展和动态列的特性,贴近业务查询需求详细设计了按目标名称、闭合空间区域和时间范围三种存储表结构,为实现海量电磁侦察大数据的高效存储和检索提供了新思路,并通过实际应用验证了该方案的有效性。

大规模轨迹数据的Geohash编码组织及高效范围查询

面向成熟的关系-对象型空间数据库,利用Geohash编码的唯一性、一维性和递归性等特征,提出了一种基于Geohash编码的大规模轨迹数据组织方法及范围查询技术。该方法结合Geohash编码和B+树索引,设计了适应不同尺度范围查询的大规模轨迹数据的关系组织模式,并给出了相应的两阶段查询处理算法,同时提出了一种Z合并优化,以进一步提高范围查询的处理效率。实验结果表明,此方法适合于组织管理与查询分析大规模的轨迹数据,其范围查询性能高于内置的R树索引。

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

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

基于GPS轨迹数据的城市交叉路口识别

【目的】针对交通方式混合模式下城市居民移动产生的GPS时空轨迹数据,实现城市道路交叉路口的自动识别。【方法】将交叉路口识别转化为一个有监督的分类学习问题。利用GeoHash算法对原始轨迹和轨迹活动区域进行编码和分格;将编码轨迹与活动区域编码矩阵映射成二值化融合矩阵,构建交叉路口特征集合;最后利用带有滑动窗口的K近邻分类算法,实现城市交通的交叉路口识别。【结果】在真实轨迹数据集GeoLife上的对比实验表明,经过GeoHash编码转换,数据集规模平均缩减率达到原有轨迹点数量的39%,降低了计算的时间复杂度;同时,识别精度优于传统的基于转向角度的交叉路口识别方法,当误差距离为50米时,综合评价指数的F1-Measure达到0.82。【局限】需要在更多城市真实轨迹数据集上进一步检验该方法的有效性。【结论】本文所提方法不受交通模式变化而产生的GPS轨迹采样频率影响,能解决混合交通模式数据集上的城市交叉路口自动识别问题,具有较强的通用性。