[P2P]位置情報を数値1つで表す手法「Z-ordering」

□はじめに
ＤＨＴやＳｋｉｐｇｒａｐｈなどの技術が注目されるとともに、位置情報をP2Pで扱いたいという要望がでてきている。だがＤＨＴやＳｋｉｐｇｒａｐｈは1次元の数値で各ノードが扱う情報範囲を扱うため、位置情報など多次元の情報を扱うのには、当初は向いてないと見られていた。しかしあるテクニックを使うとそれは一発で解消する。それがZ-orderingである。なお、このZ-orderingは位置情報を扱えるP2PミドルウェアPIAXでも採用されている。

□簡単な例
多次元を1次元で表すにはどうすればよいのだろうか？まずここで一例を挙げてみる。
例えば、2次元空間においてｘ＝｛１、２、～９９｝、ｙ＝｛１，２、～９９｝とする。これを1次元で表してみよう。一つの方法は4桁の数値で上2桁をｘ、下2桁をｙとして表示する方法である。

確かにこの方法は2次元情報を1次元の数値で表している。しかし、あるエリアの範囲内、あるいはエリアの近辺の情報だけ取得しようすると、その空間検索アルゴリズムが大変そうなのが直感的にわかるだろう。

□空間充填曲線
そこで考え出されたのが空間充填曲線だ。空間充填曲線とはある空間を曲線で埋め尽くしてしまうような曲線だ。そんなもの本当にあるの？と思ってしまうのだが実は色々と研究されている。その一つがヒルベルト曲線だ。実際のヒルベルト曲線の様子は以下のリンクを見て欲しい。
http://www1.linkclub.or.jp/~zhidao/zlab/computing/fractal.html#hilbert
2次元空間が1次元の曲線で埋まっている事がわかる。
ヒルベルト曲線を使うと空間検索も可能だ。とはいえ、ややアルゴリズム的に複雑なのでもっと単純な方法が求められていた。

□Z-ordering
そこで生まれたのが計算が楽でアルゴリズムも簡単なZ-orderingである。Z-orderingは文字の通り空間をＺのように埋め尽くし、一次元の数値で表してしまう技法だ。論より証拠、リンクの資料内の図を見てもらいたい。
空間アクセス法（pdf)

この方法は高速に空間検索が可能なため、一般的に位置情報を扱うのに使われる技法のひとつである。

なお、位置情報を扱う技法としてTreeを用いたR-Treeがあることも述べておこう。これも先ほどの「空間アクセス法」資料に説明がされている。

□位置情報以外にZ-orderingは役に立つか？

Z-orderingは多次元を一次元にするのに役立つ手法である。では位置情報以外で多次元を一次元にするのに便利なことはないのだろうか？ここで私は2つの例を考えてみました。

・意味情報検索：
単語の意味を多次元空間（意味空間）にマッピングすることが研究されている。Z-orderingで単語の意味空間を一次元数値にマッピングする。すると単語の意味が一次元で表示可能となる。
応用例として、雑誌の記事について一番意見の多かった単語と、その単語を意味空間上で表示した数値、雑誌内容を用いてデータベースを作る。すると、その雑誌記事に近い意見を持った雑誌記事を容易に検索する事が可能となる。

・調査情報の整理：
アンケートとしてＮ項目質問して、かつ1項目あたりＭ件の選択肢があると、Ｎ次元ベクトルでアンケート内容を示すことができる。このＮ次元ベクトルをZ-orderingで1次元化する。データベースにはZ-orderingで1次元化したアンケートの回答情報とアンケートをした対象品目、アンケート回答者等も入れておく。すると、アンケート回答で近い意見をした人の回答者情報や対象品目を抽出する事が可能と考えられる。

多次元の情報をうまく低次元にすることで、データベースの検索効率を上げたり、P2Pの検索に適用することが可能となるだろう。