日本データベース学会和文論文誌
一般論文

Vol. 20-J, Article No. 11, 2022年 3月

深層強化学習を用いた空間データパ

り当てる．例えば，ユーザ ID に対してハッシュを用いた分割をーティションニング手法の提案

る．データパーティショニングでは，各マシンに割り当てられた行うことで，特定のユーザのデータのみを選択的に処理可能であ
パーティションに対するクエリの並列処理が可能となるためスル

堀 敬三1
鬼塚

佐々木勇和2

ープットが向上する．さらに，パーティショニングが効果的に行

天方 大地3

われていれば，参照が必要となるパーティションは限られるため

I/O が大幅に削減される．パーティション単位での処理が可能と真4なることで，大規模データセットの管理性や可用性の向上が期待できる．

膨大な空間データに対する高速な分析処理のために，空間デー

しかしながら，一般的なデータベースシステムで用いられるハ

タ分析に特化した並列分散処理フレームワークが開発されていッシュなどのパーティショニング手法 [11]は空間データには適しる．データパーティショニング技術は，並列分散処理におけるクていない．例えば，カラムに緯度や経度の位置情報を含む空間デエリの実行時間に大きく影響するため様々な技術が提案されていータを持つテーブルにハッシュパーティショニングを適用する場

る．しかし，既存の空間データパーティショニング手法は汎用的合を考える．空間分析においては特定の地域や区域など，まとまな利用のために設計されたアルゴリズムであり，データ分布やクった範囲を対象とする処理が多いが，ハッシュでは各レコードがエリワークロードの特性に合わせたパーティションの最適化は実持つ位置情報に関係なく分割されるため，検索時には参照が必要

現できない．そのため，本研究では深層強化学習を用いた空間デなパーティションが多くなりアクセスの効率が低下する．そのたータパーティショニング手法を提案する．データ分布とクエリワ

め，空間データパーティショニングにおいては以下の課題が挙げークロードの両方に適応するように学習を行い，最適なパーティ

られている [20, 21]．第一に，位置的に近いデータ同士を同じパションを生成することで空間クエリの高速化を図る．評価実験よーティションに分割することで効率的なアクセスを可能にする．

り，提案手法では一部クエリにおける実行時間を削減できること

第二に，パーティション毎のデータ数を同程度に分割することでを示す．

マシン間のワークロードバランスを保つ．第三に，境界オブジェ
クトを最小化することでオーバーヘッドを削減する．境界オブジ

1 はじめにェクトとは，ポリゴンやラインストリングなどの範囲を持つジオ

IoT 技術の進歩や SNS の普及に伴い，街中のセンサデータやメトリタイプにおいて，複数のパーティションにまたがる位置にジオタグ付き投稿など，日々膨大な空間データが生成されてい存在するデータのことを指し，境界オブジェクトに対する追加処

る．空間データの高速な分析は，ビジネスの成長や企業のロケー

理により，全体的なクエリ性能が低下する．

ションインテリジェンスには不可欠であり，ビッグデータ社会を

上記の課題を解決するために，データ分布を考慮した様々な空支えるための必要要件である．膨大な空間データに対する複雑間データパーティショニング手法が提案されている [15, 18]．しな空間分析の必要性が高まり， Spark や Hadoop などの並列分

かし，データセットやクエリワークロードに応じて，最適なパー

散処理コンピューティング技術を拡張した Apache Sedona [25]，

ティショニング手法は異なる．そこで，データセットの一部を用

SpatialHadoop [3], Simba [24]などの空間データ処理に特化させいてデータ分布などの特徴を分析し，既存手法の中から適切なもた並列分散フレームワークが開発されている．空間データ処理にのを自動的に選択する方法が提案されている [21]．ただ，既存の用いられる空間クエリは多種多様であり，最も基本的な処理と空間データパーティショニング手法は汎用的な利用を目的としして Range Query および kNN Query は広く利用されている．

て設計されたものであり，入力されたデータやクエリに対して最さらに，これらのクエリを対象として効率化を図る研究も多く，

適とはいえない．実際は，データ分布やクエリの特性に合わせて大規模な空間データに対するより高速な処理が必要とされてい特化させた方がクエリ性能が高いことは容易に想像できる．一方で，データベース技術に機械学習を応用する研究が盛んに行われる [5, 16]．
並列分散処理システムでは，計算処理をスケールアウトできるており，データベースやクエリに応じて最適化を図る学習型の手ようにマシン間でデータを分割する必要があり，データパーティ法が多く提案されている．クエリの高速化という観点では，デーショニングが用いられる [12]．データパーティショニングは，デタパーティショニングだけでなく，インデックス技術などにも広ータの特性や利用目的に合わせてデータ全体をパーティション

く機械学習技術が応用されている [1, 2, 7, 9, 10, 14, 16, 16, 22]．しと呼ばれる小さな単位に分割し，各マシンにパーティションを割

かし，筆者らの知る限りでは空間データパーティショニングを学習する研究は存在しない．

1 学生会員そこで，本稿では深層強化学習を用いた空間データパーティシ

大阪大学大学院情報科学研究科

ョニング手法を提案する．まず，空間データパーティショニング

hori.keizo@ist.osaka-u.ac.jp
2 正会員

大阪大学大学院情報科学研究科を新たに強化学習問題として定式化する．データ分布やクエリワ

sasaki@ist.osaka-u.ac.jp
3 正会員

ークロードの情報を状態に含め，矩形パーティションを構築する

大阪大学大学院情報科学研究科

ような行動を定義する．さらに，クエリ実行時間を報酬として与amagata.daichi@ist.osaka-u.ac.jp
4 正会員

大阪大学大学院情報科学研究科

えることで，クエリ実行時間を最小化するような学習設計を行

onizuka@ist.osaka-u.ac.jp

1

日本データベース学会和文論文誌
一般論文

Vol. 20-J, Article No. 11, 2022年 3月
トを用意することで，最適なパーティショニングを自動的に構築う．学習には，Deep Q-Network (DQN) アルゴリズムを用いた深層強化学習 (DRL) を採用することで，複雑な問題設定におけする. [1] ではパーティショニングタスクを強化学習タスクとしる膨大な状態数や行動パターンを処理する． DRL エージェントて定式化し，ワークロードに適切な垂直分割スキームを発見する

はデータセットとクエリワークロードの両方に適応するように行

ように深層強化学習を行うことで，いくつかの最先端のアルゴリ

動ルールを学習し，入力に応じた最適なパーティションを構築す

ズムを上回る性能を達成している．インデックスへの応用では，ることで空間クエリの高速化を図る．予備実験では，既存の空間[9] においてB-Treeなどの従来のデータベースインデックスを一パーティショニング手法を比較し，分析の結果から提案手法の必次元キーに対応するデータ格納位置を予測するニューラルネット

要性を示した．評価実験では，提案手法を用いた空間パーティシ

ワークモデルに置き換えることで，大幅な検索速度の向上と省メ

ョニングの学習を行うことで一部のクエリに対するクエリ実行時

モリを達成している．それ以降，学習型インデックスを空間デー間を短縮した．

タのような二次元，さらには多次元データに拡張する研究が取り本稿の構成は以下の通りである． 2 章にて関連研究について説組まれている． LISA [10] は，ディスクベースの学習型空間イン

明し，3 章にて事前知識について説明する． 4 章にて深層強化学

デックスであり，範囲クエリ，最近傍クエリ，挿入・削除をサポ

習における空間パーティショニング問題を定義し，5 章にて提案ートする． ZM-index [16, 22] では，Z-order 曲線を用いた多次手法について説明する． 6 章にて実験について述べ，7 章で本稿元データの1次元空間へのマッピングと [9] の Recursive-Modelをまとめる．

Indexes (RMI) を組み合わせている．多くの学習型の多次元イ
ンデックスでは，特定のデータセットやワークロードに対してイ2 関連研究

ンデックスを自動的に最適化するというアイデアが導入されてい関連研究として既存の空間パーティショニング手法とデータベ

る． Kraskaら [2] は Flood [14] を拡張し，実際のアプリケーシ
ョンでよく見られる相関のあるデータや歪んだクエリワークロー

ース技術への機械学習の応用研究について説明する．

2.1

空間データパーティショニングドを新たに考慮することで，これまでの学習型の多次元インデッ

空間データパーティショニング手法には，データ分布を考慮

クス以上の性能を達成している．

した様々なアルゴリズムがある．最も基本的なアルゴリズムは

しかしながら，空間データパーティショニングを対象とする研Uniform Grids と呼ばれ，二次元空間に存在するデータに対し究は少ない．深層強化学習を用いて適切な空間データパーティシて均一サイズのグリッドセルを用いて分割するため，一様な分ョニング手法を選択するなどの応用 [21] がされているが，これ布を持つデータに適している．しかし，多くの場合データ分布

までのところ空間パーティショニングそのものを学習するよう手には偏りが存在するため, Uniform Grids では効果的な分割は期法は存在しない．

待できない．そこで，データ分布に合わせて不均一なサイズの3 事前知識グリッドセルを用いて分割する方法として，R-Tree [6]，Quad-

Tree [4]，KDB-Tree [17] などがある．例えば，R-Treeは位置の提案手法では，深層強化学習の学習アルゴリズムである Deep

近いデータ群の最小外接矩形を階層的に入れ子になるように二次

Q-Network (DQN) を用いる． 以下では， 強化学習の理論と元空間に分割し，Quad-Treeは指定したデータ数に至るまで二次

DQN の関連技術を説明する．

元空間を再帰的に四つの領域に分割する． R-Tree，Quad-Tree，

3.1

強化学習

KDB-Tree のような木構造を用いたパーティショニング手法で強化学習では，エージェントが環境との相互作用を繰り返すこは，葉のノードに割り当てられたデータ群をパーティションとしとで，教師データとなる情報を自律的に獲得しながら最適な行動て扱う． Quad-treeやKDB-treeは空間全体を分割していく一方

ルールを導き出すものである [8]．相互作用とは，エージェント

で， R-Treeはデータを集約しながらパーティションを作成する

が時刻 t において，状態 st を観測し，行動 a ∈ A を選択するこため，どのパーティションにも当てはまらない空間が生成がされとで，新しい状態 st+1 に遷移し，報酬 rt を得ることをいう．こる．どのパーティションにも当てはまらない空間はオーバーフロ

れを s0 上で a1 を選択しながら，状態 sn が特定の条件を満たーパーティションとして保持される．これらの手法では，葉のノすまで繰り返す．ここで，ある状態において行動を選択し一つ先ードの数を制御することにより，パーティション数を制御するこの状態に進める処理をステップ，さらに特定の条件を満たすまでとが可能である．これらの手法では，データが多く集まる空間はステップを繰り返す一連の処理をエピソードと呼ぶ. このとき，より細かく分割され，パーティション間でのデータ数のばらつき

将来的により高い報酬を獲得するようにエージェントの行動ルーが抑えられる．

ルを最適化することが強化学習の課題である．

2.2

データベース技術への機械学習の応用

3.2

データパーティショニングやインデックスといったクエリの高Q-Learning

Q-Learning は強化学習手法の一つである [23]．状態 s において可能な行動 a ∈ A の中から行動価値関数 (Q 関数) の値が最速化を図るデータベース技術に機械学習を応用する多くの研究がある．データパーティショニングへの応用として， [7] は深層も高い行動を選択するように学習を行う．この値は Q 値と呼ば強化学習を用いてOLAP スタイルのワークロードに向けたハッれ，ある状態とその状態下においてエージェントが可能な行動をシュパーティショニングを学習する．異なるデータベーススキー

対にした行動ルールに対する有効性を示す．エージェントは行動

マやワークロードの変化に対応できるように複数のエージェン

毎に Q 値の更新を行い，状態 st でエージェントが行動 a を選

2

日本データベース学会和文論文誌
一般論文

Vol. 20-J, Article No. 11, 2022年 3月

択し，状態が st+1 に遷移するとき，Q 関数は以下のように更新される．

Q(st , a) ← Q(st , a)+α[rt+1 +γ max Q(st+1 , a)−Q(st , a)] (1)a∈A

ここで，α と γ はそれぞれ学習率と割引率である．α(0 ≤ α ≤ 1)
は現在の Q 値に反映させる更新量の大きさを決定する． γ(0 ≤γ ≤ 1) は 1 に近づけると将来の報酬まで考慮し，0 に近づければ目先の即時的な報酬を優先させることになる．現在の状態のQ 値を次の状態で最大の Q 値との差分をもとに更新を行うこと
で，高い報酬を得た場合にはその状態に到達可能な過去の状態にもその報酬が伝播される．この差分を無くすように更新を繰り返すことで最適な状態遷移が学習される．

3.3

Deep Q-Network

図1: 空間データパーティショニング学習環境の例

Deep Q-Network (DQN)とは， Q 関数をパラメータ θ を持
つニューラルネットワークで近似し強化学習を行う手法である [13]． Q(s, a) はすベての状態とすべての行動の組み合わせで3.3.3

定義する必要がある．しかし，状態 s が非常に多くなるような問題設定では，すべての組み合わせを定義することが不可能であ前のパラメータ θ − に依存する．しかし， Q 関数が更新される

る．そこで，深層学習の技術を導入することにより高次元な状態度に教師データが変動すると，学習が安定しないという問題が空間や行動空間を持つ問題に対しても強化学習を適用することを発生する． そこで， Fixed Target Q-Network では， main Q-

可能とした．

Network とは別に Q(st+1 , a; θ− ) の値を計算するための target

DQN において損失関数 L は以下の式で定義される．
L=X(rt + γ max Q(st+1 , a; θ− ) − Q(st , a; θ))2B

a∈A

Fixed Target Q-Network

式 (2) において教師データとなる Q(st+1 , a; θ − ) の値は一つ

Q-Network を用意する． target Q-Network ではパラメータ θ−
を一定期間更新させずに教師データを固定させることで学習を安(2)定させる．そして，一定期間ごとに target Q-Network と main

Q-Network を同期させる.

rt + γ max Q(st+1 , a; θ− ) の部分は Q(st , a; θ) に対する教師デ

しかし，target Q-Network の更新間隔が大きいほど，ステッータの役割を果たしているため target と呼ばれる． B はエプが進んだ際に教師データに含まれる誤差が大きくなることで学

ピソードデータであり，エージェントの試行錯誤の結果の組

習精度に影響を与える．そのため， [19] などで提案されている(st , at , st+1 , rt ) の集合により表現される． DQN を用いた学習

アルゴリズムでは τ により更新の度合いを調整し，以下のようでは学習精度を向上させるための様々な工夫が取り入れられておに緩やかな更新をより小さな間隔で繰り替えすことによりパラメ

り，以下では代表的な 3 つを説明する．

ータの安定性が向上する．

3.3.1 ϵ-greedyθ′ ← (1 − τ )θ′ + τ θ

ϵ-greedy は強化学習において広く利用される行動選択手法で(3)ある．エピソードデータはある Q 関数にしたがったエージェン
トの行動歴である．学習初期では Q 関数を適当に初期化しエピ

4 問題定義ソードデータを蓄積するが，偶然に特定の行動を取りやすい初期

本章では空間データパーティショニングを新たに強化学習問

Q 関数であった場合には同じ行動を繰り返し，エピソードデータが偏るため局所解に陥いるという問題がある．そこで，ϵ-greedy

題として設計する．以下では，本強化学習問題における環境，状では確率 ϵ で学習者が完全にランダムな行動を選択し，あらゆる態，行動，報酬をそれぞれ定義する．状態の定義には，入力とし可能性の探索を可能とすることで問題に対処する．

て与えられるデータセットとクエリワークロードに対して，デー

3.3.2

タ分布やワークロードに含まれている各種クエリの情報が明らか

Experience Replay

学習に用いるエピソードデータはエージェントが蓄積した時系であるものとする．また，本稿では学習および実験において空間

列データである．しかし，ステップ毎にそのエピソードデータをデータ用の並列分散処理フレームである Apache Sedona*1 を利用いて Q 関数の更新を行う場合，時間的にデータ間の相関が高用する． Sedona における空間パーティショニングでは矩形パー

く上手く学習できないという問題がある．これは，類似するエティションをサポートしているため，本稿では矩形パーティショ

ピソードデータで更新を行うことで局所解に陥りやすいためでンを生成するように行動を設計する．図 1 には学習環境と状態ある．そこで，Experience replay では観測した (st , at , st+1 , rt )遷移の例を示す．

をメモリに蓄積し，学習時にメモリからランダムにデータを取り出して学習することで問題に対処する．

*1 https://sedona.apache.org/.

3

日本データベース学会和文論文誌
一般論文

Vol. 20-J, Article No. 11, 2022年 3月

定義 1 (Environment) エージェントが配置される強化学習環
境として，図 1 の左上のように二次元空間上にデータ全体を覆う一つのマップを初期状態として形成する．マップは均一な大きさのグリッドセルに分割されており，エージェントは各グリッド
線上に新たな境界線を追加していくことでパーティションを構築していく．
定義 2 (State) 状態 S として s(P ) と s(Q) の二種類の状態を定義する． s(P ) ではグリッドセルの状態を以下のように定義し，全てのグリッドセルに対して適用する．

sij (P ) = (h, v, pdata , prange , pknn )(4)
図2: 提案概要

i, j はグリッドセルの左上座標を指定する． h および v は各座標においてそれぞれ水平と垂直の境界線の有無を表す 0 か 1 である． pdata は全データに対してグリッドセル内に存在するレコード数の割合である． prange および pknn はクエリワークロード
内の Range Query と kNN Query のそれぞれで指定される範囲
および位置に各グリッドセルが含まれている確率である．学習中
は，pdata ，prange ，pknn の値は固定である．

s(Q)ではクエリワークロードの状態を以下のように定義する．
s(Q) = (f1 , f2 , f3 , ..., fn )(5)

fn (0 ≤ fn ≤ 1) はワークロードに含まれる n 種類のクエリに対
図3: DQN ニューラルネットワーク

して，各クエリが含まれる頻度の割合である．
定義 3 (Action) 一つ一つの行動 a ∈ A はある座標点から新たな境界線を追加することを指す．そこで，各座標から取り得る行

2 には提案概要として学習全体の流れを示す．指定されたデータ

動を以下のように定義する．

セット，クエリワークロード，マシン台数の情報を含めた状態を学習モデルに入力する．学習モデルはパーティションを構築する

a = (i, j, d)(6)

ように行動を繰り返しながら行動価値を学習し，入力に対してi と j は行動の開始点として座標を指定する． d は追加する境界

最適なパーティションを推論することが目的である．以下では，5.1節で提案手法の学習方針について説明する．続いて，5.2節で線の向きを指定し，右向きであれば 0，下向きであれば 1 とす

学習手順について説明する．

る．

5.1

学習方針

定義 4 (Reward) エピソード終了時におけるパーティション

データセットとクエリワークロードの両方に最適な空間パーテ

P に対して，入力したクエリワークロードからサンプルされたィショニングを学習するために，4 章ではそれらの情報を状態のクエリ q ∈ Q の実際の実行時間 C(P, q) を測定する．ただし，一部として定義した．高精度な学習を行うためには初期マップにエージェントは報酬の最大化を目標とするため，報酬の定義にはおいてグリッドセルをより細かく形成しておく必要がある．しかし，状態および行動の定義よりグリッドセル数が多くなるほど，負の符号を与える．

状態空間および行動空間が膨大になる．そこで，DQN を用いた

r=−

X

C(P, q)

深層強化学習を採用し，学習に用いるニューラルネットワークモ(7)

デルのイメージを図 3 に示す．ニューラルネットワークの入力次

q∈Q元，出力次元はそれぞれ状態空間と行動空間の大きさとなる．た問題定義 学習における目標は，入力されたデータセットやクエ

だし，二つの状態 s(P ) と s(Q) を使用するため，DQN には 2

リワークロードに対して，クエリ実行時間を最小化するようなパ

種類の入力を与えることを想定する．

ーティショニングを見つけることである．

しかしながら，本問題設定においては膨大な状態空間および行
動空間による学習時間の増大が懸念される．特に学習初期では境5 提案手法界線をランダム的に追加するだけでパーティションを構築するよ

本章では，4 章で設計した強化学習問題をもとに DQN アルゴ

うな行動を選択することが困難である．そこで，学習の収束性を

リズムを用いた空間データパーティショニングの学習を行う．図高めることを目的として，行動 a は境界線が存在する座標，す4日本データベース学会和文論文誌
一般論文

Vol. 20-J, Article No. 11, 2022年 3月

なわち状態 s(P ) において h もしくは v が 1 である座標からのみ行動可能とし，さらに既に境界線が存在する方向への行動は選

Algorithm 1 Learning using DQNInput: Dataset D, Query workload Q, The number of ma-

択できないように制限を与える．これにより，各ステップで新たchines M

なパーティションが生成される．

1: Randomly initialize main Q-Network Qθ

また，過剰なパーティションの生成は空間クエリにおける処理

2: Randomly initialize target Q-Network Qθ′

効率を悪化させるため，本稿ではパーティション数はマシン台

3: for e = 1, · · · , emax do

数の 2 倍という設定で学習を行う．このとき，main Q-Network

4:▷ Episodes

for t = 1, · · · , tmax do▷ Steps in Episodeの更新は一定のステップ間隔で式 (2) の損失関数を用いた学習を

5:

Initialize map: Reset to state s0

行う．また，target Q-Network の更新は main Q-Network の更

6:

partitions ← 1

新よりも細かなステップ間隔で，式 (3) の方法を用いた更新を行

7:

Choose at = arg max Qθ (st , a) with probabilitya∈A

う．

1−ϵ, otherwise random action

報酬には現在のパーティションにおけるクエリ実行時間を測定する．ここで，本問題設定では最終的なパーティションの報酬値を最大化させることが目標である．しかし，行動毎に生成されたパーティションに対する報酬を測定した場合，最終的なパーティ
ションではなく，ステップ毎の各状態における最適な行動の価値が高くなるように学習が進む．すなわち，ステップ毎に最適な行動を取ることが最終的なパーティションにとって良い行動ではない可能性がある．そこで，報酬は各エピソードにおいて行動を繰り返した後，指定のパーティション数に達したときに一度だけク

8:Execute action at

9:

Update state st

10:

if partitions ≥ 2 ∗ M then11:

Distribute partitions P to machines

12:
13:

Compute reward:P
r = − q∈Q C(P, q)

14:

Update best partitions Pbest

15:

for c = 1, · · · , partitions do

エリの実行時間を測定することで求める．そこで得られた報酬値

end for17:をこれまでにとった行動全てに対して与える．さらに，過去に同

break

18:

じ状態遷移をした経験がメモリに存在する場合，報酬値の高い方を保持するように更新を行う．
提案する DQN モデルでは，エージェントが行動を繰り返す
ことで，あらゆるパーティションの状態において取り得る行動の価値を学習し経験を蓄積する．これにより，各グリッドセルに含19:

end if20:

if Step interval of train then21:

Sample minibatch (si , ai , ri , si+1 ) from B

22:

Train main Q-Network with loss:Pb
L =i=1 (ri + γ arg max Qθ ′ (si+1 , a) −23:

まれるレコード数や各種クエリの割合などに適応した行動ルール

a∈AQθ (si , ai ))2が形成されることで，入力したデータセットとクエリワークロー

Decrease ϵ24:ドに最適なパーティションの生成を可能とする．

5.2

Store transition (sc , ac , r, sc+1 ) in B

16:

学習手順

Algorithm 1 に DQN アルゴリズムに基づく提案手法の学習

25:

end if26:

Update weights of target Q-Network:27:

手順を示す．まず，与えられたデータセットおよびクエリワーク

28:

ロードから，マップを初期化し状態を取得する (5行目)．次に，

θ′ ← (1 − τ )θ′ + τ θ
end for

29: end for

ϵ-greedy 法による行動選択を繰り返しながら状態を更新する

Output:Coordinate of partitions Pbest(7–9行目)．エージェントは指定数のパーティションが構築されるまで行動を繰り返し (10行目)，s(P ) の境界線の有無からパーティション P を生成してマシンに割り当てる (11行目)．その後，

6 実験

クエリワークロードからサンプルしたクエリに対して実行時間

C(P, q) を測定し，報酬 r を求める (12–13行目)．ここで，ステ

本章では，予備実験として既存の空間パーティショニング手法

ップ毎の経験 (sc , ac , r, sc+1 ) をメモリに保持する (15–17行目)．

の性能比較を行う．さらに，提案手法による空間クエリの高速化

また，一定間隔ごとにメモリに保存した経験 (si , ai , ri , si+1 ) かについて評価実験を行う．

らサンプルしたデータでmain Q-Networkの学習を行う(20–25行

6.1

データセット目)．その後，ϵ を減衰させる (24行目)． target Q-Networkのパ実験では [15] で公開されている OpenStreetMap (OSM) デー

ラメータの更新は定期的に行う (26–27行目)．ここまでを 1 エピ

タセットを利用する．データセットは， Nodes (Point)， Roads

ソードとし，指定したエピソード数 emax だけ繰り返す．最終的(LineString)，Buildings (Polygon), Rectangles (Rectangle) かな DQN モデルの出力は，学習中に保持しておいた報酬が最大ら構成されている． Rectangles は Polygons データから矩形デとなるパーティションの矩形座標の集合 Pbest である．

ータを抽出して作成されている．予備実験には OSM データセッ
トから一部をサンプルし，表 1 に使用したデータセットの詳細を示す．以降では，各データセットをジオメトリタイプ別に Point,5日本データベース学会和文論文誌
一般論文

Vol. 20-J, Article No. 11, 2022年 3月

表2: クエリワークロード

表1: データセット
データセットジオメトリタイプ

レコード数

Quantity

Range

kNN

Distance

OSM Nodes

Point

10 million

10

0.4

0.4

0.2

OSM Roads

LineString

10 million

OSM Polygons

Polygon10 million

OSM Rectangles

Rectangle

10 million

表3: 学習設定

LineString, Polygon, Rectangle と表記する．
6.2

実験環境

並列分散処理環境には Intel Celeron G4930T CPU @ 3.00

GHz，32 GB の RAM を搭載したコンピュータ 9 台を利用し，Spark クラスタとして 1 台のマスターノードと 8 台のスレーブ
ノードを配置する．

6.3
6.3.1

予備実験
実験設定

予備実験では既存の空間パーティショニング手法から Uniform

Grids， R-Tree， Quad-Tree， KDB-Tree の 4 種類のパーティ

Parameter

Value

Learning rate

0.001

τ (Target Q-Network update)

0.001

Optimizer

Adam

Experience replay buffer size

3000

Batch size for experience replay

32

Epsilon decay

0.9997

Episode2000

Network layout(600,300)γ (Reward discount)

0.97

Machines

8

Grid size

10 × 20

ショニング手法を用いる． それぞれの手法に対して， Range

Query，kNN Query，Distance Join，Spatial Join の 4 種類の種類のクエリが含まれるワークロードに対する実行時間を測定す

クエリを実行する．なお， Spatial Join は 2 種類のデータ間でる．なお，測定誤差の軽減のために各クエリに対して 5 回の試行包含されるものを結合する処理である．手法毎に各クエリの 10の平均時間を用いる．比較手法には， Uniform Grids， R-Tree，回の実行時間を測定し，その平均時間を用いて評価する．なお，

Quad-Tree，KDB-Tree を用いて，学習設定と同じく 16 個のパ

Apache Sedona では Range Query および kNN Query においーティションを生成する．

て，範囲を持つようなジオメトリタイプに対する空間データパー

ただし，学習および実験評価にはポイントデータセットから

ティショニングがサポートされていないため，ポイントデータの100 万件のみをサンプルした同一のデータセットを利用する．そみを用いて実験を行う．

のため，ワークロードに含まれるクエリについてもポイントデー

実験結果

タのみを対象とする．また，学習時の報酬測定で用いるクエリに

6.3.2

本項では予備実験の結果について述べる．クエリ毎の比較結はワークロード全体を用いる．クエリワークロードに含まれる果を図 4–7 に示す．図 4 の Range Queryでは，全ての選択割合

クエリの総数と各クエリの割合を表 2 に示す．ここで， Range

に対して Quad-Tree のクエリ実行時間が小さい．図 5 の kNN

Query における範囲はランダムに指定し, kNN Query の近傍数

Query でも，全ての近傍数 k に対して Quad-Tree が優れていは 1, 5, 10, 30, 50, 100, 300, 500, 1000，Distance Join の距離

る． kNN Query の性能に関しては，手法毎に 10 回のクエリ(m) は 10, 50, 100 からランダムに選択する．また，学習に用い実行で指定される位置のランダム性も影響していると考えられたハイパーパラメータを表 3 に示す．

る．しかし，ランダム性によるクエリの偏りのように，実際の分

6.4.2 実験結果

析においても目的に応じて偏りが生じることが予想できる．そ

本項では評価実験の結果について述べる．各手法で構築されたのため，より高速なクエリ処理の実現にはパーティションの最パーティションを図 8 に示す．ここで，緑矩形は Range Query

適化が必要である．図 6 の Distance Join では全体的に Quad-で指定される範囲，青点は kNN Query で指定される位置を示

Tree と KDB-Tree のクエリ実行時間が小さく，特に LineString

している． 各手法で異なるパーティションが構築されており，では KDB-Tree， Polygon では Quad-Tree が優れている． 図

R-Tree， Quad-Tree， KDB-Tree ではデータ数が多いところほ

7 の Spatial Join では Distance Join と同様に KDB-Tree とど細かく分割されている．一方で，提案手法や Uniform Grids

Quad-Tree のクエリ実行時間が小さい．

ではパーティション間でデータ数に大きく偏りがある．

実験結果から，データセットやクエリごとに適切なパーティシ

各手法のクエリワークロード実行時間の比較結果を表 4 に示ョニング手法が異なることがわかる．そのため，学習によるパー

す．これは，クエリワークロードに含まれる各クエリの実行時間

ティションの最適化を行う提案手法が有効であると考えられる．

の総和および全体の合計時間を示す．Range Query および kNN

6.4

評価実験

Query に対する実行時間は提案手法が最短であった． しかし，6.4.1 実験設定

クエリワークロード全体での実行時間は Distance Join の占め評価実験では，提案手法のクエリの高速化について実験を行る割合が大きく， Quad-Tree が最も優れる結果となった．本実

う．評価には Range Query，kNN Query，Distance Join の 3

験において設定したパーティション数はデータセットに対して最6日本データベース学会和文論文誌
一般論文

0.2
0.1
0
0.0001

0.6

250

0.5
0.4
0.3

図4: Range Query

50

60

200
150
100
50

0.2
0.01
1
10
Selection Ratio [%]70

Uniform Grids
R-TreeQuad-TreeKDB-TreeQuery Runtime [sec]0.3

Uniform Grids
R-TreeQuad-TreeKDB-Tree

0.7

Query Runtime [sec]

0.4

300

0.8

Uniform Grids
R-TreeQuad-TreeKDB-Tree

0.5

Query Runtime [sec]Query Runtime [sec]0.6

Vol. 20-J, Article No. 11, 2022年 3月

1

10

50
k

100

500

適な値ではない．そのため，Range Query や kNN Query に対

50
40
30
20
10

0

0
Point

LineString

PolygonRectangle

図6: Distance Join

図5: kNN Query

Uniform Grids
R-TreeQuad-TreeKDB-TreePointPointPoint- LineString- LineStringLineString Polygon Rectangle Polygon Rectangle

図7: Spatial Join

参考文献

して，提案手法のような直感的には非効果的に見えるパーティシ[1] Gabriel Campero Durand, Rufat Piriyev, Marcus Pinnecke,David Broneske, Balasubramanian Gurumurthy, and Gunter
Saake. Automated vertical partitioning with deep reinforcement learning. The New Trends in Databases and Information
Systems, pages 126–134, 2019.
[2] Jialin Ding, Vikram Nathan, Mohammad Alizadeh, and Tim
Kraska. Tsunami: A learned multi-dimensional index for correlated data and skewed workloads. The Proceedings of the
VLDB Endowment, 14(2):74–86, 2020.
[3] Ahmed Eldawy and Mohamed Mokbel. SpatialHadoop: A
MapReduce framework for spatial data. In Proceedings of International Conference on Data Engineering, pages 1352–1363,
2015.
[4] R. A. Finkel and J. L. Bentley. Quad trees a data structure for
retrieval on composite keys. The Acta Informatica, 4(1):1–9,
1974.
[5] Tu Gu, Kaiyu Feng, Gao Cong, Cheng Long, Zhaohai Wang,and Sheng Wang. The rlr-tree: A reinforcement learning based
r-tree for spatial data. ArXiv, 2021.
[6] Antonin Guttman. R-Trees: A dynamic index structure forspatial searching. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 47–57,
1984.
[7] Benjamin Hilprecht, Carsten Binnig, and Uwe Röhm. Learninga partitioning advisor for cloud databases. In Proceedings of
the ACM SIGMOD International Conference on Managementof Data, pages 143–157, 2020.
[8] Leslie Pack Kaelbling, Michael L Littman, and Andrew W
Moore. Reinforcement learning: A survey. Journal of artificial intelligence research, 4:237–285, 1996.
[9] Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis
Polyzotis. The case for learned index structures. In Proceedingsof the International Conference on Management of Data, pages
489–504, 2018.
[10] Pengfei Li, Hua Lu, Qian Zheng, Long Yang, and Gang Pan.
LISA: A learned index structure for spatial data. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 2119–2133, 2020.
[11] Chengwen Liu and Hao Chen. A hash partition strategy for
distributed query processing. In Proceedings of International
Conference on Extending Database Technology, pages 371–387.
Springer, 1996.
[12] Mohammad Mahmud, Joshua Huang, Salman Salloum, Tamer
Emara, and Kuanishbay Sadatdiynov. A survey of data partitioning and sampling methods to support big data analysis.
Big Data Mining and Analytics, 3:85–101, 2020.
[13] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex
Graves, Ioannis Antonoglou, Daan Wierstra, and Martin A.
Riedmiller. Playing atari with deep reinforcement learning.
arXiv, 2013.
[14] Vikram Nathan, Jialin Ding, Mohammad Alizadeh, and Tim
Kraska. Learning multi-dimensional indexes. In Proceedings of
the ACM SIGMOD International Conference on Managementof Data, pages 985–1000, 2020.
[15] Varun Pandey, Andreas Kipf, Thomas Neumann, and Alfons
Kemper. How good are modern spatial analytics systems?
The Proceedings of the VLDB Endowment, 11(11):1661–1673,

ョンも実は効果的に作用している可能性は大きく，学習を用いるからこそ得られたパーティションであると考えられる．一方で，Distance Join ではパーティション間のデータ数の均等性が大きく影響しており，特に Quad-Tree や KDB-Tree ではおおよそ均等に分割されているのに対し，提案手法ではデータ数の偏りが大きく短縮には至らなかった．これは，データ数を均等に分割するような精密なパーティションの形成には学習設定のエピソード
数やグリッドサイズでは不十分であったと考えられる．また，各マシンへのパーティションの割り当ては Spark の仕様としてランダムに制御されるため，学習時および評価時にはその組み合わせによって生じるマシン間での通信コストの違いによる性能の誤差も含まれていると考えられる．

7 おわりに本稿では, 深層強化学習を用いた空間データパーティショニン
グ手法を提案した．汎用的な利用のために設計されている既存の空間パーティショニング手法に対して，提案手法ではデータ分布
やクエリの特性に合わせてパーティショニングを学習し，最適なパーティションを生成することで空間クエリの高速化を図る．評
価実験では，提案手法による空間パーティショニングが一部クエリに対して実行時間を短縮することを示した．
今後の展望として，より効果的な設計および学習を行うことでクエリの高速化の実現を目指す．そのために，行動パターンの追加などの新たなパーティション構築方法の考案に取り組む．さらに，現在の学習ではポイントデータのみを状態に与えており，境界オブジェクトに対する学習が不十分であるため，他のジオメト
リタイプの追加が必要である．ただし，報酬計算時のクエリ実行にはジオメトリタイプやクエリの種類別に RDD の生成が必要となり，学習時間の増加が懸念される．そこで，実際にクエリ実
行時間を測定せずにコストを近似する仕組みを追加することで収束性の向上を図る必要がある．また，パーティション数は処理効率にも影響を与えるが，現在はパーティション数を手動で設定しているため，学習により自動的に決定することを今後の課題とする．

謝辞
本研究はJSPS科研費 JP20H00584 の支援によって行われた．
ここに記して謝意を表す．

7

日本データベース学会和文論文誌
一般論文

Vol. 20-J, Article No. 11, 2022年 3月(a) Uniform Grids(b) R-Tree(c) Quad-Tree(d) KDB-Tree(e) Proposal

図8: パーティションの比較

表4: クエリワークロード実行時間 (sec)Range Query

Uniform Grids

R-treeQuad-TreeKDB-Tree

Proposal

1.399

1.105

0.533

1.112

0.485

kNN Query

1.605

1.325

0.721

1.575

0.642

Distance Join

42.47

27.98

8.01

21.01

36.93

Total

45.47

30.41

9.26

23.70

38.05

ence on Advances in Geographic Information Systems, pages
545–548, 2014.
[21] Tin Vu, Alberto Belussi, Sara Migliorini, and Ahmed Eldway.
Using deep learning for big spatial data partitioning. The ACM
Transactions on Spatial Algorithms and Systems, 7(1), 2020.
[22] Haixin Wang, Xiaoyi Fu, Jianliang Xu, and Hua Lu. Learned
index for spatial queries. In Proceeding of IEEE International
Conference on Mobile Data Management, pages 569–574, 2019.
[23] Christopher JCH Watkins and Peter Dayan. Technical note:
Q-learning. The Machine Learning, 8:279–292, 2004.
[24] Dong Xie, Feifei Li, Bin Yao, Gefei Li, Liang Zhou, and Minyi
Guo. Simba: Efficient in-memory spatial analytics. In Proceedings of the ACM SIGMOD International Conference on
Management of Data, pages 1071–1085, 2016.
[25] Jia Yu, Zongsi Zhang, and Mohamed Sarwat. Spatial data
management in Apache Spark: The GeoSpark perspective andbeyond. The Geoinformatica, 23(1):37–78, 2019.

2018.
[16] Jianzhong Qi, Guanli Liu, Christian S. Jensen, and Lars Kulik.
Effectively learning spatial indices. The Proceedings of the
VLDB Endowment, 13(12):2341–2354, 2020.
[17] John T. Robinson. The K-D-B-Tree: A search structure forlarge multidimensional dynamic indexes. In Proceedings of the
ACM SIGMOD International Conference on Management of
Data, pages 10–18, 1981.
[18] Yuya Sasaki. A survey on iot big data analytic systems: Current and future. IEEE Internet of Things Journal, 9(2):1024–
1036, 2021.
[19] David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan
Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In Proceedings of the International Conference
on Machine Learning, pages 387–395, 2014.
[20] Hoang Vo, Ablimit Aji, and Fusheng Wang. SATO: A spatial
data partitioning framework for scalable query processing. In
Proceedings of the ACM SIGSPATIAL International Confer-8