Elasticsearch における geoshape, geopoint の実装

Published: 2023/2/19


Lucene はある段階から、 BKD-Tree によって数値系のデータをインデックスするようになった。 内部実装的には 8 次元までの数値データをストアできるようになっている。 ただ、実際の Elasticsearch のアプリケーション上では、緯度・経度を用いた geopoint や geoshape 系の、任意形状の交差判定処理がアプリケーションニーズの方が高く、それを実現するために一工夫がなされている。

任意形状(shape) のインデックス登録

具体的には、 Elasticsearch は任意の形状が与えられたとき、それを三角形のメッシュに分割し、その三角形の集合体として形状を捉える。 それを BKD-Tree であるインデックスに載せる際には、最初の4次元をその三角形の Bounding Box として扱い、残りの3次元で当三角形のデータを符号化する。 Bounding Box がインデックスに載っているので、任意形状との交差処理を判定したければ、 その形状の bounding box が共通しているところのみをインデックス上探索していけば良く、これにより Bounding Box を利用する系のクエリが実現される。

三角形の符号化については、上記 Elastic 社の記事に詳細が記述されているが、ざっくりと説明すると、

  • 二次元上の三角形とその Minimum Bounding Box を考えると、3点のうち2点は Bounding Box に載っている。
  • Bounding Box への載り方は 8 パターンに分類することができ、その各パターンにおける自由パラメータは X 方向のパラメータと Y 方向のパラメータそれぞれに一つずつ。
  • Bounding Box で4次元、自由パラメータで2次元、パターンの符号化で1次元、計7次元によって三角形を符号化する。
  • 元々が浮動小数(float)である場合には、 32bit 整数へ量子化してデータ投入する
    • インデックスサイズを小さくするため

帰結

二次元図形(geo系)のクエリにて任意図形を表すために符号化する、という選択を行ったがために、逆にただの BKD-Tree を直利用するようなクエリは Elasticsearch 上では開放されていない。 例えば、6次元データのある点からの nearest neighbors であれば、 Lucene 的には実現できそうな気がするが、実際のリアルアプリケーション上でのニーズは形状(shape)との交差判定がほとんどであったために、 API として提供するのは現在の geoshape や geopoint の検索機能に落ち着き、上記の符号化によるインデックス投入が可能なのは2次元 only であるため、今現在の Elasticsearch は shape や point として 2次元のみをサポートする、ということになっている模様。


Tags: elasticsearchlucene

関連記事