地理位置索引整理进化


空间映射&编码

  1. 墨卡托模型: http://cdn.hujiulong.com/geohey/blog/mercator/play.html
  2. Geohash 是一种地理编码,由 Gustavo Niemeyer 发明的。它是一种分级的数据结构,把空间划分为网格。Geohash 属于空间填充曲线中的 Z 阶曲线(Z-order curve)的实际应用。
  3. s2 参考文档 https://github.com/halfrost/Halfrost-Field/blob/master/contents/Go/gospatialsearch.md

空间索引的方法

Lucene的方法:

  1. 2D空间下的索引:
    1. geo_point :前缀索引 可以解决附近点和区域内点的搜索
    2. geo_sharp : 形状索引的实现。 Tessellation Decomposition + Block K Dimensional Trees (Bkd),三角拆分+blockKDtree
  2. 3D空间下的索引

    1. XYShape for Spatial…in Lucene 8.2+ Tessellating & Indexing Virtual Worlds

  3. lucene geo索引原理参考文档

    1. https://www.slideshare.net/elasticsearch/geospatial-advancements-in-elasticsearch
    2. https://portal.opengeospatial.org/files/?artifact_id=90337

索引涉及的数据结构和发展

  • 空间数据库中最基本的查询
    1. 正交范围查询(range query)
    2. 窗口查询(window query): 在二维坐标数据中,窗口查询是一个坐标对齐矩形,查询目标是数据库中的落在矩形内所有点。
      • 支持窗口查询的的多维点索引结构有: k-d B-tree hB-tree Bkd-tree R-tree

kdtree 的发展:

  1. K-d tree 1975 Jon Louis Bentley 发明(https://en.wikipedia.org/wiki/K-d_tree)

    1. k-d树是每个节点都为k维点的二叉树。所有非叶子节点可以视作用一个超平面把空间分割成两个半空间。节点左边的子树代表在超平面左边的点,节点右边的子树代表在超平面右边的点。选择超平面的方法如下:每个节点都与k维中垂直于超平面的那一维有关。因此,如果选择按照x轴划分,所有x值小于指定值的节点都会出现在左子树,所有x值大于指定值的节点都会出现在右子树。这样,超平面可以用该x值来确定,其法线为x轴的单位向量。

    2. 基本结构&构建:

      • 有很多种方法可以选择轴垂直分割面( axis-aligned splitting planes ),所以有很多种创建k-d树的方法。 最典型的方法如下:
        1. 随着树的深度轮流选择轴当作分割面。(例如:在三维空间中根节点是 x 轴垂直分割面,其子节点皆为 y 轴垂直分割面,其孙节点皆为 z 轴垂直分割面,其曾孙节点则皆为 x 轴垂直分割面,依此类推。)
        2. 选择的轴的具体座标的中位数作为作为分割面,同时该点放入子树。
      • 这个方法产生一个平衡的k-d树每个叶节点的高度都十分接近。但是平衡的树不一定所有场景都是最佳的
    3. 支持:最近邻查询和范围查询
    4. kdtree的主要问题:
      • 因为k-d树是多维排序的,做到平衡比较复杂。不能使用树旋转技术来平衡它们,因为这可能会破坏不变量
      • 平衡K-D树的几种算法:divided k-d tree, pseudo k-d tree, k-d B-tree, hB-tree and Bkd-tree
    5. 制约和限制:
      • 维度灾难:在高维空间中,k-d树叶并不能做很高效的* 最邻近搜索。一般的准则是:在k维情况下,数据点数目N应当远远大于2^k时,k-d树的最邻近搜索才可以很好的发挥其作用
  2. K-D-B-tree (k-dimensional B-tree) k-d-b-tree的目标是提高平衡k-d树的搜索效率,同时提高b-tree面向块的存储以优化外部内存访问

    • J. T. Robinson. The K-D-B-tree: A search structure for large multidimensional dynamic indexes. In Proc. SIGMOD Intl. Conf. on Management of Data, pages 10–18, 1981
    • https://en.wikipedia.org/wiki/K-D-B-tree
    • 原文: http://www.csee.usf.edu/~tuy/Literature/KDB-SIGMOD81.pdf
    • 也有简称kdtree的

    • 与k-d树类似,k-d-b树组织k维空间中的点,对于范围搜索和多维数据库查询等任务非常有用。k-d-b树通过比较单个域中的元素将空间划分为两个子空间。以二维b树(二维k-d-b树)为例,空间的细分方式与k-d树相同:仅使用其中一个域或轴中的一个点,在这种情况下,所有其他值都小于或大于当前值,并分别落在拆分平面的左侧和右侧。 与k-d树不同,每个半空间不是自己的节点。相反,与b-树一样,k-d-b-树中的节点存储为页,树存储指向根页的指针。

    • kdbtree基本结构
      todo: https://en.wikipedia.org/wiki/K-D-B-tree

  3. Bkd-tree 是 kd-tree 的扩展 2003发明

    • 参考文档:https://users.cs.duke.edu/~pankaj/publications/papers/bkd-sstd.pdf

  4. hB-tree

    1. http://www.cs.bu.edu/fac/gkollios/cs591/hb-tree.pdf

空间数据分割树

  • R树 R*树 R+树 X树 M树 线段树 可持久化线段树 希尔伯特R树 优先R树

  • R-tree 1984 Antonin Guttman 发明 (https://en.wikipedia.org/wiki/R-tree https://zh.wikipedia.org/wiki/R%E6%A0%91) 在空间索引应用上非常典型也非常成功。最典型的应用就是:附近两公里的餐厅这样的查询

  • R树也是平衡树(所以所有叶子节点都在同一深度)。它把数据按(内存)页存储,是为磁盘存储设计的(跟数据库的做法相同)。每一页可以存储不超过一个上限的条目,这个上限一般用M表示。R树会在除根节点以外的节点上维持数据条目不小于最小条目数

Elastic search中空间索引和lucene映射历史

1
2
3
4
5
6
7
8
9
10
11
12
13
14
    ? Lucene 8.2+      XYShape for Spatial... Tessellating & Indexing Virtual Worlds
Elasticsearch 7.0 bundles Lucene 8
2019326日 - Elasticsearch 6.7.0, based on Lucene 7.7.0.
2019-2-4              6.6.0   Integrate Lucene's LatLonShape (BKD Backed GeoShapes) as default geo_shape
Elasticsearch 6.5.0, based on Lucene 7.5.0.
Elasticsearch 6.4.0, based on Lucene 7.4.0.
2018年6月13日 Elasticsearch 6.3.0, based on Lucene 7.3.0.
Elasticsearch 6.2.0, based on Lucene 7.2.1.
                                     6.6+      "triangle" encoding(Bkd-tree)
                                     pre 6.6   terms/postings encoding
Elasticsearch 5.4.1, based on Lucene 6.5.1.
Elasticsearch 5.4.0, based on Lucene 6.5.0.
Elasticsearch 5.3.3, based on Lucene 6.4.2.
Elasticsearch 2.4.0, based on Lucene 5.5.2.

elastic search 7.4 Geo 相关支持情况

  • Geo query(https://www.elastic.co/guide/en/elasticsearch/reference/current/geo-queries.html)
  • ElasticSearch支持两种类型的地理数据:支持纬度/经度对的地理点域和支持点、线、圆、多边形、多多边形等的地理形状域。
  • 支持的查询类型:

    1. 地理框查询(geoboundingbox)
      • 查找具有落在指定矩形中的地理点的文档。(支持经纬度查询数组、字符串、或geohash编码构建的矩形区域进行查询)
    2. 地理距离查询(geo_distance)
      • 查找地理点位于中心点指定距离内的文档。
    3. 地理多边形查询(geo_polygon)
      • 查找指定多边形内具有地理点的文档。
    4. 地理图形查询(geo_shape)
      • 查找具有与指定的地理形状相交、包含或不相交的地理形状的文档。
      • 能够过滤带有geo_shap类型字段的索引
      • 查询支持直接给的一个形状也支持在另外一个索引里面定义的形状。
      • 空间关系运算符:
        1. intersects-(默认)返回其geo_shape字段与查询几何体相交的所有文档。
        2. DISJOINT-返回其geo_shape字段与查询几何图形没有任何共同点的所有文档。
        3. within-返回其geo_shape字段位于查询几何体中的所有文档。
        4. contains-返回其geo_shape字段包含查询几何图形的所有文档。注意:这只支持使用递归前缀树策略[6.6]
  • Shap query(https://www.elastic.co/guide/en/elasticsearch/reference/current/query-dsl-shape-query.html)

    1. 查询带有shap类型的索引
    2. 和geo_shape类型查询很像,shap query 用 GeoJSON 或 Well Known Text (WKT)表征形状。
    3. 支持的空间关系运算:
      1. intersects-(默认)返回其geo_shape字段与查询几何体相交的所有文档。
      2. DISJOINT-返回其geo_shape字段与查询几何图形没有任何共同点的所有文档。
      3. within-返回其geo_shape字段位于查询几何体中的所有文档。

es lbs 查询实例

  • 场景:查询当前点在可服务区域里面的所有doc并按照直线距离排序。 poi_zone 代表可服务区域 , poi_point 代表服务提供方所在位置。
  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    DELETE /shapes


    PUT /shapes
    {
        "mappings": {
            "properties": {
                "poi_zone": {
                    "type": "geo_shape"
                },
                "poi_point": {
                    "type": "geo_point"
                }
            }
        }
    }


    PUT /shapes/_doc/deu
    {
        "poi_zone": {
            "type": "polygon",
            "coordinates" : [
              [[116.402508,39.947163], [116.414653,39.94697], [116.414869,39.940083], [116.40276,39.939972],[116.402508,39.947163]]
            ]
        },
        "poi_point":{
          "lon":116.408401,
          "lat":39.943734
        }

    }

    PUT /shapes/_doc/deu2
    {
        "poi_zone": {
            "type": "polygon",
            "coordinates" : [
              [[116.409443,39.947136], [116.420043,39.946997], [116.420043,39.945615], [116.409443,39.945587],[116.409443,39.947136]]
            ]
        },
        "poi_point":{
          "lon":116.414096,
          "lat":39.946513
        }
    }

    GET /shapes/_search

    GET /shapes/_search
    {
        "query":{
            "bool": {
                "must": {
                    "match_all": {}
                },
                "filter": {
                    "geo_shape": {
                        "poi_zone":  {
                            "relation": "intersects",
                            "shape": {
                              "coordinates": [116.409766,39.946389],
                              "type": "point"
                            }
                        }
                    }

                }
            }
        },
        "sort": [{
                "_geo_distance": {
                    "poi_point": {
                        "lon": 116.413503,
                        "lat": 39.946776
                    },
                    "unit": "km",
                    "order": "asc"
                }
            }]
    }

发表评论

邮箱地址不会被公开。 必填项已用*标注