多次元データ(位置情報、画像など)の検索用インデックスのメモ

多次元データ用のインデックスに使用されるテクニック(データ構造?)として例えば下記のものがある。

  • R-tree (MySQLなど)
  • 空間充填曲線
    • Z-order curve

Z-order curve

ワイドカラム系のKVS(HBaseなど)などでは特定カラムの値でソートして格納できる。他にもDynamoDBではインデックス(セカンダリインデックス)などの機能がある。
このとき 2次元 (or higher) の空間に含まれるデータを Z-order curve などの空間充填曲線に沿うようにして1次元のデータへとマッピングすれば、上記データストア上に多次元インデックスを実装できる(←日本語要修正..)。

Z-order curveの実装:

Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account log in.