DEIM Forum 2017 E5-3

QUILTS: クエリアウェアでスキュートレラントな空間充填曲線を用いた多次元データ分割フレームワーク
西村 祥治†,††

横田治夫††† 日本電気株式会社 〒 216–8666 神奈川県川崎市中原区下沼部 1753
† 東京工業大学情報理工学院 〒 152–8552 東京都目黒区大岡山 2-12-1
E-mail: †s-nishimura@bk.jp.nec.com, ††yokota@cs.titech.ac.jp
あらまし

近年、データ分析の対象となるデータ量の増大のため、データアクセスのボトルネックを解消するデータ管理技術が重要になってきている。このため、データ分析に必要なデータだけをアクセスするデータスキッピング技術が注目を集めている。基本的なアイデアは、データをページ分割し、クエリによって取得されるデータを含むページ
だけアクセスすることである。アクセスするページを最小にする必要があるが、与えられたクエリパターンやデータ分布を用いて最適解を求めることはＮＰ困難であることが知られている。そこで、我々は空間充填曲線を用いたデータ分割手法を提案する。我々は空間充填曲線とクエリパターンとデータ分布の関係をモデル化した。そして、そのモデルに基づき、対象となるクエリパターンに対して、データ分布に偏りに対して頑健な空間充填曲線を設計する手法を提案する。我々はこの手法を基に多次元データ分割フレームワークを構築し、ＤＷＨやＧＩＳを対象とした実世界のデータを用いた評価を行った。その結果、ページアクセス数を従来の空間充填曲線を用いるより 1 ケタ少なくできることを確認した。
キーワード

多次元インデックス, 空間充填曲線, データ分散

1. は じ め に空間充填曲線を用いて多次元データを一次元データ化するかによって、クエリ実行時にアクセスするページ数が変化する。こ近年、ウェブサイトのログや様々な機器からのセンサーデー

れまで、どの空間充填曲線を用いるべきかについて幅広く研究

タなど大量データの収集と分析が広まっている。多くのデータがされてきた [8], [17]。しかし、多くの研究は一般化された場合

分析では、その収集されたデータの一部だけを用いる。そこで、であるアドホックなクエリパターンを対象としており、特定の一部のデータだけを効率的に取り出すためデータスキッピン

クエリパターンに対してはあまり注意が払われてこなかった。

グ [14], [18] 手法が注目を集めている。基本的な考え方は、デー

また、空間充填曲線を選択する際、データ分布を考慮すること

タをページに分割し、クエリによって取得されるデータを含むも重要になる。しかしながら、我々の知る限り、データ分布とページだけをアクセスする。このクエリ性能はページアクセス

空間充填曲線の関係についてほとんど議論されていない。

数に比例するため、与えられたクエリパターンやデータ分布に

我々は空間充填曲線とクエリパタンおよびデータ分布の関係

対してページアクセス数を削減するようなデータ分割をするこについて分析をした。その結果、与えられたクエリパターンにとが重要になる。しかしながら、属性を複数持つ多次元データ

対して、データ分布の偏りに対して頑健な曲線を選ぶことで、に対して、最適なデータ分割を求めることは NP 困難であるこ

クエリ実行時にアクセスするページ数を抑えられることができとが知られている [18]。

ることを見出した。このような曲線をクエリ特化でスキュー耐

Sun らは最適に近いデータ分割を得るため、クエリパターン性がある曲線 (query-aware and skew-tolerant curve) と呼ぶ。

やデータ分布を考慮したクラスタリングアルゴリズムを用いる

そこで我々はこの曲線を基にした多次元データ分割のフ手法を提案している [18]。この手法によりページアクセス数をレームワークである QUILTS(QUery-Intensive Linearization

劇的に削減することに成功している。しかしながら、この手法

Tolerating data Skew) を提案する。その概要を図 1 に示す。

はクエリを実行する前にすべてのデータに対してクラスタリン

このフレームワークは、凝集性に基づくコストモデル、ビット

グアルゴリズムを適用する必要がある。

混合曲線族、曲線設計法の 3 つの要素から構成され、入力と別のデータ分割方法は空間充填曲線を用いる方法であしてクエリパターンを与えるとそのクエリパターンに対してる [8], [13]。この方法は多次元データを空間充填曲線上の点スキュー耐性がある曲線を出力として得ることができる。我々に一対一で対応付けることで、一次元データ化し、それを範囲

はこのフレームワークに基づいて試作した。そして、実世界の分割するものである。一次元化したデータを B-Tree や HBase

データを用いたアプリケーションで評価した結果、このフレーなど範囲分割するキーバリューストアのキーとして格納するこムワークが導出した曲線は、従来よく知られている曲線に対しとで、データの挿入や更新時に適切な範囲になるようにデータて、1 桁以上ページアクセス数を削減できることを確認した。

を分割することができる。しかしながら、この方法では、どの本論文の構成は以下のとおりである。2 章では空間充填曲線

(a) C-カーブ(b) Z-カーブ(c) ヒルベルトカーブ

図 2 代表的な空間充填曲線

連続性を評価する指標として clustering number を提案している [11]。そして、Pan らはヒルベルトカーブが一般的な場合における clustering number を最善にするカーブの一つであると証明している [21]。
図 1 QUILTS の概要

これらの研究は一般的な場合に注目している。しかしながら、実際の応用では、暗黙的な上限値や下限値や、典型的な集約単に関する関連研究について紹介する。３章では前提となる概念

位が存在する。このような制約条件下で、適切な空間充填曲線について説明する。４章ではクエリ特化でスキュー耐性があるを選択する上で注目すべき性質やその指標についてはあまり考曲線を用いたデータ分割手法を提案する。５章では評価を行い、慮されてこなかった。また、データ分布はクエリ性能に影響を有用性を示す。６章では結論を述べる。なお、本研究について与えるにも関わらず、データ分布に対する空間充填曲線の性質の詳細は文献 [16] を参照されたい。

は我々が知る限り、あまり考慮されていない。

2. 関 連 研 究

3. 前 提 知 識

2. 1 空間充填曲線に基づく索引

3. 1 空間充填曲線による多次元インデックス

多次元索引を実現する方法として空間充填曲線 [1] を用いる

空間充填曲線とは多次元空間上の点を漏れや抜けなく一筆書

手法 [15] が知られている。リレーショナルデータベース (RDB)

きでたどる曲線である。この曲線がたどる順番により多次元空で使われている B-Tree と組み合わせた手法 [6], [8], [20] や、間上の点が順序付けられる。すなわち、多次元空間上の点が一

HBase のような範囲分割のキーバリューストア上で多次元索引

次元の点へとマッピングすることができる。ここではこのマッを実現する手法 [4], [13], [22] など広く適用されている。例えば、ピングされた点のことをキーと呼ぶ。このキーの値によって整RDB で広く使われている複合インデックスは図 2(a) のような列して格納されたデータ構造を空間充填曲線による多次元イン軌跡を描く C-カーブを用いた索引である。属性の値を連結すデックスと呼ぶ。例えば、このキーを B-Tree や HBase などのることでデータの並び順を決定することができるため、属性ご

範囲分割型のキーバリューストア (KVS) に格納することで容との定義域の違いがある場合でも適用することができる。しか易に実現できる。このとき、データはキーの範囲に応じてペーし、高い性能を達成するには、クエリでの属性ごとの選択性をジに分割して格納される。B-Tree や HBase など多くのデータ

意識して属性の優先度を決定することが重要である [19]。

構造では、キーの範囲は各ページがだいたい同じ量になるよう

Z-カーブ (図 2(b)) [12] やヒルベルトカーブ (図 2(c)) [3] は特に調整される。

に空間索引で広く使われている空間充填曲線である。正方形のこのような多次元インデックスに対して多次元範囲クエリの構造が階層的に埋め込まれていることから、位置情報のように実行を模式的に示したものが図 3 である。多次元範囲クエリで各属性が同じ距離基準を持つような応用に適合しやすい。一方指定された領域は、空間充填曲線上で幾つかの連続する区間ので、この特徴から定義域が異なる属性からなる多次元データに集合に写像される。多次元範囲クエリの実行では、まずこれら適用する際、ゼロで埋めるなどしてデータ表現上の定義域を区間と重なるページ集合を抽出する。そしてこのページ集合を揃える必要がある。この結果、不必要にデータ量が増えることアクセスし、クエリ範囲内にあるデータを結果として報告する。

になる。そこで、これらのデータ増加を抑える曲線が幾つか提この例では、ページ 3,5,7,9 をアクセスするため、ページアク案 [2], [7] されているが、クエリ実行時のアクセスコストに主眼

セス数は 4 となる。

をおいていない。

ここで重要なことは、多次元範囲クエリの性能は、ページア

2. 2 空間充填曲線の性質の分析

クセス数に比例するという点である。つまり、クエリ実行時に

上記以外にも様々な空間充填曲線が提案される一方で、最アクセスしなければならないページ数を抑えることができるよ

適な空間充填曲線が持つべき性質およびそれを計測する指標に関する研究も広く行われている。例えば、Mokbel らは元のうな空間充填曲線を選ぶことが我々の目的である。

3. 2 空間充填曲線とクエリパターン

空間上で近傍にある二点を、空間充填曲線上でも近傍に写像

まず、空間充填曲線とクエリパターンの関係について整理す

する局所保存性を評価する指標として irregularity を提案してる。クエリパターンとは、多次元範囲クエリの形状の観点でのいる [9], [10]。また、Moon らはディスクシーク時のアクセス

クエリの種類分けで、各属性を選択する範囲の幅の直積としてϭƵƌǀĞϭ

WŽŝŶƚ

Ϯ

ϰ
ϲ

YƵĞƌǇZĞŐŝŽŶ ϱƵƌǀĞϮϯϵDƵůƚŝĚŝŵĞŶƐŝŽŶĂůƐƉĂĐĞ

(a) データ分布が疎である場合

ϳ
ϴ

ϭϬ

ƵƌǀĞϮYƵĞƌǇ ^ĞĐƚŝŽŶƐ

DŝŶ<ĞǇ

<ĞǇƵƌǀĞϭDĂǆ<ĞǇ

^ƉĂĐĞͲĨŝůůŝŶŐĐƵƌǀĞWĂŐĞƐ(b) データ分布が密である場合
ϭ

Ϯ

ϯ

ϰ

ϱ

ϲ

ϳ

ϴ

ϵ

ϭϬ

図 5 Query Section Layout and Data Distributions

図 3 Mapping Between Multidimensional Space and Space-FillingCurve

今、２つの空間充填曲線 Curve 1, 2 があり、ある多次元範
囲クエリに該当する空間充填曲線の区間がそれぞれ図 5 の赤太線であったとする。データ分布が疎な場合、Curve 1 は一つƚƚƌŝďƵƚĞϭYƵĞƌǇϭƚƚƌŝďƵƚĞϮƚƚƌŝďƵƚĞϮƚƚƌŝďƵƚĞϭYƵĞƌǇϭのページにすべての区間が含まれているため、ページアクセス
数は１である。一方 Curve 2 のページアクセス数は 2 である。
データ分布が密な場合、Curve 1 でのページアクセス数は 3 でYƵĞƌǇϮYƵĞƌǇϮ

あるが、Curve 2 では 2 である。このことから、データ分布の違いによって、ページアクセス数の観点で最適となる空間充填
曲線が変わり得ることが推察できる。

(a) C-curve(b) Z-curve

図 4 Space-Filling Curves and Query Patterns

実際のデータセットはデータ分布が疎である領域もあれば、密である領域も存在する。また、あるクエリパターンによる領域がある空間充填曲線上に写像される区間の配置パターンは、表現する。例えば、次元数が d あり、属性 i の選択幅が Wi とす

領域の起点となるビットのアライメントが同じであれば、同じると、そのクエリパターンは W1 × W2 × ... × Wd と表現する。

パターンになる。このことから、あるクエリパターンに対して、クエリパターンがページアクセス数に与える影響について図

データ分布の疎密に関わらず、ページアクセス数を低く抑えら??を用いて模式的に分析する。ここでは空間充填曲線としてれるような空間充填曲線を利用することが望ましい。そこで、

C-カーブと Z-カーブを対象とし、クエリパターンとして各属

このような曲線をスキュー耐性がある曲線 (skew-tolerant

性の選択幅が等しい Query 1（点線で囲まれた矩形）と各属性

curve) と呼ぶ。

の選択幅が極端に異なる Query 2（太線で囲まれた矩形）を考える。それぞれのクエリパターンを表す矩形の中での曲線の軌

4. 提 案 手 法跡の連続性に注目して分析する。すると、C-カーブは、Query

以上の議論から、与えられたクエリパターンに対して、デー

1 では非連続が、Query 2 では連続である。一方、Z-カーブは、

タ分布の疎密に関わらずページアクセス数を低く抑えられる空

Query 1 では連続であるが、Query 2 では非連続である。一般間充填曲線を用いて多次元インデックスを構成すると高い性能的に、クエリ範囲内での曲線の軌跡が連続するほど、クエリでを達成すると考えることができる。以下では、このような空間取得するデータが同一のページに含まれやすい。逆に非連続に充填曲線の性質を捉えるコストモデルおよびこの指標の観点でなるほど別のページに分かれやすい。このことから、空間充填

最適な空間充填曲線を設計する手法について説明する。

曲線ごとに適合しやすいクエリパターンがあるといえる。そこ

4. 1 凝集性に基づくコストモデル

で、あるクエリパターンと相性がよい空間充填曲線をクエリ特空間充填曲線のデータ分布に対する性質を捉えるコストモデ化した曲線 (query-aware curve) と呼ぶ。

ルを設計するために、もう一度図 5 を注意深く観察する。デー

3. 3 空間充填曲線とデータ分布

タ分布が疎である場合において、Curve 1 が Curve 2 よりも次に、空間充填曲線とデータ分布の関係について整理する。

ページアクセス数が少なくなった理由は、クエリ領域の空間充

ここではページに容量があり、データの挿入や削除により、

填曲線上への写像となる区間全体がコンパクトにかたまっていページ内のデータの件数が一定量を超えて変動した場合、一定るからである。このため、ページがカバーする範囲が比較的広に保つようにページの分割あるいは結合により調整が行われる

い場合、一つのページで区間全体がカバーされやすくなる。一ことを仮定する。これは、RDB 中の B-Tree や範囲分割型の方で、データ分布が密である場合において、Curve 2 が CurveKVS である HBase などで一般的にサポートされている機能で1 よりもページアクセス数が少なくなった理由は、空間充填曲ある。この時、データ分布が密である領域にあるページはペー線上に写像されたクエリ領域の区間が局所的にコンパクトにかジの分割が進み、ページがカバーする範囲が狭くなる。一方でたまっているからである。このため、ページがカバーする範囲

データ分布が疎である場合は、逆にページがカバーする範囲がが比較的狭い場合、少ないページ数で区間全体がカバーされや広くなる。

［定義 3］（総合凝集性） 総合凝集性 CT とは大域的凝集性と
^&Ͳϯ

ф

番目の間隔の長さを ni とすると、

фф ^&ͲϱCT = CG · CLф>ŽĐĂůŽŚĞƐŝŽŶŽƐƚ^&ͲϮ

局所的凝集性をかけ合わせたものとして定義する。すなわち、i

^&Ͳϲ

ф

ф

^&Ͳϭ

= (

^&Ͳϰ

ф

X

ni )(−i= ('ůŽďĂůŽŚĞƐŝŽŶŽƐƚXi

充填曲線上で遠く離れ、これらの区間の間に多数のページが存在することになったとしても、クエリ実行におけるページアクセス数には影響を与えない点である。
以上から、図 6 に示すように、大域的な区間の凝集性と局所的な凝集性の二つの観点から空間充填曲線を評価するコストモ
デルを提案する。
［定義 1］（大域的凝集性） 大域的凝集性 CG とは、空間充填曲線上に写像されたクエリの区間全体のまとまり具合を評価する指標である。クエリの区間と区間の間となる間隔の長さの総和として定義する。すなわち、i 番目の間隔の長さを ni とすると、

CG =

ni

i

n
i i

ni ) −

ni
log P
)
n
i i

X

(ni log ni )

(3)

i

である。

すくなる。ここで注目すべき点は、ある区間とある区間が空間

X

Pni

X

ni ) log(i

図 6 凝集性に基づくコストモデル

X

(1)

i

あるクエリパターンに対して適切な空間充填曲線を選択する
際、この総合凝集性をコストとして曲線を評価する。

4. 2 C-カーブと Z-カーブの凝集性コスト分析
様々なクエリパターンに対して Z-カーブと C-カーブの凝集性コストを計測し、コストモデルの妥当性を評価するとともに傾向について評価する。ここでは、7 つのクエリパターン(2 × 128, 4 × 64, 8 × 32, 16 × 16, 32 × 8, 64 × 4, 128 × 2) についてそれぞれ凝集性コストを計測した。その結果を図 7 にまとめる。
まず、C-カーブの結果について分析する。すると大域的凝集性、局所的凝集性とも 2 × 128 のときが最小になり、128 × 2 となる。総合凝集性はこれらを掛け合せたものであるため、同様の傾向である。これはちょうど、複合インデックスにおいて範囲の選択性が高い属性を優先して結合した方が性能が高く、そである。

れを逆の結合順にすると著しく性能が悪化するという結果と一［定義 2］（局所的凝集性） 局所的凝集性 CL とは、空間充填曲

致している。

線上に写像されたクエリの区間の局所的なまとまり具合を評価

次に Z-カーブの結果について分析する。Z-カーブの場合、大する指標である。クエリの区間と区間の間となる間隔の総和に

域的凝集性は 16 × 16 の正方形型のクエリパターンのときに最対する各間隔の割合のエントロピーとして定義する。すなわち、小になる。一方、局所的凝集性はどのクエリパターンでもあまi 番目の間隔の長さを ni とすると、

り変化しない。これらを掛け合せた総合凝集性では 16 × 16 の

CL = −

X
i

Pni

n
i i

ni
log P
n
i i

(2)

である。
空間充填曲線上に写像された区間ではなく、区間と区間の間隔に着目する点がポイントである。なぜなら、クエリ範囲内にあるデータ件数が多くてページアクセス数が多くなることは問題ではなく、クエリ範囲外にあるデータによって不必要にペー
ジアクセス数が多くなることが問題であると考えるからである。また、局所的凝集性でエントロピーを用いるのは、間隔の数の少なさと間隔の長さの偏りを評価したいからである。間隔の長さの総和が一定で間隔の数が同じであるならば、各間隔の長さがすべて等しいよりも著しく偏りがある方が、区間同士が局所的にかたまっているといえるからである。
あるクエリパターンに対して、ある空間充填曲線の大域的凝集性および局所的凝集性が共に小さい値である時、データ分
布の疎密に関わらずページアクセス数を抑えることが期待できる。このような曲線をクエリに特化し、スキュー耐性がある
曲線 (query-aware and skew-tolerant curve) と呼ぶ。また、これらを総合的に評価する指標として、総合凝集性を定義する。

クエリパターンのときに最小になる。以上の結果から、このコストモデルは妥当であると推測できる。
最後に興味深い結果について報告しておく。8 × 32 のクエリパターンに着目する。大域的凝集性に関しては C-カーブが、局所的凝集性に関しては Z-カーブがよい性質を示している。そして、総合凝集性は両カーブとも同程度の数値である。ページの都合で実験結果の詳細を省略するが、データ件数が少なく、ページがカバーする範囲が広い場合、すなわち、データ分布が疎である場合は C-カーブのほうが、逆にデータ件数を増やし、ページがカバーする範囲が狭い場合、すなわち、データ分
布が密である場合は Z-カーブのほうが少なかった点を報告しておく。

4. 3 曲線設計法
ここでは、任意のクエリパターンが与えられた時、適切な空間充填曲線を設計する手法について提案する。前節では、属性の範囲幅が大きく異る、全て等しいという極端なクエリパター
ンに対して、それぞれ C-カーブおよび Z-カーブが適合することを見てきた。では、これらの中間的なクエリパターンに対しては、どのような空間充填曲線を選択すればよいだろうか。以下では、C-カーブと Z-カーブを一般化し、C-カーブや Z-カーͲĐƵƌǀĞ

ͲĐƵƌǀĞ

ϯϬϬϬϬ

ϱ

ϮϱϬϬϬ
ϮϬϬϬϬ
ϭϱϬϬϬ
ϭϬϬϬϬ
ϱϬϬϬ

ͲĐƵƌǀĞ

ͲĐƵƌǀĞ

ͲĐƵƌǀĞ

ϭϴϬϬϬϬ
ǀĞƌĂŐĞdŽƚĂůŽŚĞƐŝŽŶŽƐƚϲǀĞƌĂŐĞ>ŽĐĂůŽŚĞƐŝŽŶŽƐƚǀĞƌĂŐĞ'ůŽďĂůŽŚĞƐŝŽŶŽƐƚͲĐƵƌǀĞ
ϯϱϬϬϬ

ϰ
ϯ
Ϯ

ϭϲϬϬϬϬ
ϭϰϬϬϬϬ
ϭϮϬϬϬϬ
ϭϬϬϬϬϬ
ϴϬϬϬϬ
ϲϬϬϬϬ
ϰϬϬϬϬ

ϭ
ϮϬϬϬϬ

Ϭ

Ϭ

Ϭ

ϮǆϭϮϴ ϰǆϲϰ ϴǆϯϮ ϭϲǆϭϲ ϯϮǆϴ ϲϰǆϰ ϭϮϴǆϮYƵĞƌǇWĂƚƚĞƌŶƐ

ϮǆϭϮϴ ϰǆϲϰ ϴǆϯϮ ϭϲǆϭϲ ϯϮǆϴ ϲϰǆϰ ϭϮϴǆϮYƵĞƌǇWĂƚƚĞƌŶƐ

(a) Global Cohesion CostϮǆϭϮϴ ϰǆϲϰ ϴǆϯϮ ϭϲǆϭϲ ϯϮǆϴ ϲϰǆϰ ϭϮϴǆϮYƵĞƌǇWĂƚƚĞƌŶƐ

(b) Local Cohesion Cost(c) Total Cohesion Cost

図 7 Cohesion Cost Analysis of Query Patterns with Constant Area SizeŝƚĐŽŶĐĂƚĞŶĂƚŝŶŐ
ǆǆǆǇǇǇǆǇǆǆǇǇŝƚŝŶƚĞƌůĞĂǀŝŶŐ
ǆǇǆǇǆǇ

ト数が ni とすると、ni に関する多項分布係数になるため、

P

(

Q

ƚƚƌŝďƵƚĞyƉƌĞĐĞĚĞŶĐĞ

ni )!
0<
=i<d

(ni !)0<=i<dになる。このため、あるクエリパターンに対してありとあらゆǇǇǇǆǆǆ

ǇǆǇǇǆǆ

ǇǆǇǆǇǆ

るビット混合曲線族の凝集性コストを求め、最適な空間充填曲線を選定することは非現実的である。そこで、クエリパターンとビット混合順について定性的に分析し、ヒューリスティックƚƚƌŝďƵƚĞzƉƌĞĐĞĚĞŶĐĞ

を設計することを試みる。
図 8 ビット混合曲線族の例

まず、4. 2 節での分析をビット混合順の観点で再度検討してみる。図 9 にクエリパターンと、C-カーブと Z-カーブの軌跡のブの中間的な性質を持った空間充填曲線の構成方法について説明する。そして、与えられたクエリパターンに対して、適切な空間充填曲線を選択するヒューリスティックを提案する。

4. 3. 1 ビット混合曲線族
C-カーブと Z-カーブは一見すると全く別物の空間充填曲線に見える。しかし、その構成法に着目するととても良く似ている。

C-カーブは、属性値をビット列としてみた時、これらのビット列を連結することで構成する。一方で、Z-カーブは、ビット列を互い違いに混ぜ合わせることで構成する。例えば、4 ビットの二次元値 hx1 x2 x3 x4 ,y1 y2 y3 y4 i を考える。C-カーブにおいてこの二次元値の空間充填曲線上での順序は、x1 x2 x3 x4 y1 y2 y3 y4 で定義できる。一方で、Z-カーブの場合は、x1 y1 x2 y2 x3 y3 x4 y4 で定義できる。つまり、これらの空間充填曲線の構成上の違いは、属性値であるビット列を混合する順序の違いであるといえる。
そこで、このビット混合順序の観点で一般化した空間充填曲線の集合をビット混合曲線族 (bit-merging curve family) と呼ぶ。図 8 にその例を示す。
ビット混合曲線族はビット混合順により一意に曲線を識別することができる。一方でビット混合順で曲線を表すにはスペースを使いすぎてしまうため、ランレングス符号化した表記を用いる。例えば、x1 y1 y2 y3 y4 x2 x3 x4 は、x1y4x3 と表記する。また、カッコを付けてビット列をグループ化してもよい。例えば、

Z-カーブ x1 y1 x2 y2 x3 y3 x4 y4 は、(xy)4 と表記する。
4. 3. 2 クエリパターンとビット混合順
ビット混合曲線族を導入することにより、空間充填曲線の設
計空間は爆発的に増加する。設計空間の広さは、属性 i のビッ

関係を整理する。C-カーブは 8 × 2 の、Z-カーブは 4 × 4 のクエ
リパターンの時、クエリ範囲内の軌跡が連続している。これらのクエリパターンを 23 × 21 、22 × 22 と表記を変えて、それぞれのビット混合順を比較する。すると 23 × 21 のべき数の 3 と 1に着目すると C-カーブのビット混合順の y3x3 において、x の

3 ビットと y の 1 が下位に配置されている。同様に 22 × 22 のべき数の 2 と 2 に着目すると Z-カーブのビット混合順の yxyxyx
において、x の 2 ビットと y の 2 が下位にかたまっている。つまり、クエリパターンの範囲幅を 2 のべき数で表記したときのべき数に相当するビットがビット混合順において下位に配置されているとクエリ範囲内の軌跡が連続する。ここから、クエリパターンの範囲幅を 2 のべき数で表記したときのべき数に相当するビットがビット混合順において下位に配置されているビット混合曲線は、このクエリパターンに対して総合凝集性コストを低く抑えるのではないかと推察できる。
そこで、80 種類以上のビット混合曲線を機械的に生成し、ク
エリパターン 8 × 32 = 23 × 25 に対する総合凝集性を計算した。総合凝集性のコストが低いもの順に並べた結果上位 25 の曲線を図 10 にまとめる。この時、x に関しては 3 ビット分、yに関しては 5 ビット分がビット混合順において下位に配置されているものは濃い色で示す。すると上記で推察した曲線が数多く上位に占めていることが分かる。

4. 3. 3 曲線設計法
以上の分析結果を踏まえて、ヒューリスティックによる曲線設計法を提案する。

ϮhǆϮ>ǆƵǆ ďŝƚƐ

Ϯ>ǇƵǇ ďŝƚƐ

ůǆďŝƚƐůǇ ďŝƚƐ

ϮhǇ
z͗

y͗

(a) C-curve, 8x2(b) C-curve, 4x4(c) C-curve, 2x8
ŝƚͲDĞƌŐŝŶŐƵƌǀĞ

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
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 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
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 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
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 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ůǆнůǇ ďŝƚƐƵǆ нƵǇ ďŝƚƐ図 12 Curve for Multiple Query Patterns(d) Z-curve, 8x2(e) Z-curve, 4x4(f) Z-curve, 2x8

表 1 Data Model for Retail Sales Analysis

Dimension Layered Attribute Bit Length Distribution
図 9 Query Patterns and Trajectory Continuity

Date

32

%LW0HUJLQJ&XUYHVProduct;<;<;<;<;<;<;<;<<;<
;<;
;<;<;<;<;<;
<;<;
;<;<;<;<;<;<;<;<;<;<;<;<<;<;
;<;<;<;<;<;<;<;<<;<;
<;<;
<;<
<;<;ϭϯϯϲ͘ϲϬϭϯϰϯ͘ϰϱϭϰϮϯ͘ϯϭϭϰϯϯ͘ϭϳϭϱϬϵ͘ϵϯϭϱϮϲ͘ϭϵϭϲϬϵ͘ϰϬϭϲϭϭ͘ϱϲϭϲϯϰ͘ϰϬϭϲϯϳ͘ϵϱϭϲϲϯ͘ϲϬϭϳϬϴ͘Ϭϯϭϳϵϴ͘ϵϱϭϴϯϬ͘ϰϵϭϵϬϮ͘ϯϰϭϵϰϰ͘ϭϭϮϬϬϳ͘ϲϬϮϬϰϱ͘ϮϭϮϬϱϵ͘ϬϮϮϬϲϰ͘ϱϵϮϬϲϲ͘ϲϰϮϬϳϭ͘ϲϲϮϬϳϱ͘ϯϰϮϭϮϯ͘ϯϲϮϭϱϵ͘ϳϵϬ͘ϬϬϱϬϬ͘ϬϬ

ϭϬϬϬ͘ϬϬ

ϭϱϬϬ͘ϬϬ

ϮϬϬϬ͘ϬϬ

ϮϱϬϬ͘ϬϬ

Poisson(32)
Department

8

Zipf

Category

10

Zipf

Brand

14

Zipf

Store

(32)
Region6

NormalStore

10

Normal

表 2 Aggregation Unit and Query-Range Width

Date

ProductStore

day (16.4 bits)

category (14 bits)

region (10 bits)

week (19.2 bits)

department (24 bits)

month (21.3 bits)を求める。属性ごと選択幅のビット数の最大値と最小値を求める。次に、これらの値で各属性を 3 つの部分に分解し、属性間で部分ごとにビットを混合する (図 12)。

5. 評

価

7RWDO&RKHVLRQ&RVW

提案するカーブの有用性を、データウェアハウスおよび地理図 10 Top 25 Candidate Curves for 8 × 32 Queries

情報システムを題材とした評価実験を行う。

5. 1 データウェアハウスを題材とした評価
ϮĚǆ

ここでは、文献 [5] で紹介されているケーススタディを基にĚǆďŝƚƐϮĚǇĚǇ ďŝƚƐz͗y͗

データモデルを定義した。表 1 にその詳細をまとめる。この
データセットには Date, Product, Store の 3 つの次元がある。
各次元は表に示すデータ分布に従う。この時、各次元ごとに偏ŝƚͲDĞƌŐŝŶŐƵƌǀĞ

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 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 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 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ĚǆнĚǇ ďŝƚƐ図 11 Curve for Single Query Pattern

りの度合いが変わる点に注意する。この応用での典型的なワークロードは集約演算である。各次元はそれぞれ階層的な集約単位を持ち、その任意の組み合わせをこの応用における典型的なクエリパターンとした。各次元における集約単位およびその選
択幅を表 2 にまとめる。

a ) クエリパターンが単一である場合

これらの情報をもとに空間充填曲線を設計する。Date, Prod-

まず、クエリパターンの各属性における選択幅のビット数を

uct, Store 属性に対応するビットを d, p, s とする。提案する曲求める。そして、そのビット数に相当するビットをビット混合

線は p8s6d12p10d20s10 である。比較対象の曲線として RDB

順序において下位に配置する (図 11)。

実装で典型的な C カーブとして s16d32p32 を、Z カーブとしb ) クエリパターンが複数ある場合て (sdp)16(dp)16 と (dp)16(sdp)16 の 2 種類を用意した。さらまず、各クエリパターンの各属性における選択幅のビット数に実用上よく使われるインデックスの実装として R*-Tree も用表 3 Aggregation Units and Query-Range Widths

Longitude & Latitude

Time

0.0001 (6.6 bits)

hour (11.8 bits)

0.001 (10.0 bits)day (16.4 bits)

0.01 (13.3 bits)

week (19.2 bits)

0.1 (16.6 bits)

month (21.3 bits)

幅の増分が異なる点に注意する。すなわち、位置に関する次元のほうが時刻より選択幅が相対的に小さく、位置に関する次元の選択幅の増分は均一であるが、時刻はそうではない。
提 案 す る 曲 線 と し て 、次 元 間 の 選 択 幅 の 相 違
だ け を 考 慮 し た (xy)5(txy)27t5(提 案 カ ー ブ 1) と 、
選 択 幅 の 増 分 の 相 違 も 考 慮 し て 設 計 し た 曲 線(xy)5(xyt)10t2(xy)3t3(xy)4(xy)3t5(xyt)7t5(提 案 カ ー ブ 2)
意した。
実験のため、上記のデータモデルに従って、1 億件のデータを生成した。ページの許容量を 1000 件に設定してデータをロードしたところ、各実装ともおよそ 20 万ページに分割された。各次元の任意の集約単位の組み合わせごとに 1000 種類のクエリを生成し、クエリを実行し、平均ページアクセス数で評価した。
その結果を図 13 にまとめる。縦軸は平均ページアクセス数であり、対数目盛となっている。横軸はクエリパターンである。
提案カーブはすべてのクエリパターンにおいて最も良い結果を得ることができた。2 番めに良かった Z カーブ 1 と比較しても最大で 6 分の 1 にページアクセス数を抑えることができた。
提案カーブは想定するクエリパターン全てに対してなるべく適合するように設計したため、全クエリパターンに渡ってページ
アクセス数を抑えることができた。一方で、Z カーブ 1 は各次元の選択幅が近いクエリパターンでは提案カーブに迫るものの、選択幅が大きく異なるクエリパターンではページアクセス数が増加した。
意外だったのは R*-Tree の結果である。選択幅が小さいときを用意した。比較対象として、Z-カーブを時刻優先の (txy)32(Z
カーブ 1) と位置優先の (xyt)32(Z カーブ 2) の２種類を用意した。また、他の種類の空間インデックスとして R*-Tree を用意した。
データをそれぞれの実装に対してロードしたところ、それぞれおよぼ 20 万ページに分割された。それぞれのクエリパター
ンに対して 1000 種類のクエリを生成し、クエリを実行した際の平均ページアクセス数で評価した。その評価結果を図 14 にまとめる。
クエリパターンをより考慮した提案カーブ 2 が 10 種類のク
エリパターンにおいて最も良い結果を得た。一方でこの曲線は、時間次元の選択幅が小さく、空間次元の選択幅が大きいク
エリタイプでは結果が悪かった。この原因としては、すべてのクエリパターンにおいて、クエリパターンが関係するビットを下位に配置するようなビット混合順序を定義することができな
いことに起因している。このことから、複数のクエリパターン
でビット混合順序が干渉する場合、どのクエリパターンの性能向上させるかを優先付ける必要がある。

は相対的によい結果である。しかし、選択幅が大きくなるに連れてページアクセス数が増加した。この理由としては、Product
次元が他の次元と比べてデータ分布の偏りが大きいことが影響しているためと考えられる。すなわち、Product 次元のデータ
分布の偏りが大きいため、この次元の方向にページ分割がされやすくなったと考えられる。この結果、Product 次元の選択幅が大きくなるにつれ、顕著にページアクセス数が増加したと考えられる。提案カーブはデータ分布の偏りに対して寛容な性質を持っているため、R*-Tree のような結果に陥らなかったと考える。

5. 2 地理情報システムを題材とした評価
この評価実験では、NYC Yellow Taxi の 2015 年一年間の

6. お わ り に我々は、クエリ特化でスキュー耐性がある空間充填曲線を用いた多次元データ分割フレームワークを提案した。このフレームワークでの技術的な貢献は、(1) 空間充填曲線のクエリパター
ンおよびデータ分布に対する性質を明らかにするモデル、(2)Zカーブと C-カーブを一般化し、空間充填曲線の設計空間を爆発的に拡張したビット混合曲線族、(3) ビット混合曲線族を用いた曲線設計法である。このフレームワークを用いることで、クエリパターンやクエリの制約条件を考慮してクエリ性能を向上させることができることを、二種類の応用で 1 桁近く性能改
善しうることを示した。

位置情報ログのデータセットを用いた評価をした。このデータセットは 1.5 億件のレコードが含まれていた。しかし、このう
ち 2% は GPS 機器の故障と思われる無効なデータが含まれていた。このデータセットは、タクシーが乗客を乗せた／降ろし
た位置（緯度と経度）と時刻、乗客数、支払額などの情報が含まれている。
この評価実験では、時空間統計分析をワークロードとして想定した。すなわち、場所や期間あたりの乗客数、売上高を計算するものである。範囲検索の対象となる次元は、緯度、経度、時刻の 3 次元である。各次元の集約単位は実用上意味のある単位を選び、表 3 のとおりである。これらの選択幅の任意の組み合わせを評価対象のクエリパターンとした。また、この集約単位に関して、位置（緯度、経度）と時刻とで選択幅および選択

文

献[1] M. Bader. Space-Filling Curves: An Introduction with Applications in Scientific Computing, volume 9 of Texts in
Computational Science and Engineering. Springer Berlin
Heidelberg, 2013.
[2] C. H. Hamilton and A. Rau-Chaplin. Compact hilbert indices: Space-filling curves for domains with unequal side
lengths. Information Processing Letters, 105:155–163, 2008.
[3] D. Hilbert.
Ueber stetige abbildung einer linie auf
flächenstück. Mathematische Annalen, 38:459–460, 1891.
[4] S. Huang, B. Wang, J. Zhu, G. Wang, and G. Yu. R-hbase:
A multi-dimensional indexing framework for cloud computing environment. In Data Mining Workshop (ICDMW),
2014 IEEE International Conference on, pages 569–574,
Dec 2014.

ͲĐƵƌǀĞ͗ƐϭϲĚϯϮƉϯϮͲĐƵƌǀĞϭ͗;ƐĚƉͿϭϲ;ĚƉͿϭϲͲĐƵƌǀĞϮ͗;ĚƉͿϭϲ;ƐĚƉͿϭϲZΎͲdƌĞĞ

ĞƐŝŐŶĞĚ͗ƉϴƐϲĚϭϮƉϭϬĚϮϬƐϭϬϳϲϲ͘ϰϳ
ϳϰϰ͘Ϯϭ

ϭϬϬϬϭϵϳ͘ϲϵ
ϲϱ͘ϴ

ϭϬϬ
ϯϭ͘ϱϭ
ϭϬ

ϭϲ͘Ϯϵ

ϯ͘ϰϭ ϯ͘ϯϴϭϴϲ͘ϲϭ

ϲϯ͘ϳϵ
Ϯϯ͘ϰϭ

ϵ͘ϰϵ

ϳ͘ϴϳ

ϭϮ͘ϲ

ϲ͘Ϯϰ

ϮϬ͘ϭϮ

ϵ͘ϰϳ

Ϯ͘ϳϱ
ϭ͘ϰϭ

ϭ͘Ϭϳ

ϭ

ϲϵ͘ϰϴ
ϲϮ͘Ϯϵ

ϯϭ͘ϲϲ

ϭϳ͘ϲϯ
ϭϲ͘ϳϱ
ϱ͘ϲ

Ϯϭϳ͘Ϯϲ
ϮϬϯ͘ϱ

ϳϮ͘ϭϲ
ϲϳ͘ϳϰ

ĚĂǇ

ǁĞĞŬ

ŵŽŶƚŚ

ĚĂǇ

ǁĞĞŬ

ĐĂƚĞŐŽƌǇ

ŵŽŶƚŚĚĞƉĂƌƚŵĞŶƚ

図 13 Average Number of Page Accesses by Retail Sales Analysis Query=FXUYH W[\ =FXUYH [\W 

5 7UHH'HVLJQHG [\  W[\ W'HVLJQHG [\  [\W W [\ W [\  [\ W [\W W











KRXU















GD\









ZHHN





PRQWK

図 14 Average Numbers of Page Accesses through GIS Analysis Query[5] R. Kimball and M. Ross. The Data Warehouse Toolkit: thecomplete guide to dimensional modeling. Wiley Computer
Publishing, second edition, 2002.
[6] J. K. Lawder. Querying multi-dimensional data indexedusing the hilbert space-filling curve. SIGMOD Record,
30:2001, 2001.
[7] V. Markl. MISTRAL: Processing Relational Queries using a Multidimensional Access Technique. PhD thesis, TU
München, 1999.
[8] V. Markl and R. 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.
[9] M. F. Mokbel and W. G. Aref. Irregularity in multidimensional space-filling curves with applications in multimedia
databases. In In Proceedings of the International Conference on Information and Knowledge Managemen, CIKM,
2001.
[10] M. F. Mokbel, W. G. Aref, and I. Kamel. Analysis of multidimensional space-filling curves. Geoinformatica, 7(3):179–
209, Sept. 2003.
[11] B. Moon, H. V. Jagadish, C. Faloutsos, and J. Salz. Analysis of the clustering properties of hilbert space-filling curve.
IEEE Trans. Knowl. Data Eng., TKDE, 13(1):124–141,
2001.
[12] G. M. Morton. A computer oriented geodetic data base anda new technique in file sequencing. Technical report, IBM
Ltd., 1966.
[13] S. Nishimura, S. Das, D. Agrawal, and A. El Abbadi.
MD-HBase: A Scalable Multi-dimensional Data Infrastructure for Location Aware Services. In Proceedings of 12th
IEEE International Conference on Mobile Data Management, MDM, pages 7–16, 2011.
[14] V. Raman, G. Attaluri, R. Barber, N. Chainani, D. Kalmuk,
V. KulandaiSamy, J. Leenstra, S. Lightstone, S. Liu, G. M.
Lohman, T. Malkemus, R. Mueller, I. Pandis, B. Schiefer,
D. Sharpe, R. Sidle, A. Storm, and L. Zhang. Db2 with blu

[15]

[16]

[17]

[18]

[19]
[20]

[21]

[22]

acceleration: So much more than just a column store. Proc.
VLDB Endow., 6(11):1080–1091, Aug. 2013.
H. Samet. Foundations of Multidimensional and Metric
Data Structures. Morgan Kaufmann Publishers Inc., San
Francisco, CA, USA, 2005.
N. Shoji and Y. Haruo. Quilts: Multidimensional partitioning framework based on query-aware and skew-tolerant
space-filling curves. In Proceedings of the 2017 ACM SIGMOD International Conference on Management of Data,
SIGMOD ’17, 2017. (to appear).
T. Skopal, M. Krátký, J. s. Pokorný, and V. Snášel. A newrange query algorithm for Universal B-trees. Information
Systems, 31(6):489–511, Sept. 2006.
L. Sun, M. J. Franklin, S. Krishnan, and R. S. Xin. Finegrained partitioning for aggressive data skipping. In Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, SIGMOD ’14, pages 1115–
1126, New York, NY, USA, 2014. ACM.
Sybase, Inc. Performance and Tuning: Basics, Aug. 2003.
Chapter 13: Indexing for Performance.
M. White. N-trees: large ordered indexes for multidimensional space. Technical report, Statistical Research
Division, US Bureau of the Census, 1982.
P. Xu and S. Tirthapura. On the optimality of clustering
properties of space filling curves. In Proceedings of the 31st
Symposium on Principles of Database Systems, PODS ’12,
pages 215–224, New York, NY, USA, 2012. ACM.
Y. Zou, J. Liu, S. Wang, L. Zha, and Z. Xu. Ccindex: A
complemental clustering index on distributed ordered tables
for multi-dimensional range queries. Network and Parallel
Computing, 6289:247–261, 2010.