DEIM Forum 2019 H4-5

空間データベースにおけるインタラクティブオブジェクトの高速検索
天方 大地†

原隆浩†† 大阪大学大学院情報科学研究科 〒 565–0871 大阪府吹田市山田丘 1-5
E-mail: †{amagata.daichi,hara}@ist.osaka-u.ac.jp
あらまし 本稿では，空間データベースにおける新たなクエリである MIO（Most Interactive Object）クエリを提案する．空間データベース内の各オブジェクトが複数の点で構成されるものとする．距離の閾値が与えられた時，異なるオブジェクト間で閾値以内の距離の点のペアが存在する場合，これらのオブジェクトはインタラクトしていると考える．MIO クエリは，最も多くのオブジェクトとインタラクトしているものを検索するクエリであり，ニューロサイ
エンスにおけるデータ分析等の応用が考えられる．ここで，MIO クエリ処理の効率化は自明ではない．単純なアルゴ
リズムはオブジェクト数の自乗の計算量が必要であり，理論的に高速なアルゴリズムではオブジェクト数の自乗のメ
モリ量が必要となってしまう．本稿では，BIGrid と呼ぶ新たなデータ構造を設計し，MIO クエリを効率的に処理する
アルゴリズムを提案する．実データおよび人工データを用いた実験の結果により，提案アルゴリズムの有用性を示す．
キーワード 空間データベース，MIO クエリ

1 はじめに
近年，空間クエリ処理によるデータ分析を可能とするため，
オブジェクトを空間点の集合でモデル化するアプリケーションが増えている．その一例として，ニューロサイエンス [1]，コン
ピュータビジョン [2]，および軌跡データベース [3] が挙げられる．より具体的には，計算機でニューロンデータを解析する際，

1 つのニューロンデータは，3 次元の点集合で表される [4]．本

図 1 3 次元点により表現されるニューロンデータ [4]

稿では，そのようなオブジェクトに注目し，MIO と呼ぶクエリを提案する．このクエリは，最も多くのオブジェクトとインことも知られている [10]．そのようなニューロンは脳の機能にタラクトしているものを検索する [5]．

おける重要な役割を果たしていると考えられており，そういっ

オブジェクト o を 3（または 2）次元の点集合とする（o =たニューロンの特定および解析が重要視されている [11]．本稿

P = {p1 , p2 , ..., p|P | }）．オブジェクト集合 O および距離の閾で考える問題（MIO クエリ）はそのようなニューロンを特定す

値 r が与えられた時，MIO クエリはオブジェクト o のスコア

るため，ニューロサイエンスシミュレーションに貢献できる．

を閾値以下の距離となる点のペアが存在する他のオブジェクトの数とする．つまり，任意の p ∈ o および o′ ∈ O\{o} に対し′′て，o′ が dist(p, p′ ) <= r となる p を持っている時，o は o とインタラクトしていると考え，o のスコアはインタラクトしているオブジェクトの数となる．MIO クエリは，スコアが最大のオブジェクトを検索する．MIO クエリ処理が利用される例

課題．上で挙げたような例では，ユーザは r を変えながら MIO
クエリ処理を実行することが考えられる．そのため，MIO ク
エリ処理の時間が長い場合，試行（シミューレーション）回数が限られてしまう．このような問題を避けるため，MIO クエリ
を高速に処理するアルゴリズムが必要となる．
この問題を解く素朴なアルゴリズムは，ネステッドループを

を以下で紹介する．

用いたものである．具体的には，オブジェクト o ∈ O が与え

例 1（ニューロサイエンス）．ニューロサイエンスシミュレー

られた時，全ての o′ ∈ O\{o}，p ∈ o，および p′ ∈ o′ に対しションでは，ニューロンの機能を計算機を用いて解明するため，て距離を計算し，これを全てのオブジェクトに対して実行す

図 1 のようにニューロンを 3 次元の点集合でモデル化すること

る．オブジェクト集合 O のサイズを n，各オブジェクトが持が近年多くなっている [6], [7]．ニューロン間はシナプスを通しつ点の数の平均を m とした時，このアルゴリズムの計算量はて信号伝達を行うが，シナプス結合は距離の近いニューロン間O(n2 m2 ) であり，スケーラビリティに欠ける．2. 2 節で紹介すで形成される傾向にあることが知られている．そこで，あるシるが，O(n log n) 時間で MIO クエリを処理できるオンライン

ミューレーションでは距離の閾値 r を指定し，距離 r 以内の点

アルゴリズムが存在する．しかし，このアルゴリズムは O(n2 )のペアを持つニューロン間にシナプス結合が存在すると想定すの空間計算量が生じるため，現実的に実行可能でない．また，る [1], [8], [9]．また，ネットワークにおけるハブのように，多く

これらのアルゴリズムの結果は時間計算量と空間計算量にトのニューロンとシナプス結合を形成するニューロンが存在する

レードオフ関係が存在することを示している．そのため，実践

的なメモリコストで高速に MIO クエリを処理するアルゴリズ

ネステッドループアルゴリズム．最も直感的なアプローチは空ムが望ましい．

間ジョイン（距離 r 以内となる全ての点のペアを検索）を用い貢献．以下に，本稿の貢献を要約する．

たアプローチである．ここで，本問題では全ての点のペアを検

本稿では，空間データベースにおける新たなクエリであ索する必要はない．例えば，τ (o) を計算するとして，o と o′ をる MIO（Most Interactive Object）クエリを提案する（2 章）．

比較すると想定する．今，p ∈ o かつ p′ ∈ o′ で dist(p, p′ ) <=r

筆者らの知る限り，本問題はこれまでに扱われていない．

と分かったとき，o と o′ の点のペアはこれ以上比較する必要はMIO クエリ処理を高速に実行するため，新たなデータ

ない．

構造である BIGrid を提案する（3 章）．このインデックスはオ

Algorithm 1: Nested loop (NL)

ンラインで構築されるため，一切の事前処理を必要としない．

Input: O, r

この BIGrid により，実践的なメモリコストで効率的にスコアの下界値，上界値，および正確な値を計算できる．



実データおよび人工データを用いた実験により，提案ア1o∗ ← ∅

2for ∀oi ∈ O do

3for ∀oj ∈ O such that j > i do

ルゴリズムの有効性を示す（4 章）．

4

f ←0

上記の内容に加えて，5 章で関連研究について述べ，6 章で本

5for ∀pki ∈ oi do

稿をまとめる．

6for ∀plj ∈ oj do
if dist(pki , plj ) <= r then7

2 事前準備
2. 1 問 題 定 義

8τ (oi ) ← τ (oi ) + 1, τ (oj ) ← τ (oj ) + 1

9

f ←1

10

break

オ ブ ジェク ト 集 合 を O と し ，|O| = n と す る ．あ る オ

11

if f = 1 then

ブジェクト oi ∈ O は，3 次元の点集合とする．すなわち，

12

break

|P |
oi = Pi = {p1i , ..., pi i } であり，各オブジェクトが持つ点の数∑は同じとは限らず，その平均を m とする（m = n|Pi | ）．また，

13

O はメモリで管理されており，更新は無いものと想定する．距離の閾値 r および 2 つのオブジェクト o, o′ ∈ O が与えられた

14
15

if τ (o∗ ) < τ (oi ) theno∗ ← oi
return o∗′′時，dist(p, p′ ) <= r となる p ∈ o および p ∈ o が存在すれば oと o′ にはインタラクションが存在していると考える．ここで，dist(p, p′ ) は p と p′ 間のユークリッド距離とする [1], [9]．MIO

アルゴリズム 1 にネステッドループアルゴリズム（NL）の詳細を示す．NL は一切の事前計算を必要としないが，τ (o) のクエリはこの概念からオブジェクトにスコアを与える．

計算量が O(nm2 ) であるため，全体の計算量が O(n2 m2 ) であ

定義 1（MIO クエリ）．オブジェクト集合 O および r > 0 とり，非常に計算コストが高い．

なる MIO クエリが与えられた時，oi ∈ O のスコア τ (oi ) は以

理論的アルゴリズム．次に，理論的に NL よりも高速なアルゴ

下のように定義される．

リズムについて考える．まず，以下の定理を紹介する．
定理 1．本問題において，オンライン実行時間が O(n log n) とτ (oi ) = |Oi |なるアルゴリズムが存在する．
ここで，証明．各オブジェクト o ∈ O に対して，他の全てのオブジェク′′

Oi = {oj | oj ∈ O\{oi }, ∃p ∈ oi , ∃p ∈ oj , dist(p, p ) <
= r}
(1)

トとの最近傍ペア間の距離を保存する配列 Ai を管理する（Aiである．MIO クエリは O においてスコアが最大となるオブジェが r 以内であれば，oj ∈ Oi であることが保証される．さらに，∗の大きさは n − 1 となる）．もし oi と oj 間の最近傍ペアの距離

クト o を出力する．

Ai は距離の昇順で管理されているとする．このとき，τ (oi ) は

本稿では，正確な解を高速に計算することを目的とする．

Ai に対して 2 分探索を実行することにより得られるため，そ2. 2 ネステッドループおよび理論的なアルゴリズム得られるため，全体の計算量は O(n log n) となる．

の計算量は O(log n) である．この操作を n 回実行すれば o∗ が□MIO クエリを高速に処理する難しさは，そのスコアリング

上のアルゴリズムは理論的に高速かつ任意の r に対応できる関数に由来する．オブジェクト oi のスコアは，他のオブジェクという利点はあるが，実践的ではない．まず，全てのオブジェク

トとの距離の関係によって決まる．また，図 1 に表されるよう

トが大きさ n − 1 の配列を持つため，メモリコストが O(n2 ) でに，オブジェクトの形は非常に複雑である．そのため，R 木のある．次に，oi と oj 間の最近傍ペアの計算には O(|Pi | log |Pj |)ように最小外接矩形を用いたインデックス構造は有用ではない．

時間かかる．この計算の償却時間は O(m log m) であるため，

本問題はこれまでに誰にも取り組まれていないため，ここでは他の全てのオブジェクトとの最近傍ペアの距離を計算するコス

ベースラインとなるアルゴリズムについて考える．

トは O(nm log m) となり，ソートに O(n log n) 時間必要である．つまり，Ai を構築するコストは O(n(m log m + log n)) でAlgorithm 2: Framework

あり，事前計算のコストは O(n2 (m log m + log n)) となる．

Input: O, r

要約すると，NL は計算効率が悪く，理論的アルゴリズムは1

Grid-Mapping(O, r)▷ build the BIGrid

メモリコストおよび事前計算コストが高い．データの利用が可

2

low ← Lower-bounding(O, r)τmax▷ lower-bound comp.

能となった際にできる限り早く分析を開始する必要があるアプ

3

low )
Ocand ← Upper-bounding(O, r, τmax

リケーションでは，高い事前計算コストが必要なアルゴリズム
4は用いられない [12]．そのため，事前計算が必要なく，実践的▷ upper-bound comp.

andpruningo∗ ← Verification(Ocand , r)

▷ exact score comp.

5 return o∗

なメモリコストで効率的に MIO クエリを処理するアルゴリズ
ムが必要となる．
スモールグリッド

3 MIO クエリ処理

セル
キー

セル
キー

転置リス 圧縮ビット
ト
集合

𝐾

𝐛 𝑐𝐾𝑠

𝐾

𝐼 𝑐𝐾𝑙

MIO クエリ処理の主なボトルネックはスコアの計算であり，

𝐛 𝑐𝐾𝑙

𝐛 𝑎𝑑𝑗 𝑐𝐾𝑙

…

…

…

…

…

要がある．つまり，課題となるのは，正確性を保ちつつ，いか圧縮ビット集合（union）…

実行時間を削減するためには，スコアの計算回数を削減する必

ラージグリッド

圧縮ビット
集合

𝐾′

𝐛 𝑐𝐾𝑠 ′𝐾′

𝐼 𝑐𝐾𝑙 ′

𝐛 𝑐𝐾𝑙 ′𝐛 𝑎𝑑𝑗 𝑐𝐾𝑙 ′に無駄なスコアの計算を枝刈りできるかという点になる．

図 2 BIGrid の構造

メインアイデア．無駄なスコアの計算を削減するため，スコア𝑟のバウンディングを導出する．このとき，スコアの下界値およ

𝐼 𝑐𝐾𝑙

び上界値を正確なスコアの計算よりも小さいコストで得る必要がある．これを実現するため，以下の事実を用いる．



スコアは集合のサイズである．



確実に距離が r 以内である，または r 以内になり得る点𝑟𝑟

例えば，点 p ∈ o に対して，距離が r 以内となる点をもつオブ

稿では，このアイデアに基づいてスコアのバウンディングを可能とするインデックス構造 BIGrid を設計する．このインデッ

𝑜𝑖+1

3
{𝑝𝑖+1
}

𝑜𝑖+2

4
{𝑝𝑖+2
}

𝐛 𝒂𝒅𝒋 𝑐𝐾𝑙 = 0 … 101 … 0

図 3 ラージグリッドのセル clK の概要

ジェクトを把握している時，そのオブジェクトをビット集合でる．同様のアプローチにより，τ (o) の上界値も計算できる．本{𝑝𝑖2 , 𝑝𝑖5 }𝐛 𝑐𝐾𝑙 = 1 … 0のペアは，グリッドを用いることにより容易に得られる．

管理すれば，ビット OR 演算により τ (o) の下界値が計算でき

𝑐𝐾𝑙

𝑜𝑖

次元グリッドを統合したインデックス構造である．具体的には，BIGrid は 2 つのグリッド（スモールグリッドおよびラージグリッド）から成る．

クスを用いたスコアのバウンディングでは，一切の距離計算を

定義 2（スモールグリッド）．閾値 r の MIO クエリに対する必要としない．

スモールグリッドは，セル csK の集合であり，K はキーを表す．

フレームワーク．アルゴリズム 2 に提案アルゴリズムの概要を示す．まず，BIGrid をオンラインで構築し，バウンディングよるオブジェクトの枝刈りを実行した後，必要なオブジェクトに対して正確なスコアを計算する．具体的には，MIO クエリが入力されると，Grid-Mapping(O, r) により BIGrid を構築する．

スモールグリッドはハッシュテーブルで実装される．各セルの1 辺の長さは √r3 であり，各点のキーはその座標と √r3 から計算される．各セル csK は圧縮ビット集合 b(csK ) を管理し，oi がキー K の点を持っている場合，b(csK ) の i 番目のビットは 1 である．

次に，Lower-bounding(O, r) により，各オブジェクトの下

定義 3（ラージグリッド）．閾値 r の MIO クエリに対するラー

low
界値を計算し，その中の最大値 τmax
を得る．さらに，Upper-

ジグリッドは，セル clK の集合であり，K はキーを表す．ラー

lowbounding(O, r, τmax
) により，各オブジェクトのスコアの上界

ジグリッドはハッシュテーブルで実装される．各セルの 1 辺値を計算し，o になり得ないものを枝刈りしつつ，必要なオブの長さは r であり，各点のキーはその座標と r から計算されジェクトを Ocand に入れる．その後，Verification(Ocand , r)る．各セル clK は転置リスト I(clK ) および 2 つの圧縮ビット集

により，枝刈りされなかったオブジェクトのスコアを計算し，合 b(clK )，badj (clK ) を管理する．I(clK ) はポスティングリストo∗ を得る．

I(clK )[oi ] の集合であり，キーが K の点 pji を管理する．また，∗

以下では，3. 1 節において BIGrid について説明し，3. 2 節でスコアのバウンディングを説明する．その後，3. 3 節で正確なスコアの計算方法について述べる．

I(clK )[oi ] が存在する場合，b(clK ) の i 番目のビットは 1 であ∨る．一方，badj (clK ) =b(clK ′ ) であり，K ′ は K または clKの隣接セルのキーである．
図 2 は BIGrid の構造を表している．以下で，ラージグリッド

3. 1 BIGrid：提案インデックス構造
BIGrid（a hybrid index of compressed Bitset, Inverted list,
and spatial Grid）は，圧縮ビット集合，転置リスト，および 3のセルの例を示す．
例 2．図 3 はラージグリッドのセル clK を表しており，キーがK である点 p2i ，p5i ，p3i+1 ，および p4i+2 が clK にマッピングされている．これらの点は転置リスト I(clK ) で管理され，b(clK )の i 番目，(i + 1) 番目，および (i + 2) 番目のビットが 1 にな

Algorithm 3: Grid-Mapping(O, r)
12る（圧縮されていると想定する）．

for ∀oi ∈ O dofor ∀pji ∈ oi do

3/* Building the small-grid */4

K ← the key of pji for the small-grid

また，スモールグリッドとラージグリッドはキーを共有してい5

if csK exists in the small-grid thenない．ハッシュテーブルによる実装のため，隣接セルにアクセ

6

Set the i-th bit of b(csK ) as 1

スするコストは O(1) である．

7

if |b(csK )| becomes 2 (the i′ -th bit is already 1)

定義 2 で示すように，スモールグリッドは点を管理しない．

then

圧縮ビット集合を利用するアイデアは，実データは偏りが大きいという事実に由来する．実データには，疎な領域と密な領域がともに存在することが多い [7]．圧縮ビット集合は，（例えば，疎な場合 00...0，密な場合 11...1 のように）連続するビッoi′ .L ← oi′ .L ∪ {K}, oi .L ← oi .L ∪ {K}8
9

if |b(csK )| becomes more than 2 thenoi .L ← oi .L ∪ {K}

10

else

トが同じ値の時，そのシーケンスを圧縮する．疎な場合および

11密な場合のどちらもビット集合がコンパクトになり，計算効率

12Create csK and set the i-th bit of b(csK ) as 1

13

Insert csK into the small-grid

用いない場合は全てのセルが n ビットのビット集合を管理する

14/* Building the large-grid */必要があり，メモリコストが高い．
（各セルの圧縮ビット集合の15

K ← the key of pji for the large-grid16

if clK exists in the large-grid then17

Set the i-th bit of b(clK ) as 1

18

I(clK )[oi ] ← I(clK )[oi ] ∪ {pji }およびメモリ効率いずれも向上する．一方，圧縮ビット集合を

大きさは圧縮状態に依存するため，同じとは限らない．
）スモー
ルグリッドはスコアの下界値を計算するために用いられ，ラー
ジグリッドはスコアの上界値を計算するために用いられる．

19

else

Grid-Mapping(O, r)．定義 2 および 3 から分かるように，BI-

20

Create clK and execute lines 17–18

Grid は閾値 r に依存するため，オンラインで構築される．アル21

Insert clK into the large-grid

ゴリズム 3 は BIGrid の構築方法を示している．全ての oi ∈ O
に対して，以下の操作を実行する．
スモールグリッドの構築．まず，pji のキー K を計算し，csK が（存在しな
存在していれば b(csK ) の i 番目のビットを 1 にする．
s
）ここで，|b(csK )| をい場合は cK を作成し，同様の操作を行う．
b(csK ) においてビットが 1 になっている数と定義する．|b(csK )|が 2 以上となったかどうかを確認し，2 となった場合，このセルには 2 つのオブジェクトの点が存在することが分かる．今，i′ 番目のビットが 1 とすると，oi と oi′ ともにキー K をキーリスト（oi .L および oi′ .L）で管理する．2 より大きくなった場
合，oi .L のみ更新する．
ラージグリッドの構築．ラージグリッドの構築はスモールグリッドの構築とほぼ同様である．違いは，転置リストを更新（18–20
行）することのみである．
上記のアルゴリズムは，以下の特徴がある．
（i）空セルが存在しない：セルが作成されるのは，セルが必要になった時のみである．
（ii）重複がない：ある点は一つのセルのみにマッピング
される．
（iii）効率的である：アルゴリズム 3 の各行は定数時間で処理できるため，Grid-Mapping(O, r) の計算量は O(nm)である．

3. 2 スコアのバウンディング∨|b(csK )| − 1 <= τ (oi )(2)∀K∈oi .L

証明．スモールグリッドのセルの 1 辺の長さは √r3 である．つまり，同じキーをもつ点 p と p′ は，dist(p, p′ ) <= r が保証される．そのため，b(csK ) の i 番目と j 番目のビットが 1 である場∨
合，oj ∈ Oi である．つまり， ∀K∈oi .L b(csK ) は，oi に対して，必ず dist(p, p′ ) <= r となる点のペアを持つオブジェクトの集合を表している．今，b(csK ) の i 番目のビットは 1（自身）□であるため，“−1” が必要である．
表記の簡単化のため，τ
る．ここで，なぜ τ

low

low

(oi ) を |∨s∀K∈oi .L b(cK )| − 1 とす(oi ) の計算の際に oi .L のみ考慮すれば十分かについて議論する．最も単純なアプローチは，全てのpji ∈ oi にアクセスし，OR 演算を実行することである．しかし，このアプローチでは無駄なセルのアクセスが生じてしまう．
具体的には，|b(csK )| = 1 かつ i 番目のビットが 1 のとき，このセルの圧縮ビット集合は式（2）に貢献しない．アルゴリズ
ム 3 により，oi .L はそのようなセルのキーを管理しない．

Lower-bounding(O, r). アルゴリズム 4 は，下界値の計算ア
low
ルゴリズムを示している．まず，τmax
を 0 とする．次に，各オ下界値の計算．各オブジェクト oi ∈ O に対してスコアの下界

ブジェクト oi ∈ O に対して，b(oi ) を作成し，oi .L で管理して値を計算する際，キーリストを利用する．具体的には，以下のいるキーをもつセルにアクセスし，ビット OR（b(oi )∨ b(csK )）補助定理によりスコアの下界値を得る．

lowを計算することで下界値を得る．この時，τmax< τ low (oi ) であ補助定理 1（下界値）．オブジェクト oi および BIGrid が与えられた時，以下の不等式が成り立つ．

low
low
れば，τmaxを更新する．最終的に，τmax= argmaxO τ low (oi )

となる．

low
Algorithm 5: Upper-bounding(O, r, τmax)

Algorithm 4: Lower-bounding(O, r)
1

low ← 0τmax

2for ∀oi ∈ O do

3b(oi ) ← ∅4for ∀K ∈ oi .L do▷ b(oi ) is a temporal compressed bitsetb(oi ) ← b(oi ) ∨ b(csK )5▷ bitwise OR operation

1

Ocand ← ∅▷ Ocand is a set of candidate objects for o∗

2

K←∅

3

for ∀oi ∈ O do4b(oi ) ← ∅5for ∀pji ∈ oi do▷ K is a set of keys
▷ b(oi ) is a temporal compressed bitset6τ low (oi ) ← |b(oi )| − 1

6

K ← the key of pji for the large-grid7

low thenif τ low (oi ) > τmax

7

if K ∈/ K then8

low ← τ low (o )
τmax
i

8

K ← K ∪ {K}9Compute badj (clK )10b(oi ) ← b(oi ) ∨ badj (clK )9lowreturn τmax

11

2 つ の 圧 縮 ビット 集 合 間 の ビット 演 算 の 計 算 コ スlow

ト を cost(b,b’) と す る と ，τ(oi ) の 計 算 コ ス ト は∑O( oi .L cost(b(oi ),b(csK ))) である．そのため，アルゴリズ∑
ム 4 の計算量は O(n oi .L cost(b(oi ),b(csK ))) となる 1 ．

12▷ see Definition 3▷ bitwise OR operation

τ upp (oi ) ← |b(oi )| − 1
low then> τmaxif τ upp (oi ) =Ocand ← Ocand ∪ {oi }1314

Sort Ocand in descending order of upper-bound15

return Ocand

上界値の計算．このステップは下界値の計算とほぼ同様である．オブジェクト oi のスコアの上界値を τ upp (oi ) とすると，

τ upp (oi ) の計算は以下の補助定理に従う．
補助定理 2（上界値）．オブジェクト oi の各点のラージグリッ
ドのキーの集合を oi .L′ とすると，以下の不等式が成り立つ．

∨

τ (oi ) <=|∨時間かかる．下界値の計算と同様に，全てのオブジェクトの上∑界値の計算は，O(n oi .L′ cost(b(oi ),badj (clK ))) 時間かかる.
ソートの計算量はこれらの計算量よりも小さいため，アルゴリ

badj (clK )| − 1

ズム 5 の計算量はこれらを足したものとなる．

∀K∈oi .L′

証明．前述の通り，badj (clK ) =ラージグリッドのセルの数を g とする．ラージグリッドの各セ∑
cost(badj (clK ),b(clK ′ )))ルの clK の badj (clK ) の計算は，O(gb(clK ′ ) であり，K ′ は K ま

たは clK の隣接セルのキーである．点 pji がセル clK にマッピングされたとする．ラージグリッドのセルの 1 辺の長さは r であ

3. 3 解 の 特 定
最後に，o∗ を特定する操作を説明する．まず，補助定理 2 から成り立つ以下の系を紹介する．

lるため，dist(pji , p) <= r を満たす点は，cK またはその隣接セ系 1（早期終了条件）．今，Ocand をキューと考える．このキュー

ルに存在する．これらと補助定理 1 の証明と同様の議論から，の先頭のオブジェクトをデキューし，その正確なスコアを計算□する．これまでに正確なスコアを計算したオブジェクトの中で，補助定理 2 は成り立つ．
補助定理 1 および 2 から以下の定理が成り立つ．

スコアが最も大きいものを o とする．現在のキューの先頭のオ

low
定理 2．もし τ upp (oi ) < τmax
ならば，oi =| o∗ ．

upp ′ブジェクトを o′ とした時，τ (o) >(o ) であれば，o∗ = o=τlowUpper-bounding(O, r, τmax)．この操作では，補助定理 2 とである．

定理 2 を利用してスコアの上界値の計算とオブジェクトの枝刈

BIGrid は，スコアのバウンディングだけでなく正確なスコアりを行う．アルゴリズム 5 により各オブジェクトの上界値を計の計算も効率化する．以下で，無駄なセルのアクセスと距離計算する．ここで，Ocand と K を用意する．Ocand は o の候補の算が削減できることを示す．

集合であり，K はキーの集合である（どちらも最初は空集合でVerification(Ocand , r)．途中結果のオブジェクトを o とし，ある）．オブジェクト oi のスコアの上界値を計算する際，下界初期状態を o = ∅（τ (o) = 0）とする．以下に，本ステップに値の計算と同様に b(oi ) を用意する．全ての pji ∈ oi に対して，pji のキー K を計算し，K ∈ K であるか確認する．K ∈/Kである場合，badj (clK ) が計算されていないことを意味するため，
clK とその隣接セルにアクセスして badj (clK ) を計算し，K を Kに追加する．また，b(oi ) は badj (clK ) とのビット OR により更low
新し，補助定理 2 から τ upp (oi ) を得る．もし τ upp (oi ) >= τmaxおける詳細を示す．

∗（ 1 ） Ocand の先頭のオブジェクトをデキューし，これを oi∗とする．もし τ upp (oi ) <= τ (o) であれば，o = o であることが系 1 から保証されるため，クエリ処理を終了する．そうでないならば，次の操作に移る．
（ 2 ） バウンディング時と同様に b(oi ) を作成し，i 番目のであれば，oi を Ocand に追加する．これらの操作を全てのオブビットを 1 にする．点 p ∈ oi に対して，ラージグリッドのキー

ジェクトに対して実行し，最後に Ocand を上界値の降順にソーK を計算し，セル clK にアクセスする．ここで，b = badj (clK )−トする．

b(oi ) とする．もし |b| = 0 であれば，b(oi ) は clK およびその1：本 実 験 で 用 い た 実 装 で は ，cost(b,b’) = O(size(b)+size(b’)) で あ り，size(b) は b のバイトサイズである [13]．

隣接セルにマッピングされた点の全てのオブジェクトを管理していることを意味する．この時，隣接セルにアクセスする必要

Algorithm 6: Verification(Ocand , r)
1

o←∅

2

while |Ocand | > 0 do

3
4

▷ o is an intermediate result

4 評価実験
本章では，提案アルゴリズムの評価のために行った実験につoi ← the front object of Ocand
if τ upp (oi ) <= τ (o) then▷ dequeue the front object

いて紹介する．

4. 1 設

定

5

break

6

b(oi ) ← ∅7

Set the i-th bit of b(oi ) as 1

および 512GB RAM を搭載した計算機で行った．本実験では

8for ∀p ∈ oi do

実行時間とメモリコストを評価したが，アルゴリズムの実行時▷ b(oi ) is a temporal compressed bitset

9

K ← the key of p for the large-grid10b ← badj (clK )− b(oi )11

if |b| > 0 thendofor ∀oj ∈ I(clK ′ ) s.t. the j-th bit of b is 1 do
if ∃p′ ∈ I(cl ′ )[oj ] s.t. dist(p, p′ ) <
=r

13
14

K

then
Set the j-th bit of b(oi ) (b) as 1 (0)15間の制限を 8 時間とした．
評価したアルゴリズム．以下に，本実験で評価したアルゴリズ

for ∀K ′ in the set of K and its adjacent cell keys

12

全ての実験は，Intel Xeon E5-2687W v4 processor (3.0GHz)

16

if |b| = 0 then

17

break

18

Execute lines 16–17

ムを紹介する．

BIGrid：本稿における提案アルゴリズム．



NL：2. 2 節で紹介したアルゴリズム．



SG：単純にグリッドを用いたアルゴリズム．閾値 r が与えられた時，1 辺の長さが r のグリッドを構築し，各点を該当するセルにマッピングする．オブジェクト o のスコア τ (o) は，

BIGrid と似たアプローチで計算される．このアプローチは，空間ジョインの既存アルゴリズムである TOUCH [6] を本問題に

19

τ (oi ) ← |b(oi )| − 1

20

if τ (oi ) > τ (o) theno ← oi21

適用したものに相当する．
ここで，2. 2 節で紹介した理論的アルゴリズムは事前計算にかかる時間が 8 時間を超えたため，評価しなかった．上記のアルゴリズムは C++で実装した．

o∗ ← o

データ集合．本実験では，Neuron および Syn を用いた．Neu-

23 return o∗ron はラットのニューロンデータであり，Syn はヒトの脳ネッ

22

トワーク [14] の次数分布から作成した人工データである．これ
らのデータの統計値を表 1 に示す．
はない．一方，|b| > 0 であれば，隣接セルにアクセスする必
表 1 データの統計

要があるが，転置リストを用いて無駄な距離計算を削減する．
ここで，Oi に含まれるかもしれないオブジェクトは，b によって表現されている．具体的には，b の j 番目のビットが 1 なら，

oj は Oi に含まれるかもしれない．そのため，I(clK ′ )[oj ] のみにアクセスすれば良いことが分かる．もし dist(p, p′ ) <= r とな

Dataset n

m

nm

r の単位

Neuron7,960 6,176,960

マイクロメートル

Syn

776

851,519 52

44,266,671-

る点 p′ が I(clK ′ )[oj ] に存在すれば，b(oi )（b）の j 番目のビッ

4. 2 実 験 結 果

トを 1（0）にする．再度 |b| = 0 であるか確認し，|b| = 0 で

r の影響．本実験では，文献 [8] に基づいて r を [4, 10] とした．

あれば隣接セルにアクセスする必要はないため，次の点を評価

図 4 は実験結果を示す．

する．上記の操作を全ての p ∈ oi に対して実行する．

図 4(a) から，NL と SG は逆の傾向を示していることが分か（ 3 ） 上の操作により，τ (oi ) = |b(oi )| − 1 である．もしる．NL は r が大きくなると実行時間が短くなり，SG は長くτ (o) < τ (oi ) であれば o を oi とし，最初の操作に戻る．

なっている．ここで，r が大きくなると，距離が r 以下となる

アルゴリズム 6 は本ステップを要約したものである．

点のペアができやすくなる．そのため，NL はそういったペア

議論．定義 1 ではスコアが最大のオブジェクトのみ考慮していを早い段階で発見でき，距離計算の回数が少なくなる．一方，るが，提案アルゴリズムは top-k オブジェクトの検索にも対応

SG については，セルに存在する点の数が増加するため，距離できる．アプリケーションがスコアが最大の k 個のオブジェク

計算の回数が増加してしまう．

low
トを求める場合，下界値の計算ステップにおいて，τmax
では

図 4(a) および 4(b) から，BIGrid の性能が最も良いことが分なく，k 番目に大きい下界値を保存する．上界値の計算ステッ

かる．例えば，r = 4 の時，Neuron データにおいて，BIGrid

プでは，この値を用いて枝刈りを行う．解の特定ステップでは，は NL（SG）よりも 60（3）倍早い．また，Syn データにおいk 個のオブジェクトの正確なスコアを計算した後に閾値を設定て，BIGrid は SG よりも 16 倍早い．この結果から，BIGrid

し，系 1 を拡張したものを用いる．

におけるスコアのバウンディングは正確にスコアを計算するよりも高速であることが分かる．

SG

BIGrid

SG

100

10

メモリ [GB]

実行時間 [sec]1000

実行時間 [sec]SG

BIGrid100000

10000

1000

100

1
4

5

6

7

8

9

4

10

5

6

7

8

9

(a) 実行時間（Neuron）

SG

10

8
6
4
2
0

4

10

BIGrid12

5

6

r （Syn）

r（Neuron）

BIGrid

5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0

メモリ [GB]NL
10000(b) 実行時間（Syn）

7

8

9

10

4

5

6

7

8

9

r（Neuron）

r（Syn）(c) メモリ（Neuron）(d) メモリ（Syn）

10

図4 r の 影 響SGBIGrid

SG

100

10

メモリ [GB]

1000

実行時間 [sec]実行時間 [sec]SG

BIGrid

10000

1000

1

100

10
0.2

0.4

0.6

0.8

1

0.2

0.4

0.6

0.8

1

(a) 実行時間（Neuron）(b) 実行時間（Syn）

SG

BIGrid

12
10
8
6
4
2
0

0.2

0.4

サンプリング率（Syn）

サンプリング率（Neuron）

BIGrid

5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0

メモリ [GB]

NL
10000

0.6

0.8

1

0.2

0.4

0.6

0.8

サンプリング率（Neuron）

サンプリング率（Syn）(c) メモリ（Neuron）(d) メモリ（Syn）

1

図 5 データ数の影響

NL

SG

BIGridSG

コアの計算の枝刈り効果は継続している．

BIGrid10000

実行時間 [sec]実行時間 [sec]

10000

1000

100

5 関連研究1000

空間データ処理は多くのアプリケーションで利用されている．
10

100
1

2

4

8

16

1

2

k（Neuron）

4

8

16

k（Syn）(a) 実行時間（Neuron）(b) 実行時間（Syn）

図6 k の 影 響

本章では，提案アルゴリズムに関連した技術を紹介する．
空間クエリ処理．メインメモリ空間ジョインは幅広い応用例を持ち，近年注目を集めている [15]．点集合と距離の閾値が与えられた時，この問題は，距離が閾値以内の点のペアを全て検索

図 4(c) および 4(d) は SG と BIGrid のメモリコストを示しする．そのため，この問題の計算量はデータ数に対して自乗でている．
（NL はインデックスを用いないため，メモリコストをあり，実践的な実行時間を削減するための研究が多数行われて割愛する．
）閾値 r が大きくなると，メモリコストが小さくな

いる．階層的なグリッド構造を利用する TOUCH [6] や空間分る．これは，セルの数が少なくなるためである．BIGrid のメ

割アルゴリズム [16] がその一例である．4 章の実験により，ジョモリコストは SG よりも大きいが，近年のメインメモリシステ

インを用いたアプローチは本稿の問題では有効ではないことをムに対して問題のないコストである．

示した．

データ数の影響．スケーラビリティの検証のため，各データ集

最近傍ペア検索問題は，点集合の中において，距離が最も短合をサンプリングし，データサイズを変えた場合の性能を調べ

い点のペアを検索するものである [17]．本稿の問題でも距離がた．また，r = 4 とした．サンプリング率 s の時，s × n 個の近い点のペアを検索するため，この問題に関連しており，最近

オブジェクトがランダムに選ばれる．図 5 に実験結果を示す．

傍ペアを利用した理論的アルゴリズムを 2. 2 節で紹介した．し

図 5(a) および 5(b) から分かるように，NL と SG はスケー

かし，この理論的アルゴリズムは実践的ではない．

ラビリティに乏しいが，BIGrid はデータ数に対してほぼ線形

統合的なインデックス構造．近年のアプリケーションでは，空であることが分かる．これは，Grid-Mapping(·, ·)，Lower-

間データは他の属性を持つものが増えており，例として，キー

bounding(·, ·)，および Upper-bounding(·, ·, ·) のコストがほワード [18] やソーシャル関係 [19] がある．このようなオブジェ

ぼ線形であり，かつ正確なスコアを計算するオブジェクトの数

クトを検索するためのクエリとして，spatio-textual クエリやが少ないためである．また，図 5(c) および 5(d) から，BIGrid

geo-social クエリが提案されている．このようなクエリを効率のメモリコストは線形であることが分かる．

的な処理するためには，空間属性と他の属性に対するインデッk の影響．最後に k の影響を調べる．図 6 に実験結果を示す

クスを統合することが効果的であることが知られており，その（r = 4）．ここで，NL と SG は全てのオブジェクトのスコアを代表例に IR 木（R 木と転置リストの統合インデックス）[20] が計算するため，k の影響を受けない．図 6(a) および 6(b) から，ある．BIGrid はこのようなデータ構造から着想を得ているが，

top-k オブジェクトを検索する場合も提案アルゴリズムは効率

例えば IR 木とは大きな違いがある．IR 木は，クエリオブジェ

的であることが分かる．また，k が大きくなると，k 番目のス

クトが与えられた時，そのクエリに対して Top-k にならないオ

コアが小さくなるため，実行時間は長くなるものの，不要なスブジェクトをまとめて枝刈りするために用いられる．このクエ

リオブジェクトは点であるため，最小外接矩形によるインデックス構造が有効である．一方，BIGrid はスコアのバウンディン
グおよび正確な計算を効率的に実行するために設計されている．

6 おわりに本稿では，空間データベースにおいて最もインタラクティブなオブジェクトを検索する問題に取り組んだ．筆者らの知る限
り，本稿の問題はこれまでに取り組まれていない．本稿では，
ネステッドループおよび理論的アルゴリズムを紹介し，これらが効率的でないことを示した．次に，BIGrid と呼ぶインデッ
クス構造を設計し，効率的にスコアのバウンディングおよび正確な計算を実行できることを示した．実データおよび人工デー
タを用いた実験から，提案アルゴリズムは比較アルゴリズムよりも効率的であることを確認した．
謝辞. 本研究の一部は，文部科学省科学研究費補助金・基盤研
究 (A)(18H04095) および JST，ACT-I の支援を受けたもので
ある．
文

献

[1] J. van Pelt and A. van Ooyen, “Estimating neuronal connectivity from axonal and dendritic density fields,” Frontiers incomputational neuroscience, vol. 7, pp. 160:1–160:19, 2013.
[2] H. Fan, H. Su, and L. J. Guibas, “A point set generation
network for 3d object reconstruction from a single image,”in CVPR, vol. 2, no. 4, 2017, pp. 605–613.
[3] Q. Fan, D. Zhang, H. Wu, and K.-L. Tan, “A generaland parallel platform for mining co-movement patterns overlarge-scale trajectories,” PVLDB, vol. 10, no. 4, pp. 313–
324, 2016.
[4] http://neuromorpho.org/index.jsp.
[5] D. Amagata and T. Hara, “Identifying the most interactive
object in spatial databases,” in ICDE, 2019.
[6] S. Nobari, F. Tauheed, T. Heinis, P. Karras, S. Bressan,and A. Ailamaki, “Touch: in-memory spatial join by hierarchical data-oriented partitioning,” in SIGMOD, 2013, pp.
701–712.
[7] F. Tauheed, T. Heinis, and A. Ailamaki, “Thermal-join: A
scalable spatial join for dynamic workloads,” in SIGMOD,
2015, pp. 939–950.
[8] A. van Ooyen, A. Carnell, S. de Ridder, B. Tarigan, H. D.
Mansvelder, F. Bijma, M. de Gunst, and J. van Pelt, “Independently outgrowing neurons and geometry-based synapse
formation produce networks with realistic synaptic connectivity,” PloS one, vol. 9, no. 1, p. e85858, 2014.
[9] R. Badhwar and G. Bagler, “A distance constrained synaptic plasticity model of c. elegans neuronal network,” Physica
A: Statistical Mechanics and its Applications, vol. 469, pp.
313–322, 2017.
[10] S. Nigam, M. Shimono, S. Ito, F.-C. Yeh, N. Timme, M. Myroshnychenko, C. C. Lapish, Z. Tosi, P. Hottowy, W. C.
Smith et al., “Rich-club organization in eﬀective connectivity among cortical neurons,” Journal of Neuroscience,
vol. 36, no. 3, pp. 670–684, 2016.
[11] P. Bonifazi, M. Goldin, M. A. Picardo, I. Jorquera, A. Cattani, G. Bianconi, A. Represa, Y. Ben-Ari, and R. Cossart,“Gabaergic hub neurons orchestrate synchrony in developing hippocampal networks,” Science, vol. 326, no. 5958, pp.
1419–1424, 2009.
[12] M. Pavlovic, D. Sidlauskas, T. Heinis, and A. Ailamaki,“Quasii: Query-aware spatial incremental index,” in EDBT,
2018, pp. 325–336.

[13] O. Kaser and D. Lemire, “Compressed bitmap indexes: beyond unions and intersections,” Software: Practice and Experience, vol. 46, no. 2, pp. 167–198, 2016.
[14] http://networkrepository.com/bn.php.
[15] B. Sowell, M. V. Salles, T. Cao, A. Demers, and J. Gehrke,“An experimental analysis of iterated spatial joins in main
memory,” PVLDB, vol. 6, no. 14, pp. 1882–1893, 2013.
[16] J. M. Patel and D. J. DeWitt, “Partition based spatialmerge join,” in SIGMOD Record, vol. 25, no. 2, 1996, pp.
259–270.
[17] M. I. Shamos and D. Hoey, “Closest-point problems,” in
FOCS, 1975, pp. 151–162.
[18] L. Chen, G. Cong, C. S. Jensen, and D. Wu, “Spatial
keyword query processing: an experimental evaluation,” in
PVLDB, vol. 6, no. 3, 2013, pp. 217–228.
[19] K. Mouratidis, J. Li, Y. Tang, and N. Mamoulis, “Joint
search by social and spatial proximity,” TKDE, vol. 27,
no. 3, pp. 781–793, 2015.
[20] G. Cong, C. S. Jensen, and D. Wu, “Eﬃcient retrieval of the
top-k most relevant spatial web objects,” PVLDB, vol. 2,
no. 1, pp. 337–348, 2009.