ES地理空间查询利器:Geo-Shape

网友投稿 3079 2022-05-29

地理位置检索广泛于各行各业,在智慧城市,城市规划,物流,房地产选址,新零售,公共安全,交通等各个方面都能够发挥重大作用,应用包含坐标查询(点查多边形)、范围查找(多边形查点)、范围统计分析(基于多边形的统计分析)等,例如查询任意指定区域内的酒店,学校,餐饮店等,统计不同电子围栏、不同时间段的派单数,优化车辆调度等;

ES地理空间查询利器:Geo-Shape

elasticsearch 是一个分布式、可扩展的全文搜索引擎,底层依赖开源的Lucence库,ES是面向文档型数据库,内部使用倒排索引Inverted Index,而非MySQL内部的B+树,可以基于时间构建索引,历史索引可以定期删除,分布式多副本索引架构。

地理位置功能仅仅是 Elasticsearch 的冰山一角,Elasticsearch 的妙处在于,它让你可以把地理位置、全文搜索、结构化搜索和分析结合到一起。Elasticsearch 提供了两种表示地理位置的方式:用纬度-经度表示的坐标点使用 geo_point 字段类型,以GeoJSON格式定义的复杂地理形状,使用 geo_shape 字段类型。

优点:支持多种复杂查询,扩展性很好,例如在千万级别的数据量下,基于点的空间检索,性能也有比较好的表现;

性能分析

从Elasticsearch 7.0开始,ES引入了地理空间图形字段类型的新默认索引技术,它再一次为地理空间几何图形提供了比传统前缀树索引方法更大的性能改进。从精度上来看,在7.0之后的版本创建的geo_shape字段可以达到1cm的精度,从速度上来看,与6.x geo shapes相比,它提供了更快的搜索速度和数倍的索引速度。

优化点:

1、存储方式:三角形切割方法替代传统的网格化编码方式,在存储容量和精度上有了飞跃的提升

2、索引优化:利用R-树索引方式检索

在BKD树之前,利用倒排索引的方式进行空间索引,需要将空间几何体转化为可表示的位置信息,可通过栅格化的技术来实现编码,geohash是一套网格化的编码方式,经过编码,可以将经纬度对应的点,表示为一个网格,网格的大小,取决于geohash的精度。通常,geohash使用32个字符进行编码。业界也有使用geo base 36的编码,即36个字符来表示的。下图为将同一区域进行不同精度的网格化划分,可见精度越高,会造成存储的网格信息量成倍增加,造成精度和性能成为约束的关系。

为了有效地存储和显示高分辨率的几何图形,大多数计算机图形和游戏引擎将这些几何图形分解为基本体,如三角形。三角形在很大程度上是有效的,因为“每个对象都可以分割为三角形,但三角形不能分割为除三角形之外的任何其他对象”。

使用三角形细分,可以显著减少项的数量,并保持几何体的原始精度,但几何体现在表示为三角形的集合,而不是其原始顶点形式。通过这种改变,形状索引和搜索问题被简化为将三角形组织到BKD数据结构中的过程,从而使搜索变得高效。要实现这一目标,还需要两项额外的改进。

首先,BKD数据结构需要一种优化组织三角形几何体的方法。这是通过修改BKD实现的,称为选择性索引。选择性索引的目标是允许N维字段指定前k个维度(索引维度),以驱动BKD树的构建,剩余的d维度(数据维度)作为存储的辅助数据,供叶节点使用。对于二维三角形集合,选择前四个维度作为索引维度,代表三角形的边界框。通过这样做,一般的BKD树被转换成R树,其中树的内部节点是边界框的集合,叶子包含重建原始三角形所需的数据。

第二个改进是对单个镶嵌三角形进行紧凑的维度编码,以便它们可以有效地存储在树的叶子上,而不需要不必要的大量空间。这是通过使用三个数据维度(总共七个维度)来完成的,这使得编码能够从前四个边界框维度重建三角形的三个二维顶点。

在上图中,“code”维度表示哪些顶点与原始边界框共享,以及如何从最小/最大边界框索引维度和y、x数据维度重建剩余顶点。例如,在第一行中,代码维度“0”表示三角形与边界框索引维度共享(Ymin,Xmin)和(Ymax,Xmax)顶点。第三个三角形顶点可以直接用Y和X数据维重建。通过这种编码,可以使用总共七个维度有效地索引细分的三角形,使得BKD数据结构被组织为一个R树,该R树是空间搜索的最佳选择,同时能够从少量辅助数据重建三角形的原始顶点。

R-树采用一种叫做MBR(Minimal Bounding Rectangle)最小外界矩形,其中的R就是指的Rectangle矩形的意思,从叶子结点开始用矩形(Rectangle)将空间框起来,结点越往上,框住的空间就越大,以此对空间进行分割。R-树是处理空间数据的B+树的改进,它像B+树一样,是一个高度平衡的数据结构,现已成为空间数据库索引中应用最广泛的算法之一。

R-树是B+树在高维空间的扩展,是一颗平衡树,每个R-树的叶子结点包含了多个指向不同数据的指针,这些数据可以是存放在硬盘中的,也可以是存在内存中。根据R-树的这种数据结构,当我们需要进行一个高维空间查询时,我们只需要遍历少数几个叶子结点所包含的指针,查看这些指针指向的数据是否满足要求即可。这种方式使我们不必遍历所有数据即可获得答案,效率显著提高。

可见,基于Elasticsearch可以快速高效的进行地理位置空间检索,同时支持空间检索和全文搜索、结构化搜索和分析结合;

geo-shape查询

Elasticsearch支持两种类型的地理数据:支持经纬度对的geo_point字段和支持点、线、圆、多边形等的geo_shape字段。

本文用geo_shape举例来进行空间查询:在地图上画一个矩形,搜索区域中的店铺。

首先,插入一家新华书店的位置数据:

PUT /example {    "mappings": {        "properties": {            "location": {                "type": "geo_shape"            }        }    } } POST /example/_doc?refresh {    "name": "新华书店",    "location": {        "type": "point",        "coordinates": [13.400544, 52.530286]    }

然后,输入查询语句,进行区域内的店铺搜索:

GET /example/_search {    "query":{        "bool": {             "must": {                "match_all": {}             },            "filter": {                 "geo_shape": {                     "location": {                         "shape": {                             "type": "envelope",                             "coordinates" : [[13.0, 53.0], [14.0, 52.0]]                         },                        "relation": "within"                     }                }            }        }    } }

结果:

{  "took" : 71,  "timed_out" : false,  "_shards" : {    "total" : 1,    "successful" : 1,    "skipped" : 0,    "failed" : 0  },  "hits" : {    "total" : {      "value" : 1,      "relation" : "eq"    },    "max_score" : 1.0,    "hits" : [      {        "_index" : "example",        "_type" : "_doc",        "_id" : "Mav003QB1KmvPzr042GF",        "_score" : 1.0,        "_source" : {          "name" : "新华书店",          "location" : {            "type" : "point",            "coordinates" : [              13.400544,              52.530286            ]          }        }      }    ]  } }

华为云搜索服务是一个基于开源Elasticsearch且完全托管的在线分布式搜索服务,为用户提供结构化、非结构化文本、时间,数字,地理位置、声音、图片等的多条件检索、统计、报表。

华为云CSS首页链接: https://www.huaweicloud.com/product/es.html

EI企业智能 云搜索服务 CSS AI平台

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:经典面试题:Python 为什么 这么慢?
下一篇:一文读懂云原生2.0时代的DevOps体系框架
相关文章