DEIM Forum 2013 F10-1

一般化された Z-Order を用いた多次元索引の提案
西村 祥治†

宮崎昇幸††† 日本電気株式会社 〒 211–8666 神奈川県川崎市中原区下沼部 1753†† 京都大学大学院 〒 606–8501 京都市左京区吉田本町
E-mail: †s-nishimura@bk.jp.nec.com, ††tmiyazaki@db.soc.i.kyoto-u.ac.jp
あらまし

近年，Web サイトのログデータ，センサ情報など複数の属性を持った大量の多次元データを解析し，より有用な情報を抽出することが試みられている．この増え続けるデータを格納する先として，従来からあるリ
レーショナルデータベースに代わり，容易にシステムをスケール可能なキーバリューストア（KVS）が注目されている．しかし，多次元データ解析をする際，効率的な多次元検索や集約演算が提供されることが望ましいが，

KVS は単純なデータ操作しか提供していない．本論文では，KVS に適用可能な一般化された Z-Order を用いた多次元索引を提案する．本手法により索引の設計空間を拡張し，問い合わせパターンに応じて最適化可能なスケー
ラブル多次元データストアを実現する．
キーワード 多次元インデックス, キーバリューストア, スケーラブル, 多次元データベース, 空間充填曲線, Z-Order

1. は じ め に

順序型 KVS であれば，開始，終了となる key を指定してその間にあるレコードセットを取得する Scan 操作があるが，

近年，Web サイトのログデータ，センサ情報など複数の

これは，key という単一属性に対する範囲検索を提供するだ属性を持った大量の多次元データを解析し，より有用な情報けである．このため，多次元データ解析に欠かせない多次元を抽出することが試みられている．このような増え続ける

範囲検索を実現するためには工夫が必要である．

データを格納する先として，容易にシステムをスケール可

このようなデータストア上で，多次元データを表現する方

能なキーバリューストア (Key-Value Store, KVS) が注目さ法として，空間充填曲線による多次元空間から一次元空間へれている．このようなデータストアの例としては，HBase,の写像を用いる方法がある．空間充填曲線とは，多次元空間

Cassandra といったオープンソースプロジェクトを挙げるこ

上のすべての点をもれなく一筆書きでなぞりつくす曲線で，とができる．KVS は，key と value の組みとしてレコードを例として Z-order やヒルベルト曲線が知られている．この方表現し，key 通じてレコードにアクセスするデータストアで

法では，インデックスを張りたい属性集合の多次元空間を考ある．KVS は，key によってデータを分割することができる

え，それを空間充填曲線によりその空間内にあるすべての点，ため，容易にシステムをスケール（拡大）させることが可能

すなわち各属性の属性値の組を一列化し，その並びでデータである．KVS は，データの格納方法により，ハッシュ型とストアに格納する．

key 順序型に分けられる．前者は，ハッシュ関数により key

多次元空間を一次元空間に写像するため，多次元空間上でを格納する場所を決めるものである．後者は，key を辞書式

は近い２点が写像先の一次元空間では遠くに配置されたり，順でレコードを整列して格納するものである．つまり，key

逆に，遠い２点が近くに配置されたりする．このため，従来

順序型 KVS は，key の範囲でデータを分割して格納する．

研究では，多次元範囲検索を写像された空間上で実現する

データ解析のためには，ある属性がある範囲内にあるレ

際，いかに効率的に必要な Scan 区間を見つけ，いかに無駄

コードの取得（範囲検索）や集約（クロス集計）をするが必な Scan を減らすかに主眼があった．このため，多くの研究要である．複数の属性を持っている多次元データを対象としでは，問題を単純にするため，すべての属性は同じ定義域をているため，複数の属性の範囲を指定した多次元範囲検索や，もち，検索の際，各属性の範囲はほぼ同じという仮定が明示

集約演算を効率的に実行することができる必要がある．とこ的に，あるいは，暗黙的に置かれている．

ろが，KVS は単純なレコードアクセス操作しか提供しない．

しかし，現実のデータは，属性ごとに定義域の幅は異なり，

すなわち，key と value のペアを引数にした Put 操作と key

かつ，検索されるときに指定される範囲の幅も異なる．そこを引数に value を取得する Get 操作が基本操作である．key

で、本論文では、このような状況で検索効率がよいインデックスキーを設計，生成する方法について提案する．ただし、本論文では、データ解析をする際に指定される範囲は，ある程度事前に推測できることがあるという仮定をおく。これは，例えば，位置情報の場合，１ｋｍ四方や５ｋｍ四方，時刻の場合，日ごと，週ごと，月ごと，商品情報の場合，商品カテ
ゴリごとのように，集約したい単位が，設計時にある程度推測可能と考えられるからである．このとき，検索範囲の幅は，(a) Z-order(b) ヒルベルト曲線(c) 複合インデックス

図 1 空間充填曲線

毎日の午前 0 時 00 分から翌午前 0 時 00 分までの 24 時間というように，範囲の幅だけでなく始点と終点も固定する場合

ンデックスに用いられてきた．Z-order を用いたインデック（離散化可能な場合）だけではなく，今から直近の 24 時間のス手法としては，UB-tree [2], zkd-B-tree [3], MD-HBase [4]ように始点と終点が固定されていないが，24 時間という範囲など多くある．Z-order は１ビットずつ順番に交互に混ぜ合の幅だけが事前に分かっている場合も対象とする．

わせて構成することから，インデックス対象の各属性値は，本論文の貢献は以下のとおりである．

等しいビット幅を持つことを暗に仮定する．しかし，現実の•データでは，これは強い仮定である．そこで，UB-Tree の関

インデックスキーの設計と多次元範囲検索の効率を明らかにするコストモデルを提案•

コストモデルに基づいて，多次元範囲検索の効率を達成するインデックスキーの設計方針を提案•

Z-order を一般化することでインデックスキーの設計

空間を拡張し，上記の設計方針を実現する多次元インデック
スキーを提案•

評価実験により，提案手法の有効性を報告

連研究では，ビット幅が長い順に属性の優先度付けをし，先頭ビットから順に交互に混ぜ合わせ，ある属性のビット列がすべて混ぜ合わされたならその属性からビットを取ることをスキップする方法を提案している [5]．すなわち，ビット列を左詰めで混ぜ合わせる方法を提案している．
次によく使われる空間充填曲線としては，ヒルベルト曲線が挙げられる．ヒルベルト曲線は，図 1(b) で示すような曲

本論文の構成は以下のとおりである．2 章では，関連研究線である．Z-order に比べて複雑であるが，ヒルベルト曲線について紹介する．3 章では，本論文で扱う多次元範囲検索

上で一つ隣のデータ点は，元の多次元空間においても必ずの効率に関する問題について説明する．4 章では，インデッ（どこかの次元において）一つ隣のデータ点であることから，

クスキーによる多次元範囲検索のコストモデルを提案し，そZ-order よりも高く元の空間の近傍性を保存する．この性質れに基づいて，インデックスキーの設計方針を提案する．5から，範囲検索性能の効率が高まることが期待される．この章では，評価実験をし，提案手法が有効であることを示す．6

ことから，Lawder らは，ヒルベルト曲線を用いた手法を提章では，全体と今後の課題についてまとめる．

案している [6]．ヒルベルト曲線は図 1(b) から明らかに各次元に対して対称的な構造をしているため，インデックス対象

2. 関 連 研 究の属性の定義域が異なる場合，工夫が必要である．単純には，多次元空間を空間充填曲線により一次元空間に写像し，多0 でパディングして属性のビット列長を一致させる方法があ

次元データを一次元データとして扱う手法は従来よりよく研る．Hamilton らは，ゼロパディングによるインデックスキー

究されてきた．例えば，文献 [1] は，空間充填曲線をもちい長を増加を抑えるために，ビット長が短い属性の次元の上位

たインデックス手法を網羅的に紹介している．これらのうち，ビットをスキップさせるように構成するヒルベルト曲線を提代表的な空間充填曲線に関して，関連研究を紹介する．

案している [7]．これは，本質的には，属性値を右詰めしなが最も使われる空間充填曲線として，Z-order がある．Z-orderらインデックスキーを構成する方法といえる．

を用いた手法は，インデックス対象の属性値の組をビット列

最後に，リレーショナルデータベースでよく使われる複合の組と見たとき，それぞれのビット列を１ビットずつ交互に

インデックスも図 1(c) のような空間充填曲線により多次元

混ぜ合わせること（bit-interleaving）でインデックスキーを

空間を一次元空間へ写像した方法とみることができる．すな

構成する．すなわち，属性値の組として，４ビットのビット

わち，４ビットの属性値の組 (abcd, WXYZ) が与えられたと列の組 (abcd, WXYZ) が与えられたとき，aWbXcYdZ のようき，abcdWXYZ のように，それぞれのビット列を連結するこに構成する．これは，つまり図 1(a) で示すような曲線としと (bit-concatenation) でインデックスキーを構成する方法て表現される．Z-order の特徴としては，任意の個数のビッである．複合インデックスは，単に各属性のビット列を連結

ト列の組からインデックスキーとなるビット列を容易に構成するだけなので，属性ごとのビット長が異なっていても特にすることができる点と，一次元空間に写像された後も，元の構成上の問題は起きない．また，複合インデックスは，どの空間における多次元データ点同士の近傍性がいくぶんか保順番で属性を並べるかで，検索性能が大きく変わることが知存されている点である．このため，位置情報といった空間イられている．一般的には，カーディナリティが小さい属性，—2—と呼ぶ．次に，ヒットページ内を走査する．ヒットページがカバーしている領域は必ずしも検索領域とは重ならない領域も含まれる．そこで，ヒットページ内のレコードを検査し，条件を満たすレコードだけを結果として返す．
多次元範囲検索の実行時間は，ヒットページ数に依存する．
なぜなら，ページ内を走査する回数は，ヒットページ数分必要だからである．図 2 で示すように，ヒットページ内のすべてのレコードが検索範囲内に存在するとは限らない．このた
図 2 範囲検索の例

め，ヒットページ内にあるレコードのヒット率を上げて，できる限り少ないヒットページ数で検索範囲をカバーできるこ

必ず指定される属性を優先する（インデックスキーにおいて上位ビット側に配置する）とよい．しかし，上記の空間充填曲線とくらべ，元の空間の近傍性が保存されにくいため，多次元範囲検索の効率は一般的によくない．
以上のように，属性の定義域が異なる場合のインデックス
キーの構成方法についての研究はいくつかある．しかし，検索時に属性の範囲指定が異なる場合にこれらを考慮して検索効率を向上させるようなインデックスキーの構成に言及した研究は，筆者が知る限りない．

とが望ましい．
すべての範囲検索のパターンに対して，最小のヒットペー
ジ数を達成するようなレコード配置は不可能である．そこで，本論文では，インデックスキーを設計する時，各属性に対す
る支配的な検索範囲の幅がわかっていると仮定する．そして，
そのような範囲検索のパターンに対してヒットページ数がな
るべく少なくなるようなインデックスキーを設計する問題と設定する．
この仮定は，例えば，時間軸だと日，週，月という単位，
地理情報だと 100m 四方といったマス目の単位など，ある程

3. 問 題 設 定
本章では，まず，空間充填曲線を用いた多次元データベー
ス上での多次元範囲検索について概説する．そして，多次元
範囲検索を効率化には，ヒットページ内のレコードヒット率度推測できることが多いのではないかという観測に基づく．
ただし，各属性の支配的な検索範囲の幅がわかっていることだけを仮定し，その範囲の起点や終点は任意とする．

4. 提 案 手 法を上げることの重要性を示す．最後に，本論文でどのような仮定のもと，このヒット率の改善をするかを説明する．

3. 1 空間充填曲線と多次元範囲検索
多次元空間を空間充填曲線上に写像した多次元データベースにおいて，多次元範囲検索はおおよそ次のように実現される．
各レコードは，インデックスを張りたい属性値の組から空間充填曲線上に対応する一次元の値をもとめ，これをインデックスキーとしてデータベース上に保持される．この時，インデックスキーの値の順に従ってレコードが整列される．
レコード数が多い場合，適当なインデックスキーの値でレ
コードを分割し，ページとしてまとめて保持する．図 2 で具体例を示す．この例では２つの属性に対してインデックスを張った例であり，この図の各マス目が２つの属性値の組を表す．図中の矢印線が２次元空間を一次元に写像する空間充填曲線であり，この例では Z-order を表している．太枠で囲まれた領域が，ページがカバーする範囲である．
このように格納されたレコードに対して，多次元範囲検索を実行する．図 2 では，点線の枠で囲った部分が検索領域である．多次元範囲検索は，大きく以下の２つのステップからなる．まず，検索範囲と重なるページの抽出を抽出する．この例では，影が付けられた太枠の領域が検索範囲と重なるページである．これらのページのことを，ここではヒットページ

本章では，インデックスキーの設計と範囲検索の効率の関係をヒットページ数の観点でコストモデルを構築する．そして，このコストモデルを元に，インデックスキーの設計方針について説明する．次に，この方針を実現するため，Z-orderを一般化し，それをインデックスキーとする手法を提案する．そして，この一般化された Z-order を効率的に生成するScatter-OR 法を提案する．
4. 1 インデックスキーの設計と範囲検索のコスト
範囲検索のコストモデルを構築するにあたり，本論文では，
空間充填曲線として解析が容易な Z-order を対象とする．まず，解析に必要な変数を定義する．次に，解析が容易な特殊な例でコストモデルを議論する．最後に，これを一般化し，インデックスキーの設計方針を得る．
属性 i のビット長を xi とし，その属性の支配的な検索範
囲の幅のビット長を wi とする．するとインデックスキーの∑ビット長 l は i xi であり，範囲検索のカーディナリティは∏ wi∑より，そのビット長 w は， i wi である．
i2
議論を単純にするため，データの分布は一様とし，各属性の検索範囲の起点，終点はビットアラインされているとする．
つまり，属性 i に関する検索範囲は，上位の xi − wi ビットは同じで，下位ビットが，0 が wi 個並んだ値から，1 が wi個並んだ値までが指定されたものとする．この空間充填曲—3—

線上における検索範囲の最大値と最小値の差のビット数は，るとは，インデックスキーの下位 w ビットに，属性 A の下

高々k ビットであるとする．いいかえれば，空間充填曲線上

位 wA ビット，属性 B の下位 wB ビットを配置するようにイで，2k の範囲の幅に，範囲検索でヒットするレコードが含ま

ンデックスキーを設計するのがよい．

れているとする．検索範囲のカーディナリティのビット長が以下では，各属性の検索範囲がビットアラインされていな

w より，k >= w である．
今，データの分布は一様と考えているので，ページはイン

い場合，データの分布が一般の場合について議論する．いずデックスキーの全範囲をページ数で等分した区間をカバーしいという結論が得られる．

れの場合も上記の方針でインデックスキーを設計した方がよていると考える．この時，各ページがカバーする区間のビッa ) 各属性の検索範囲がビットアラインされていない場合

ト長を c とする．もし，c >= k であれば，範囲検索にヒットす

属性 i の検索範囲がビットアラインされていない場合，そるレコードはすべて一つのページに収まる．次に，c < k のの範囲内にあるレコードのビット列のパターンを観察する．

場合について考える．今，インデックスキーにおいて，下位

ビットアラインされていないため，下位の wi ビットから上から j ビット以内に含まれている属性 i のビットの数を vi (j)位ビットへ桁上がりが発生する (図 3)．上位の xi − wi ビッとする．すると，１つのページに含まれる範囲検索にヒット∏するレコード数は高々 i min(wi , vi (c)) である．いいかえれ∏
ば，少なくとも i max(wi − vi (c), 0) のページに範囲検索

トに着目すると，桁上がりで伝播するビット長に関わらず，にヒットするレコードが配置される．

そのプレフィックスとなるビットのパターンは，高々2 種類しかない．
以上より，属性 i の検索

以上より，データの分布が一様で，検索範囲の起点，終点

範囲だけがビットアラインの値がビットアラインされている場合，ページがカバーする

されていない場合を考える

区間のビット長が c の時，範囲検索の際にヒットページ数は，∏
i max(wi − vi (c), 0) となる．つまり，レコード数が増えてと，ヒットページ数は，最ページ分割が増えるほど c が小さくなり，その結果，ヒット

性がビットアラインされてページ数が増える．ヒットページ数が増えるのは，c が k よいる場合に比べて高々2 倍

り小さくなった時であるため，k ができる限り小さくなるよで抑えられる．そして，属

うにインデックスキーを設計したほうがよい．今，k >=wという関係があるため，k = w となるようインデックスキーを性の数が d である場合，す設計するのがよい．

アラインされていない場合

悪の場合でも，すべての属

べての属性の検索がビットげて議論する．二つの 6 ビットの属性 A,B があり，それぞのヒットページ数は，最悪∏
2d i max(wi −vi (c), 0) でれ [a0 00000, a0 11111]，[b0 b1 b2 b3 00, b0 b1 b2 b3 11] の範囲を検抑えられる．

では，k = w とはどういう場合であるかを具体例を挙䝥䝸䝣䜱䝑䜽䝇
ඹ㏻㒊

図 3ϬϬϬϬϬϬ
ϬϬϬϬϬϭ
00 00 00 00 00ϬϬϬϬϭϬ
0000000000000000000000000000000
00 00 00 00 00 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000ϬϬϬϬϭϭ
000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000
00 00 00 00 00ϬϬϬϭϬϬ
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
000 000 000 000 000ϬϬϬϭϬϭ
000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000
000 000 000 000 000ϬϬϬϭϭϬ
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000ϬϬϬϭϭϭ
000000000000000000
000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
000000000000000000
000 000 000 000 000ϬϬϭϬϬϬ
000 000 000 000 000 000 000 000 000 000 000 000 000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00ϬϬϭϬϬϭ
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
000000000000000000
000 000 000 000 000ϬϬϭϬϭϬ
000 000 000 000 000 000 000 000 000 000 000 000 000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00ϬϬϭϬϭϭ
ϬϬϭϭϬϬ᳨⣴⠊ᅖᖜ䠙ϴ

ビットアラインされていない検索範囲とプレフィッ
クスのパターン

索する．この時，wA = 5，wB = 2 であり，w = 7 であさらに詳細に解析するため，この桁上がりで影響を受ける

る．次に，この場合での k を求める．Z-order 上での検索範

ビット長の期待値を見積る．1 ビット分だけ桁上がりする場

囲の最小値と最大値は，各属性の起点同士，終点同士を bit

合は全体の 1/2，2 ビット分の場合は 1/4 と桁上がりのビッinterleaving することで求まる．この時，a0 b0 0b1 0b2 0b3 0000，

ト長が長くなるほど指数関数的にそれが起こる事象は稀にな∑xi −wiる．つまり，その期待値は，Ecarry,i = j=1
j/2j <=2である．この期待値は，ビットアラインされていて桁上がりがa0 b0 1b1 1b2 1b3 1111 であり，これらの値の上位 2 ビットが共通であるから k = 10 である．ページがカバーする区間のビット長が c >
= k = 10 である時，１つのページ内で検索範囲内のレコードがすべて含まれる．次に，c = w = 7 の場合を起きない場合 (j = 0) も含んでいる．以上より，ヒットペー∏
ジ数の期待値は， i max(wi + 2 − vi (c), 0) である．この場考える．例として，[a0 b0 0b1 00000000, a0 b0 0b1 1111111] の区

合でも，wi （および桁上がり伝播のビット長の期待値分）を間をカバーしているページを考える．このヒットページ内に下位ビット側に寄せるように設計した方がよい．

は，属性 B の値が b0 b1 b2 b3 00 のような属性 B の検索範囲内b ) データの分布が一般の場合のレコードだけでなく，例えば b0 b1 b2 b3 00 のような b2 と b3

上記では，データの分布が一様の場合を議論したので，各がビット反転した範囲外のレコードも含みうる．つまり，こページがカバーするくか n 区間のビット長を c と固定した．

のようなレコードがヒットページ内のレコードヒット率を下データの分布が一般の場合，この c がページごとに変化す

げる要因になる．言い換えれば，レコードヒット率を下げるることを意味する．一般にデータが密に集まっている区間を要因となる，属性 B の b2 や b3 のビット位置にあるものをイカバーするページの c は小さく，疎である区間をカバーする

ンデックスキーの下位 7 ビットの位置に配置しないようにすページの c は大きい．個々のページに関して，c の大きさは変べきである．w = wA + wB なので，k = w となるようにすわるが，上記と同じ議論が成り立つ．従って，データの分布—4—ŝƚŽŶĐĂƚĞŶĂƚŝŶŐ
΀ǆϬ͕ǆϭ͕ǆϮ͕ǇϬ͕Ǉϭ͕ǇϮ΁

4. 3 一般化された Z-order の性質ŝƚ/ŶƚĞƌůĞĂǀŝŶŐ
΀ǆϬ͕ǇϬ͕ǆϭ͕ǆϮ͕Ǉϭ͕ǇϮ΁

΀ǆϬ͕ǇϬ͕ǆϭ͕Ǉϭ͕ǆϮ͕ǇϮ΁

Z-order を用いた多次元データストアは，Z-order がもつ性質を利用して効率的に，検索範囲と重なる範囲をカバーすᒓᛶyඃඛ

るページを見つける．一般化された Z-order は Z-order より自由度が高いが，上記の目的に有用な性質を保存している．
΀ǇϬ͕Ǉϭ͕ǇϮ͕ǆϬ͕ǆϭ͕ǆϮ΁

΀ǇϬ͕ǆϬ͕Ǉϭ͕ǇϮ͕ǆϭ͕ǆϮ΁

このため，既存の Z-order を用いた多次元データストアに一΀ǇϬ͕ǆϬ͕Ǉϭ͕ǆϭ͕ǇϮ͕ǆϮ΁

般化された Z-order を比較的軽微な修正で導入可能であると考える．以下の節では代表的な性質を挙げる．

ᒓᛶzඃඛ

4. 3. 1 最小値と最大値
Z-order を用いた多次元データストアで，候補のページを
図 4 一般化された Z-order

絞り込む際，まず，検索範囲内にあるレコードが，Z-order 上のどの範囲内にあるかを調べることである．Z-order の場合，に関わらず同様の方針でインデックスキーを設計すればよい．

4. 2 一般化された Z-order

せることで，Z-order 上での区間の最小値/最大値を求める．

前節で，各属性に関して，支配的な検索範囲の幅に相当
する下位ビットをインデックスキー上で，できる限り下位側に寄せた方がよいことを示した．この方針を実現するため，Z-order を一般化し，インデックスキーの設計空間を拡張する．

一般化された Z-order の場合も，同様のアルゴリズムで，検索範囲内にあるレコードが存在しうる一般化された Z-order上の範囲を算出することができる．

4. 3. 2 2 つの矩形領域の交差領域の最小値と最大値
さらに走査範囲を絞り込むには，検索範囲とページのカ

従来の Z-order を用いたインデックスキー生成手法は，１ビットずつ交互にビット列を混ぜ合わせることで，生成していた．このビット列の混ぜ合わせのルールに自由度をもたせ，以下の条件を満たすように生成される空間充填曲線を一般化された Z-order と定義する．

バー範囲が交差する範囲を見つけることが有用である．その基本となる操作は，2 つの矩形領域が交差する領域が，空間充填曲線上でどの範囲にあたるかを見つけることである．
２つの矩形領域 A，B があり，それぞれ属性 i の始点と終点を，[sAi , eAi ]，[sBi , eBi ] とする．Z-order の場合，Z-order［定義 1］（一般化された Z-order） 以下の条件を満たすように，ビット列を混ぜ合わせて生成して得られる空間充填曲線の集合を一般化された Z-order と呼ぶ．

上におけるこの交差領域の最小値，最大値は，それぞれ，各属性について max(sAi , sBi )，min(eAi , eBi ) となる値のビッ
ト列を交互に混ぜ合わせることで得られた．一般化された（ 1 ） 各属性のビット列の並び順は，写像先のビット列においても入れ替えしない．
（ 2 ） 属性ごとのビットの混ぜ合わせ順は任意

属性ごとの範囲の最小値/最大値のビット列同士を混ぜ合わ2

具体例として，２つの４ビットの属性の組 (abcd, WXYZ)があったとすると，この属性の組により生成されうる一般化された Z-order の例としては，abcdWXYZ, abcWdXYZ,

abWXcdYZ, aWbXcYdZ, WaXbYdZ, WXYZabcd などを挙げることができる．いくつかの一般化された Z-order が描く曲線の例を図 4 に示す．一般化された Z-order の定義より，bit-interleaving も bit-concatenation も一般化された Z-order の特別な例であるし，属性ごとのビット長が異なる際にビット列を右詰め，左詰めすることも一般化された Z-order の特別な例であることは明らかである．すなわち，この一般化によりインデックスキーの設計空間を大幅に広げることができる
ことがわかる．
また，一般化された Z-order を用いたインデックスキーは，各属性の各ビットを，インデックスキー上のどの位置にビットを配置するかを制御することを可能にする．すなわち，前節で示したような，最適化したい範囲検索にあわせたイン
デックスキー設計を可能とする空間充填曲線群の一つである

Z-order の場合も，同様にして得ることができる．
結局のところ，4. 3. 1 節と本節の最小値，最大値に関する性質は，属性間でのビットの混ぜ合わせ順に依存しているのではなく，各属性におけるビットの並びが保存されていることに依っているからだと考えられる．

4. 3. 3 プレフィックスと空間上の位置
Z-order が描く曲線を注意深く観察すると，Z という形がフラクタルな入れ子構造になって描かれていることがわかる．
そして，この入れ子構造の階層と Z-order のビットパターンには強い関連がある．２次元空間の Z-order の場合，図 5 で示すように，インデックスキーを２ビットずつ区切った時，何番目の区切りかが，Z-order が描かれた空間において何階層目かを表し，その区切りの値が，その階層における位置を表している．すなわち，インデックスキーのプレフィックスと Z-order が描く曲線がつくる領域が一対一に対応している．
例えば，文献 [8] は，インデックスキーを上位から下位ビッ
ト方向にビットパターンを走査することで，効率的に検索範
囲と重なる範囲をカバーするページを見つけるアルゴリズムを提案している．また，文献 [4] は，インデックスキーのプ
リフィックスのパターンを空間分割に利用している．

といえる．

—5—

΀Ϭ͕Ύ͕Ύ͕Ύ͕Ύ͕Ύ΁΀Ϭ͕Ϭ͕Ϭ͕Ύ͕Ύ͕Ύ΁΀Ϭ͕Ϭ͕Ύ͕Ύ͕Ύ͕Ύ΁

がある位置に，対象のビット列の最上位ビットの値を，その΀Ϭ͕Ϭ͕Ϭ͕Ϭ͕Ύ͕Ύ΁

次に最左の 1 ビットがある位置に 2 番目の最上位ビットの値を置くことを意味する．

Scatter-OR 法では，インデックスキーを構成する属性ごとに，scatter マスクを用意する．このビットマスクの組がイ

図 5 Z-order のプレフィックスと空間上の位置関係

ンデックスキーの定義となる．つまり，各属性の各ビットが([y0,x0,y1,x1,y2,x2] の場合)

インデックスキーのビット列上においてどの位置に配置した΀Ϭ͕Ύ͕Ύ͕Ύ͕Ύ͕Ύ΁΀Ϭ͕Ϭ͕Ύ͕Ύ͕Ύ͕Ύ΁΀Ϭ͕Ϭ͕Ϭ͕Ύ͕Ύ͕Ύ΁΀Ϭ͕Ϭ͕Ϭ͕Ϭ͕Ύ͕Ύ΁

いかを与えることで，インデックスキー定義を与える．

Scatter-OR 法では，まず，インデックスキー定義として与えられた scatter マスクを，対応する属性に対して scatter 演
算を適用して，各属性のビット列がインデックスキーのビッ
図 6 一般化された Z-order のプレフィックスと空間上の位置関係

ト幅に散らされたビット列を得る．次に，これらのビット列に対して OR 演算で 1 つのビット列に集約する．こうして得([y0,x0,y1,y2,x1,x2] の場合)られたビット列がインデックスキーである．
ᒓᛶϭ

ᒓᛶE

Ϭ ϭ ϭ Ϭϭ ϭ ϭ Ϭ^ĐĂƚƚĞƌ

scatter 演算はよく使われるビット演算であることから，効率的なアルゴリズムが知られていたり，ハードウェア命令と^ĐĂƚƚĞƌ

^ĐĂƚƚĞƌ䝬䝇䜽 ϭ

ϭ

ϭ

ϭ

ϭ

ϭ

ϭ

ϭ

Ϭ

ϭ

ϭ

Ϭ

ϭ

ϭ

ϭ

Ϭ

して提供されていたりする．例えば，文献 [9] では，基本ビット演算を用いて，ビット幅 n に対して O(log n) ステップで

Haswell マイクロアーキテクチャのプロセッサでは scatter 演

KZ䜲䞁䝕䝑䜽䝇䜻䞊 Ϭϭ ϭ

実行できるアルゴリズムを紹介している．また，Intel(R) の

ϭ ϭ

ϭ Ϭ

Ϭ

算（PDEP 命令）をサポートすることが予定されている [10]．
また，属性ごとの scatter 演算，OR 演算による集約は命令レ

図 7 Scatter-OR 法

ベルでの並列性があるので，CPU のメニーコア化や SIMD
命令化による高速化も期待できる．

一般化された Z-order においても，Z-order と同様にそのプレフィックスと空間上の位置に強い関連がある (図 6)．すな
わち，インデックスキーの各ビットが，どの属性のどのビット由来であるかの情報があれば，そのプレフィックスと空間上の位置を一対一に対応付けることが可能である．上記のヒットページ探索手法も空間分割手法も，本質的に，このプレフィックスと空間上の位置の対応関係を利用しているので，これらの手法を一般化された Z-order 向けに拡張可能である．

4. 4 Scatter-OR 法
レコードにアクセスする操作をする際には，インデックス
キーが必要となるため，インデックスキー生成にコストがあまりかからないことが望ましい．この節では，効率的にイン

4. 5 Scatter-OR 法の計算量
Scatter-OR 法の計算量を解析する．属性の数を d，属性の平均ビット長を m，インデックスキーのビット長 n とし，このとき，n = dm である．そして，scatter 演算や OR 演算
は，N ビット幅で実行する命令が用意されているものとし，その計算量をそれぞれ O(1) とする．

scatter 演算は，インデックスキーのビット長 n を N ビッ
トごとに分割して実行する必要があるので，O(n/N ) である．
これを属性の数だけ適用するため，scatter 演算フェーズの計算量は O(dn/N ) である．
一 方 ，OR 演 算 は ，2 つ の ビット 列 の OR を と る の にO(n/N ) かかる．そして，すべての属性の scatter 結果を

デックスキーが生成可能な手法として，Scatter-OR 法を提インデックスキーへ集約するのに d − 1 回適用が必要である．

案する．

このため，OR 演算フェーズの計算量は O((d − 1)n/N ) で

Scatter-OR 法は，その名前のとおり，scatter 演算と OR
演算（論理和演算）を実行することでインデックスキーを生成する方法である．図 7 にその概略を示す．

scatter 演算とは，ビット演算の一種で，与えられた制御
ビットマスク（以下，scatter マスク）に従って，与えられたビット列の各ビットを散らす（scatter）操作である．scatter
マスクは，操作対象のビット列の各ビットを，結果のビット
列のどこに配置するかを，ビットを立てることで表すものである．すなわち，scatter マスクにおいて，最左の 1 ビットある．
以 上 よ り，Scatter-OR 法 の 計 算 量 は ，O(dn/N ) =O(d2 m/N ) である．インデックスキーのビット長より，属性の数の方が計算量の影響が大きいといえる．

4. 6 インデックスキー定義の検証
一般化された Z-order では，Z-order よりインデックスキー
定義の自由度があるため，ユーザがインデックスキー定義をする際にミスが入り込む余地が大きくなる．このため，与えられたインデックスキー定義が妥当であることが，チェッ—6—クしやすいことが重要である．本提案手法は，インデックス
キー定義が満たすべき条件は，比較的簡単にチェックするこ

表1

インデックスキーの種類とヒットページ数の見積と実際（検索範囲のビットアラインなし）
見積ヒットページ数

実ヒットページ数

index A20

1

index B

21

3

index C26

55とが可能である．

a ) scatter マスクのビット長
scatter マスクのビット長は，インデックスキーのビット長に一致する必要がある．インデックスキーのビット長は，イ
ンデックスキーを構成する各属性のビット長の和である．こ表 2 インデックスキーの種類とヒットページ数のことから，単純な和と比較で検証できる．

（検索範囲のビットアラインあり）

b ) scatter マスクの数

見積ヒットページ数

実ヒットページ数

scatter マスクは，属性ごとに関連付けて提供されるべきindex A

22

1

ものであるため，scatter マスクの数は，インデックスキーを

index B26

10

index C

212

88

構成する属性の数と一致する必要がある．これも簡単な比較で検証できる．

c ) scatter マスクで立っているビットの数数を評価した．表 1,2 にコスト計算の結果に基づくヒット

ある属性に関連付けられた scatter マスクは，その属性のページ数と実際のページ数をまとめる．インデックスキーがすべてのビットが，インデックスキー上においてどの位置に

A,B,C となるに従って，各属性の検索範囲の幅分のビットあるか示すものである．このことから，scatter マスクで立っがインデックスキーの上位ビット側に配置されやすくなるたているビットの数は，その属性のビット長と一致する必要がめ，ヒットページが増加する傾向にある．表 1 を見ると，検ある．これは，scatter マスクに対してビットカウントした結索範囲がビットアラインされている場合は，見積もったヒッ

果と，その属性のビット長を比較すれば検証できる．

トページ数とほぼ同じヒットページを得られることがわかる．

d ) scatter マスクで立っているビットの網羅性と排他性

一方，表 2 の検索範囲がビットアラインされていない場合は，

インデックスキーを生成した結果，各属性の各ビットがイ多めに見積る傾向がある．原因としては，二つ考えられる．

ンデックスキー上で漏れや抜けなく展開されている必要があ

一つめは，ビットアラインされていない時の桁上がりの効果

る．上記の検証結果に加え，2 つ以上の属性のあるビットが，を多めに見積もっているためである．ビットアラインされてインデックスキー上で同じ位置に展開されていないことを示いない時の桁上がり発生によるヒットページ数の増加を，桁すことができれば，scatter マスクで立っているビットの網羅

上がりの期待値として属性あたり 2bit を用いた．この期待性と排他性を示すことができる．これは，すべての scatter

値は，インデックスキーのビット長が無限とした時の極限値マスクを OR で 1 つのビット列に集約した時，すべてのビッである．二つめの原因としては，実験に用いたデータの特性

トが 1 になっていることを検証すればよい．

が挙げられる．この実験ではすべての属性値の分布が一様で

5. 評

価

はない．このため，ページのカバー範囲のばらつきにより少数のページで広範囲をカバーした結果，実際のヒットページ

5. 1 範 囲 検 索

数が少なくなった可能性がある．しかしながら，ビットアラ

インデックスキーの定義による範囲検索性能の影響についインされていない場合でも，見積もったページ数が多いほど，て評価する．
本提案手法を MD-HBase 上に実装し，検索性能を評価し実際にアクセスされるページ数も多いことから，インデック
スキーを設計する際の評価指標には成り得る．

た．評価のデータセットとしては，文献 [11] で例として挙5. 2 インデックスキーの生成

がっている通信会社や電力会社の請求書情報に関するスター

インデックスキーを構成する属性の数や属性のビット長をスキーマを参考に生成したデータセットを用いた．属性数は変えて，Scatter-OR 法によるインデックスキー生成性能を５で，それぞれ，32，32，16，16，8 ビットである．データ

評価する．

生成の際，属性ごとにデータ分布として単調増加，べき分布，

本論文では，Scatter-OR 法を Java で実装し，表 3 で示す

正規分布，一様分布，正規分布を指定し，１億件生成した．

環境で評価した．本評価では，属性のビット長が，8 ビット

インデックスキーの定義を index A,B,C の 3 通り用意し（byte 型），32 ビット（int 型）の二つを用意し，それぞれイ

た．この時，それぞれの場合で，ページはおおよそ 76 − 77

ンデックスキーを構成する属性の数を変化させたときの生成ビットの範囲をカバーするように分割された．
ヒットページ数のコスト計算の妥当性を検証するために，ページのカバー範囲を基準に検索範囲のカーディナリティを固定し，それぞれのインデックスキーでのヒットページ件

時間を計測した．計測値は，Scatter-OR 法を 1 万回適用した際の実行時間を 100 回繰り返した時の平均時間とした．結果を図 8 に示す．

4. 5 節で解析した通り，属性のビット長が 8 ビット，32 ビッ
—7—

実験環境

験を通じて，提案するヒットページ数のコストモデルが，イ

CPU

表3

Intel Core i5 1.8GHz

ンデックスキーを設計する上での評価指標になり得ることを

メモリ

8GB

OS

MacOS X 10.8.2

Java

1.6.0 37

示した．
今後は，例えば，階層的な集約や条件として指定しない場
合があるといった支配的な検索範囲の幅が複数あるような属性を含む場合へとコストモデルを拡張していきたい．また，

ϮϬϬϬ

本論文では十分に言及しなかったが，既存の Z-order を用いᐇ ϭϱϬϬ⾜᫬㛫咁吶呁 ϭϬϬϬ
⛊咂ϯϮďŝƚ

たインデックス手法に関連する最適化技術を一般化されたϴďŝƚ

Z-order を用いた手法に拡張していきたい．
文

ϱϬϬ

Ϭ
Ϭ

ϰ

ϴ

ϭϮ

ϭϲ

ᒓᛶ䛾ᩘ

ϮϬ

Ϯϰ

Ϯϴ

ϯϮ

図 8 Scatter-OR 法によるインデックスキー生成性能
実行時間は，scatter-OR 法を 1 万回実行した時の平均値

トの両方の場合で，インデックスキーを構成する属性の数に比例する時間がかかっていることがわかる．また，属性のビット長が 8 ビットと 32 ビットのものを比べると，結果のインデックスキー長に比例した実行時間がかかっていることがわかる．
インデックスキー生成にかかる時間を見てみると，最も時間がかかった，ビット長が 32 ビットの属性を 32 個から生成する場合でも，1 万回実行して 1 秒程度であるため，1 回あたり，0.1 ミリ秒程度であることがわかる．範囲検索をする
際，ディスクにレコードを走査する時間や，分散環境でネッ
トワーク越しにレコードを取得する時間のオーダはこれよりも十分に大きいため，この程度の実行時間ではインデックス
キー生成がボトルネックとなるとは考えにくい．

6. ま と め増え続ける複数の属性をもった多次元レコードに対して，
スケーラブルに，かつ，効率的な多次元範囲検索が可能な
データストアの実現にむけ，本論文では空間充填曲線を用い

献[1] Hanan Samet. Foundations of Multidimensional andMetric Data Structures. Morgan Kaufmann Publishers
Inc., San Francisco, CA, USA, 2005.
[2] Volker Markl. MISTRAL: Processing Relational Queries
using a Multidimensional Access Technique. PhD thesis,
TU München, 1999.
[3] J.A. Orenstein and T.H. Merret. A class of data structures for associate searching. In Proc. ACM SIGMOD
Intl. Conf. on Management of Data, pages 194–305, 1984.
[4] Shoji Nishimura, Sudipto Das, Divyakant Agrawal,
and Amr El Abbadi. MD-HBase: A Scalable Multidimensional Data Infrastructure for Location Aware Services. In MDM, pages 7–16, 2011.
[5] Volker Markl and Rudolf Bayer. Processing Relational
OLAP Queries with UB-Trees and Multidimensional Hierarchical Clustering. Proceedings of the International
Workshop on Design and Management of Data Warehouses, 2000:1–10, 2000.
[6] J. K. Lawder and P. J. H. King. Querying Multidimensional Data Indexed Using the Hilbert Space-Filling
Curve. SIGMOD Record, 30(1):19–24, 2001.
[7] Chris H. Hamilton and Andrew Rau-Chaplin. Compact
hilbert indices: Space-filling curves for domains withunequal side lengths. Information Processing Letters,
105:155–163, 2008.
[8] Tomáš Skopal, Michal Krátký, Jaroslav Pokorný, andVáclav Snášel. A new range query algorithm for Universal
B-trees. Information Systems, 31(6):489–511, September
2006.
[9] Henry S. Warren. Hacker’s Delight Second Edition, chapter 7, pages 156–157. Addison-Wesley Professional, October 2012.
[10] Intel Corporation.
Intel(R) Architecture Instruction
Set Extensions Programming Reference, August 2012.
http://software.intel.com/sites/default/files/319433-014.pdf.
[11] Ralph Kimball and Margy Ross. The Data Warehouse
Toolkit: the complete guide to dimensional modeling. Wiley Computer Publishing, second edition, 2002.

てインデックスキーを構成するデータストアに注目した．
本論文では，従来の Z-order では，属性ごとに指定される範囲の幅が均一でない場合，その範囲検索の効率が低下する
ことを，ヒットページ数のコストモデルを構築することで示した．同時に，インデックスキーを設計する際，各属性において，支配的な検索範囲の幅が推測可能である際，その知識を用いて，よりよいインデックスキーを設計する方針も示した．そして，Z-order を一般化し，この設計方針に基づいて
インデックスキーを設計する手法を提案した．最後に評価実—8—