ElasticSearch之geohash替代方案：基于morton码的地理位置检索与轨迹匹配应用

2023-10-28 19:41
文章标签 应用 elasticsearch 检索 轨迹 匹配 替代 方案 地理位置 geohash morton

本文主要是介绍ElasticSearch之geohash替代方案：基于morton码的地理位置检索与轨迹匹配应用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

地理位置检索服务在日常生活中随处可见，小到共享单车、高德地图，大到飞行航线轨迹。上述服务中很多相关功能都可以通过GeoHash来实现，Lucene/Solr中也有应用到GeoHash，通过GeoHash创建索引、查询索引以及距离的计算等等。

GeoHash编码

Lucene内部sandbox包支持地理位置检索，默认实现可以支持方形，圆形和多边形的地理位置检索。

GeoHash算法本质上是空间索引的一种方式。我们可以将整个地球设想为一个二维平面，将地球上所有区域展开平铺之后通过递归分解将该平面切分为32个模块。之后再将其中的模块再进行分块，随着范围不断缩小，位置精度也越来越高。每个分块都由一定的标识来表示该块。而地球上所有经纬度坐标都会通过GeoHash算法转变为一个唯一的base32标识，该标识对应上述分块的标识，一层一层的确定分块位置，最终便可通过标识找到具体的地理位置。

首先贴出base32编码表：

对于给定的一组经纬度数据（116.389550， 39.928167），使用二分法无限逼近。对纬度39.928167进行编码：

1）区间[-90,0),[0,90]，39.928167在右区间内，取1；

2）区间 [0,45),[45,90]，39.928167在左区间内，取0；

3）区间 [0,22.5),[22.5,45]，39.928167在右区间内，取1；

4）不断递归进行二分拆解，慢慢缩小范围（最多缩小13次）...

5）最终纬度编码为1 1 0 1 0 0 1 0 1 1 0 0 0 1 0；

对经度116.389550做上述操作，可得经度编码1 0 1 1 1 0 0 0 1 1 0 0 0 1 1。

得到经纬度的二进制位后需要对其进行合并。奇数位取纬度，偶数位取经度，每次取其二进制位的一位（不足为取0），最终合并成一个新的二进制串：

11100 11101 00100 01111 0000 01101

每5位为一个10进制数，换算过来为28、29、4、15，0，13。通过换算过来的5个十进制数便可对照上面的base32表得到该经纬度对应的encode标识：wx4g0e。将标识编码转换为经纬度的decode算法与之相反。

经过以上过程，便可将一长串经纬度数据简化为一段短小的url标识——wx4g0e。

在得到标识之后，便可以只通过标识在地图上寻找对应的具体位置了。首先现在已分好的板块中找到W。找到W块后，再将W块进行分块，从子块之中找到X块。随后继续将X块细分，从X块的子块中找到4块。以此类推...随着不断地细分，直至找到wx4g0e对应的子块。

在该子块对应的区域内，即一定的经纬度范围内，他们的标识相同。也就是说，每一个字符串标识，都代表了而某一矩形区域。在这个矩形区域内的所有点，都共享GeoHash字符串标识，这样既可以保护隐私，又容易做缓存。

GeoHash优势

GeoHash因为是字符串查询，本身是比较耗时的。但当其做了索引之后，其查询速度是快于普通查询的，尤其是当第二次命中时查询速度比普通查询二次命中会更快。原因也很简单：单列索引、单列命中显然是高于多列的。GeoHash查询出来的仅仅是某个范围内的数据，需要对返回的数据在进行距离运算，排序后最近的便是。其优化效率主要体现在范围查询上。

由上述分析可知，GeoHash是相当有用且高效的一个算法，这个算法通过无穷的细分，能确保将每一个小块的geohash值确保在一定的范围之内，这样就为灵活的周边查找和范围查找提供了可能。

GeoHash缺陷

GeoHash算法也存在一定的缺陷。由于GeoHash算法采用的是Peano空间填充曲线，虽然能够将将二维空间转换成一维曲线，但Peano空间填充曲线最大的缺点就是突变性，有些编码相邻但距离却相差很远，比如0111与1000，编码是相邻的，但距离相差很大。虽然geo确实尽可能的将位置相近的点hash到了一起，可是这并不是严格意义上的(实际上也并不可能，因为毕竟多一维坐标)，例如在图中的红点虽然和上方的白点离的很近，可是它们的geohash值一定有差别，因为他们所属子块并不同；虽然在视野上红点和黑点离的很远，但他们因为同属一个子块，事实上geohash值相同。很多时候我们对geohash的值进行简单的排序比较，结果貌似真的能够找出相近的点，并且似乎还是按照距离的远近排列的，可是实际上会有一些点被漏掉了。

Morton码替代

眼下有一替代方案——morton码（莫顿码）代替GeoHash。针对现有剖分模型的不足，有效避免了传统经纬度格网模型在高纬度地区的形状退化和正多面体格网模型的面片形状不规则问题。通过morton码，实现了面片编码与传统地理坐标之间的转换和邻接关系的计算，弥补了上述GeoHash算法中因地球不规则性和纬度变化带来的缺陷。

Morton码可以将多维数据转化为一维数据编码，根据一维编码位数可确定多维数据保留精度，是一种比较常用的压缩编码方法，尤其是作为哈希表的映射算法等，加速了树结构数据的存储和访问速度。

Morton编码也叫z-order code ，因为其编码顺序按照空间z序，编码结果展现为一种Z形的填充曲线。

 

lucene在实现地理位置检索上的缺点

由于morton码仅能用来表达一个方形的区域，而lucene在实现圆形，多边形地理位置检索的时候是先基于morton筛选出一个大致的范围，然后对筛选出来的每一条记录进行二次验证与剪切，以达到精确匹配的目的。

目前lucene的二次验证采用的是DocValues实现，DocValues字段是一个面向列存储的字段，DocValues是在Lucene4.0引入的新特性，属于正向索引。它存储文档编号到字段值正向关系的索引。

基于DocValues实现二次验证和剪切存在较多的随机IO，如果命中的记录条数很多，会导致整体地理位置检索性能非常的差。

改进方法

原先采用docvalues或正排数据进行地理位置（如圆形，多边形）的二次校验，也即原先进行地理位置（如圆形，多边形）的二次校验读取的数据分布在磁盘的不同位置，不连续。如下图所示：

更改为将相同的地理位置的数据存储存储在一起，通过构造连续数据，减少随机读取的次数：

 

 

 

使用方法

基本使用

1. 创建实例

能支持geo查询的数据类型必须为y_geopoint_idmp

create table geo_example(
id y_string_id,
geoname y_string_id,
geodata y_geopoint_idmp
);

2. 导入数据

(1) 数据样例

1) 每条数据一个点：

{"tablename":"geo_example","partition":"test","id":1,
"geoname":"102.72242222037083,28.88523027458959 ",
"geodata":"102.72242222037083,28.88523027458959 "}

2) 每条数据2个点，每个点之间以空格隔开，当然写成json数组也可以：

{"tablename":"geo_example","partition":"test","id":1,
"geoname":"102.72242222037083,28.88523027458959  103.72242222037083,29.88523027458959 ",
"geodata":"102.72242222037083,28.88523027458959  103.72242222037083,29.88523027458959 "}

(2) 导入测试数据

sh load.sh -t geo_example -p test1 -tp json -local -f /wyh/test.json

(3) 全表扫描

3. 筛选方法

(1) 圆形区域匹配

查询语句如下：

select count(*) from geo_example where partition like '%'  
and SYS_JSON_QUERY@{query_type:"geo",geo_type:"circle",field:"geodata",list:["99.71,29.38"],radius:1000}@SYS_JSON_QUERY limit 20;

查询结果如下图所示（查询半径不同，匹配到的结果数不同）：

(2) 方形区域匹配

查询语句如下：

select count(*) from geo_example where partition like '%'  
and SYS_JSON_QUERY@{query_type:"geo",geo_type:"box",field:"geodata",list:["99.71,29.38"],radius:10000}@SYS_JSON_QUERY limit 20;

查询结果如下图所示（查询半径不同，匹配到的结果数不同）：

(3) 多边形区域匹配

查询语句如下（至少4个点，且因多边形要求闭合，第一个与最后一个点必须相同）：

select count(*) from geo_example where partition like '%'  
and SYS_JSON_QUERY@{query_type:"geo",geo_type:"polygon",field:"geodata",list:["105.39,45.40","99.50,29.20","110.50,29.20","105.39,45.40"]}@SYS_JSON_QUERY limit 20;

查询结果如下图所示：

(4) Geohash网格汇聚

查询语句如下：

select geohash_s,count(*) as cnt from geo_example where partition like '%'  
and SYS_GEO_QUERY@{field:"geodata",minLon:"99.50",minLat:"29.20",maxLon:"110.50",maxLat:"45.40",precision:4}@SYS_GEO_QUERY 
group by geohash_s order by cnt desclimit 20;

查询结果如下图所示：

 

相似轨迹匹配

1. 匹配算法

Lsql的默认打分机制是根据TF/IDF算法，即词频算法。

  • TF：分词项在文档中出现的次数（term frequency）。

  • IDF：代表分词项在多少个文档中出现（inverse document frequency）。

但在进行轨迹匹配时需要按照匹配的条件个数排序，匹配个数多的排在前面。

2. 创建实例

create table geo_match(
id y_string_id,
geoname y_string_id,
geodata y_geopoint_idmp
);

3. 导入数据

测试数据如下所示（标红为几条轨迹数据的不同之处）：

{"tablename":"geo_match","partition":"test","id":1,
"geoname":"102.72242222037083,28.88523027458959 110.72242222037083,28.88523027458959 99.72242222037083,28.88523027458959 ",
"geodata@geo5000":"102.72242222037083,28.88523027458959 110.72242222037083,28.88523027458959 99.72242222037083,28.88523027458959 "}
{"tablename":"geo_match","partition":"test","id":2,
"geoname":"102.72242222037083,28.88523027458959 110.72242222037083,28.88523027458959 90.72242222037083,28.88523027458959 ",
"geodata@geo5000":"102.72242222037083,28.88523027458959 110.72242222037083,28.88523027458959 90.72242222037083,28.88523027458959 "}
{"tablename":"geo_match","partition":"test","id":3,
"geoname":"102.72242222037083,28.88523027458959 120.72242222037083,28.88523027458959 90.72242222037083,28.88523027458959 ",
"geodata@geo5000":"102.72242222037083,28.88523027458959 120.72242222037083,28.88523027458959 90.72242222037083,28.88523027458959 "}
{"tablename":"geo_match","partition":"test","id":4,
"geoname":"100.72242222037083,28.88523027458959 130.72242222037083,28.88523027458959 90.72242222037083,28.88523027458959 ",
"geodata@geo5000":"100.72242222037083,28.88523027458959 130.72242222037083,28.88523027458959 90.72242222037083,28.88523027458959 "}

./load.sh -t geo_match -p test -tp json  -local -f /wyh/testMatch.json

导入数据后全表查询结果如下：

select * from geo_match  where partition like '%' limit 10;

4. 轨迹匹配检索

(1) 描点

轨迹匹配，需要对导入的两个经纬度之间，进行描点，以体现出轨迹匹配，lsql默认在两个经纬度点之间从两头向中间最多描100个点。

注意：描完点后的经纬度的值，会很多，膨胀率较高，一般仅用于轨迹匹配，不要做其他用途。另外描点距离越近，精度越高，但膨胀率越高。

上面导入的经纬度数据是不能进行描点的。如果要进行描点，需要导入数据的时候在列名字上做特殊处理。

  • kafka导入 

原先

{
'table':'geo_match'
,'partition':'default'
,'id':'1'
,'geoname':'test'
,'geodata':'100.72242222037083,28.88523027458959 130.40751616748125,31.369586323194188 90.71391535438913,29.393961382032614'
}

按照5000米描点的写法

{
'table':'geo_match'
,'partition':'default'
,'id':'1'
,'geoname':'test'
,'geodata@geo5000':'100.72242222037083,28.88523027458959 130.40751616748125,31.369586323194188 90.71391535438913,29.393961382032614'
}
  • 离线导入

json写法与上述kafka导入类型，不再细述。

分隔符方式的导入以@分隔符为例

原先写法：

./load.sh -t geo_match -p default -tp txt -fl id,geoname,geodata -f /load /1.log -sp @

按照5000米描点写法：

./load.sh -t geo_match -p default -tp txt -fl id,geoname,geodata@geo5000 -f /load/1.log -sp 0x09

(2) 普通排序语法

  • radius为匹配半径，meters为描点距离，radius通常来说大于等于meters

  • percent:表示最小匹配的点数，小于该值的记录不会被检索出来
select * from geo_match where partition like '%' and  SYS_JSON_QUERY@{query_type:"geo",geo_type:"track",field:"geodata",list:["100.72242222037083,28.88523027458959","130.72242222037083,28.88523027458959","90.72242222037083,28.88523027458959"],radius:10000,meters:5000,percent:20}@SYS_JSON_QUERY limit 20;

查询结果如下图所示：

(3) 按匹配条件个数排序语法

select id, geoname,geodata, cl_score_y_double_d  from geo_match where partition like '%' and SYS_SCORE_QUERY@SYS_JSON_QUERY@{query_type:"geo",geo_type:"track",field:"geodata",list:["100.72242222037083,28.88523027458959","130.72242222037083,28.88523027458959","90.72242222037083,28.88523027458959"],radius:10000,meters:5000,percent:20}@SYS_JSON_QUERY 
@SYS_SCORE_QUERY
order by cl_score_y_double_d desclimit 20;

查询结果如下图所示：

记录匹配condition个数越多的得分越高，排名越靠前，会首先返回，而普通排序功能无此效果。

必备函数

CL_GEO_DISTANCE(tmp.geodata,6.1,8.3) as distance  //计算两点之间的距离
CL_GEO_UNHASH(tmp.geodata) //用于将morton值解析出经纬度
CL_GEO_HASH(lon,lat) //用于将经纬度数据解析成morton值

 

 

LSQL不仅在地理位置检索、多值列、多列联合索引上具有亮点，其检索和统计分析服务更能够满足万亿秒查，该方面的性能也是业内的佼佼者。即席查询、模糊检索、Facet统计、列簇存储、异构存储、主从集群、过载保护、权限管理... 只需要一套数据库就可以解决大数据行业内从业人员的无数痛点。现在登陆LSQL官网：www.lucene.xin，还可以免费试用喔~

 

关注录信数软官方公众号，录信团队欢迎优秀的你！

 

这篇关于ElasticSearch之geohash替代方案：基于morton码的地理位置检索与轨迹匹配应用的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/295515。

相关文章

基于MySQL Binlog的Elasticsearch数据同步实践

基于MySQL Binlog的Elasticsearch数据同步实践

一、为什么要做 随着马蜂窝的逐渐发展，我们的业务数据越来越多，单纯使用 MySQL 已经不能满足我们的数据查询需求，例如对于商品、订单等数据的多维度检索。 使用 Elasticsearch 存储业务数据可以很好的解决我们业务中的搜索需求。而数据进行异构存储后，随之而来的就是数据同步的问题。 二、现有方法及问题 对于数据同步，我们目前的解决方案是建立数据中间表。把需要检索的业务数据，统一放到一张M
阅读更多...
中文分词jieba库的使用与实景应用（一）

中文分词jieba库的使用与实景应用（一）

知识星球：https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义： 精确模式（默认模式）： 全模式： 搜索引擎模式： paddle 模式（基于深度学习的分词模式）： 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取
阅读更多...
水位雨量在线监测系统概述及应用介绍

水位雨量在线监测系统概述及应用介绍

在当今社会，随着科技的飞速发展，各种智能监测系统已成为保障公共安全、促进资源管理和环境保护的重要工具。其中，水位雨量在线监测系统作为自然灾害预警、水资源管理及水利工程运行的关键技术，其重要性不言而喻。 一、水位雨量在线监测系统的基本原理 水位雨量在线监测系统主要由数据采集单元、数据传输网络、数据处理中心及用户终端四大部分构成，形成了一个完整的闭环系统。 数据采集单元：这是系统的“眼睛”，
阅读更多...
无人叉车3d激光slam多房间建图定位异常处理方案-墙体画线地图切分方案

无人叉车3d激光slam多房间建图定位异常处理方案-墙体画线地图切分方案

墙体画线地图切分方案 针对问题：墙体两侧特征混淆误匹配，导致建图和定位偏差，表现为过门跳变、外月台走歪等 ·解决思路：预期的根治方案IGICP需要较长时间完成上线，先使用切分地图的工程化方案，即墙体两侧切分为不同地图，在某一侧只使用该侧地图进行定位 方案思路 切分原理：切分地图基于关键帧位置，而非点云。 理论基础：光照是直线的，一帧点云必定只能照射到墙的一侧，无法同时照到两侧实践考虑：关
阅读更多...
高效+灵活，万博智云全球发布AWS无代理跨云容灾方案！

高效+灵活，万博智云全球发布AWS无代理跨云容灾方案！

摘要 近日，万博智云推出了基于AWS的无代理跨云容灾解决方案，并与拉丁美洲，中东，亚洲的合作伙伴面向全球开展了联合发布。这一方案以AWS应用环境为基础，将HyperBDR平台的高效、灵活和成本效益优势与无代理功能相结合，为全球企业带来实现了更便捷、经济的数据保护。 一、全球联合发布 9月2日，万博智云CEO Michael Wong在线上平台发布AWS无代理跨云容灾解决方案的阐述视频，介绍了
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
hdu1394(线段树点更新的应用)

hdu1394(线段树点更新的应用)

题意：求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质，在0到n-1这些数字组成的乱序排列，将第一个数字A移到最后一位，得到的逆序数为res-a+(n-a-1) 知道上面的知识点后，可以用暴力来解 代码如下： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
zoj3820(树的直径的应用)

zoj3820(树的直径的应用)

题意：在一颗树上找两个点，使得所有点到选择与其更近的一个点的距离的最大值最小。 思路：如果是选择一个点的话，那么点就是直径的中点。现在考虑两个点的情况，先求树的直径，再把直径最中间的边去掉，再求剩下的两个子树中直径的中点。 代码如下： #include <stdio.h>#include <string.h>#include <algorithm>#include <map>#
阅读更多...
Android平台播放RTSP流的几种方案探究（VLC VS ExoPlayer VS SmartPlayer）

Android平台播放RTSP流的几种方案探究（VLC VS ExoPlayer VS SmartPlayer）

技术背景 好多开发者需要遴选Android平台RTSP直播播放器的时候，不知道如何选的好，本文针对常用的方案，做个大概的说明： 1. 使用VLC for Android VLC Media Player（VLC多媒体播放器），最初命名为VideoLAN客户端，是VideoLAN品牌产品，是VideoLAN计划的多媒体播放器。它支持众多音频与视频解码器及文件格式，并支持DVD影音光盘，VCD影
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2