論文
DBSJ Letters Vol.4, No.1――――――――――――――――――――――――――――――――――――

ムービングオブジェクトデータベ
ースにおける類似検索のための 1
次元索引付け手法とその評価
One-Dimensional Indexing of Moving
Object Database for Similarity Search andits Evaluation

北原 由美子♥

増永 良文♠

Yumiko KITAHARA

Yoshifumi MASUNAGA

我々は，3 次元空間において物体の動きに関するデータを市販のモーションキャプチャシステムQuickMAGⅣを用いて取得し，様々な問合せを実現するムービングオブジェクトデータベースシステムの構築を進めてきた．本論文では，このシステムで類似検索処理を効率化するために，データに索引付けするにあたり，多次元の空間索引を付与するのではなく，
現在ビジネスデータ処理の分野で普及している 1 次元の索引であるB+木を用い索引付けすることを考えた．この索引付
けは，データベース内のある一つのデータと他のデータ間の相違度を探索キーとしてデータを 1 次元で構造化する. この索引法が類似検索でどれほど有効かを，データを構造化しない場合と比較して示す．
A moving object database system has been underdevelopment at Ochanomizu University. It captures
motion object data in the three dimensional space, where
the data are captured using a commercial motion
capturing system named QuickMAGⅣ. In this paper, anovel indexing method of moving object data using
B+-tree, a widely used index in business data processing,is investigated. The essential difference between the
traditional spatial indexing and our approach is that theformer is multi-dimensional while the latter is one
dimensional.
The one dimensional index is given
according to the dissimilarity measure between the dataand one fixed data a moving object database.
Effectiveness of this approach is examined by comparing
it with non-indexed case under similarity search.

1. はじめに
近年，モーションキャプチャリングシステムやGPSなどを用いて，動く物体の位置や姿勢などのデータを計測するセン
シング技術が発達している．それに伴い，こうした動きのデータに対して様々な問合せや分析を行いたいという要求が高まっている．そこで我々は，3次元空間において，物体の動きに関するデータを取得し，様々な問合せを実現するムー
ビングオブジェクトデータベースシステムの構築を進めてきた[1,2,3]．本システムの主要な機能である類似検索機能は，Query-By-Exampleの発想に基づいて行い，データ間の相違♥

学生会員 お茶の水女子大学大学院人間文化研究科博士前期課程 yumiko@db.is.ocha.ac.jp♠
正会員 お茶の水女子大学理学部情報科学科
masunaga@is.ocha.ac.jp

1

度をユークリッド距離関数によって計算している．これまで
は類似検索を行うのに，問合せデータを与えたとき，データ
ベースに格納されている全データとの相違度を総当りで計算していた．しかし，これでは格納されているデータ量が多くなるにつれ，検索時間が増加してしまう．そのために，データを索引付けすることが考えられるが，ムービングオブジ
ェクトのデータは，空間的な位置や時間を属性として有するために，一般にはR木といった多次元の索引付け手法を必要とする．しかし，現在，多用されている索引付け手法である
B+木は“1次元”の索引であるので，Oracleなど市販のデー
タベースシステムを使ってムービングオブジェクトデータを格納して検索するにはB+木を使ったムービングオブジェ
クトデータの索引付けを考えることが必要である．この観点から，我々は，先行研究 [4] で索引を1次元のスカラー値で与える方法を提案した．本論文では，その手法のもとで類似
検索処理時間が索引を付与された場合と付与されない場合とでどれほどの改善があるのか，その有効性を論じる．

2. ムービングオブジェクトデータベースと類似検索
2.1 システム概要
本研究でのシステム概要を図1に表す．ムービングオブジェクトデータの計測には，センシング装置には光学式のモーションキャプチャリングシステムであるQuickMAG Ⅳ（応用計測研究所製）を使用する．
オブジェクトの 3 点にカラーマーカを付け，ステレオカメ
ラを用いオブジェクトの動きを 3 次元で計測する．計測後，ユーザは格納インタフェースで計測データのシーンやオブジェクトに関する情報を登録し，挿入エンジンによりムービ
ングオブジェクトデータモデルに従ったデータに変換した
上でムービングオブジェクトデータベースに格納される．また，ユーザは問合せインタフェースによって検索エンジンを制御し，Query-By-Example の発想に基づく問合せを行い，検索エンジンを通して検索結果を返す．
ステレオカメラ

格納インタフェース
シーン・オブジェ
クト情報の登録

問合せインタフェース
オブジェクト制御

QuickMAG Ⅳ

挿入エンジン・データ変換・データ格納の SQL 文の発行

データ格納

オブジェクトの動きを計測し，データの取得

結果の表示

検索エンジン・データ変換・相違度の計算・検索結果の受渡し

データ検索

結果

データベースサーバ(SQL Server7.0)
シーンデータ
動きに関するデータ
・計測間隔など
・基本データオブジェクト情報・導出データ・形状，サイズ，マーカの位置など

図 1 システム概要
Fig.1 A System Overview

2.2 動きとは計測されたオブジェクトの動きは，オブジェクトの中心座
標，向き，傾き，及びそれに付与された時刻印の4要素で構成される．正式には，計測周波数fで時刻tsからteまで計測さ
r
r r
r で表
れたオブジェクトの動きをベクトル M = m
1 , m2 ,L, mnrr r rであり，各要素はオブジェク
す．このとき mi = pi , o ri , gri , t i

日本データベース学会 Letters Vol.4, No.1

論文
DBSJ Letters Vol.4, No.1――――――――――――――――――――――――――――――――――――
トの位置ベクトル pr i = xi , yi , z i ，向きベクトルrr
ori = oxi , oyi , ozi ，傾きベクトル gri = gxi , gyi , gzi を表してい

3. ムービングオブジェクトデータの 1 次元
索引付ける．また，ts = t0，te = tn，n = (te-ts)× fである．

ムービングオブジェクトデータは時間属性を有しているという意味で時系列データである．これまで，時系列データを構造化するための技術として様々な索引付けの研究が行われてきた．よく知られた方法として，離散フーリエ変換などの特徴抽出関数を用いて時系列データを 2 次元の周波数空間にマッピングして，R木やK-D木に代表される空間アクセス法を適用する方法がある[6,7]．注意すべきこととして，このような変換により，一般には多次元の索引構造が誘引される．一方，売上や社員管理といったビジネスデータ管理を主目的とするリレーショナルデータベースではB木やB+ 木といった索引付けの手法が使われているが，それはデータのある一つの属性値に基づいた索引であるという意味で，1 次元の索引構造である．これらの索引付け手法は現在稼動しているほとんどのデータベース管理システム上で使用可能となっている．さらに，リレーショナルデータベースでは，BLOB
データ型の導入で，時系列データを属性値として直接格納できる状況となっている．したがって，Oracleなど既存のリレーショナルデータベースシステムを用いてムービングオブ
ジェクトデータ管理を行う場合，ムービングオブジェクトデータにB+木などの 1 次元の索引付けができるか否かを研究しておくことが重要となる．

2.3 動きの同一性と基本類似性
動きの同一性の定義について述べた後，動きの各要素の基
本類似性の定義について述べる．
【定義 2.1】（動きの同一性）
r
r
動き M と M ′ が次の条件を満たすとき，2 つの動きは同一であるという．
1.
f = f′
2.
3.

t s = t s′ ∧ te = te′(∀i ) pr i = pr i′【定義 2.2】（位置の基本類似性）
rr
動き M が M ′ に対して次の条件を満たすとき，位置について
ε -類似しているという．
1.
f = f′
2.

t s = t s′ ∧ te = te′

3.

r r
DP M , M ′ =

(

)

∑

n
i =1

r
r 2
p i − p i′n≤ε

なお，定義から分かるように，これらは開始時刻と終了時
刻が同じでかつ計測周波数が等しい 2 つのムービングオブジェクトデータに対する定義である．そこで，格納データの長さが異なる場合に対応する検索法として，タイムワーピング
距離関数[5]を用いてデータ間の相違度を計算する方法や，データ自身を伸縮し長さを等しくした後ユークリッド距離関
数で相違度を計算する方法を取入れた．それぞれの方法で類似検索を行ったときの検索結果の比較を次節で示す．

2.4 ユークリッド距離関数の採用
ムービングオブジェクトデータには，模型列車を円軌道上
を 等 速 (train̲c) ， 速 - 遅 (train̲fs) ， 速 - 遅 - 速 - 遅(train̲fsfs)の 3 速度変化パターンで走らせた 300 個データを用いる．表１に，問合せデータに train1̲c と train1̲fsを与えたときの検索結果をランキングで示したものと検索に要した時間を示す．
表 1 類似検索結果と検索時間
Table 1 Similarity Search Results and Execution Timetrain1_c
train1_fs
ユークリッド Time Warping
ユークリッド Time Warping
1 train1_c
1 train1_fs
train1_c
train1_fs
2
2 train2_fs
train2_c
train2_c
train2_c
3 train2_fsfs
3 train1_fsfs
train2_fsfs
train1_c
4 train1_fsfs
4 train2_fsfs
train1_fs
train2_fsfs
5 train2_fs
5 train1_c
train2_fs
train2_fs
6 train1_fs
6 train2_c
train1_fsfs
train1_fsfs
2.82 (s)72.95 (s)2.84 (s)74.76 (s)この結果から，タイムワーピング距離を用いた場合，走行パターンがうまく識別されていないことが分かる．またタイ
ムワーピング距離を用いると，要素同士の比較回数が膨大になるため，検索に要する時間は平均約 26 倍もかかってしまう．そのため，ムービングオブジェクト同士の類似性を取り扱うためには，ユークリッド距離関数を用いることにする．

2

3.1 相違度に基づく索引付け
まず，データベースに格納されているムービングオブジェ
クトデータの中からある一つのデータを選定し，それを“基準データ”とする．次に，基準データと他の格納データとの相違度をユークリッド距離関数によって計算する．相違度は1 次元の値なので，この値を索引としてB+木を用いてデータを構造化する．B+木はデータの挿入順で木構造が変わってくるが，ここではデータベースに格納されている順にデータを索引付けすることとする．
こうして構造化したデータに対して類似検索を行う，しかし，この基準データとの相違度，つまり各データに付与された索引は相対的なものであるので，実データ同士の距離関係が正確に保存されていない．そのため，本来類似していない
データを検索結果として返してしまう過多誤認が生じる恐れがある．一方，過小誤認は発生しないことは明らかにされてる[4]．そこで次に，この索引を利用しながらも過多誤認を排除する類似検索法について説明する．

3.2 索引を利用した類似検索法
r

ある問合せデータ Q が与えられたとする．
rr
r r【手順Ⅰ】まず，基準データ R と Q との相違度
D p R, Q を求r
める．格納されている全データには， R との相違度が索引として付与されているのでその値に着目し，

(

)

( )

(

)

(

)

r r
r v
r r
D p R, Q − ε ≤ D p R,vO ′ ≤ D p R, Q + ε vとなる索引をもつ全てのデータ O′ を検索する．この O′ が全検索結果候補データとなる．
v【手順Ⅱ】手順Ⅰで検索された候補データ O′ と問合せデーr
タ Q との実際のユークリッドr 距離を計算し，( v)

D p Q, O r≤ εvとなる索引をもつ O が最終的に Q と ε-類似している検索結果となる．

例えば，与えられた問合せデータの索引が 4.8 とすると，4.8 に一番近い値の葉ノードにたどり着く．その前後で 4.8

日本データベース学会 Letters Vol.4, No.1

論文
DBSJ Letters Vol.4, No.1――――――――――――――――――――――――――――――――――――±εに入る探索キーをもつ葉ノードが候補データとなる．またε= 0 のときは特殊な場合であるが，問合せデータに格納
データを用いれば検索可能である．

3.3 基準データの選定法
以上に述べた手法により類似検索を行う場合，基準データの選定法が問題となってくる．シミュレーションによりその最適解を探ったところ，データベースに格納されたデータの分布が正規分布に近い偏りである場合，その中心からある程
度離れた位置のデータを基準データに取ることで，類似検索時に検証すべきデータ数をある程度抑えられることが明らかになったので，格納されている全データの時刻ごとの座標r
値を平均して一つのデータを作成し，この平均データ A とのr
相違度が最も大きいデータを基準データ R と定めている[4]．
こうして選定した基準データとの相違度を用いた類似検索の検索範囲を簡単のため，2 次元の点データを用いたものをr
図 2 に示す．問合せデータ Q と ε-類似しているものを検索するとき，図 2 の環状の網掛け部分に含まれるデータが検索結果の候補データ，円状の斜線部分に含まれるデータが最終的な検索結果である．これまでは問合せデータを与える度にデータ間の相違度を総当りで計算していたが，データをこの手法を用いて索引付けすることにより，データ間の相違度を計算する回数が減り，検索に要する時間の削減が期待できる．

表 2 検索時間（ε = 500）
Table 2 Execution Time（ε = 500）
data1 data2 data3 data4 data5 data6
問合せデータ13.473 13.088 13.204 13.492 13.268 13.183
総当り
一次元索引構造 14.721 14.65 14.416 15.189 15.03 14.862
600
600
600
600
600
600
検索結果数
0.915 0.893 0.916 0.888 0.883 0.887
性能比(倍)
表 3 検索時間（ε = 100）
Table 3 Execution Time（ε = 100）
data1 data2 data3 data4 data5 data6
問合せデータ13.272 13.39 13.663 13.28 13.387 13.274
総当り
一次元索引構造 2.592 3.86 7.602 7.157 4.912 7.99
8
62
256
178
122
210
検索結果数
5.12
3.47
1.8
1.86
2.73
1.66
性能比(倍)
表 4 検索時間（ε = 50）
Table 4 Execution Time（ε = 50）
data1 data2 data3 data4 data5 data6
問合せデータ13.264 13.53 13.274 13.249 13.11 13.205
総当り
一次元索引構造 0.739 2.037 4.793 2.74 1.936 2.861
4
20
114
34
32
44
検索結果数
17.9
6.64
2.77
4.84
6.77
4.62
性能比(倍)
表 5 検索時間（ε = 0）
Table 5 Execution Time（ε = 0）
data1 data2 data3 data4 data5 data6
問合せデータ13.21 13.319 13.503 13.09 13.247 13.469
総当り
一次元索引構造 0.328 0.329 0.343 0.338 0.344 0.341
1
1
1
1
1
1
検索結果数
40.3
40.5
39.4
38.7
38.5
39.5
性能比(倍)の葉ノードまでたどるのにかかるコストをCpath1，類似検索法の手順ⅠでかかるコストをCpath2，手順Ⅱでかかる平均コ
ストをそれぞれCpath3とする．Cpath3=Cpath0に注意する．過多
誤認検証の対象となる候補データ数をmεとすると検索時間

図 2 検索範囲
Fig.2 Search Ranges

CB+treeは(2)式の通りである．

C B+ tree = C path0 × m ε + C path1 + C path2 + C′0

4. 検索時間のモデル化
総当りで検索を行った場合と，1 次元索引付けしたデータに対して検索を行った場合の検索時間を第 1 次近似でモデル化したものについてそれぞれ論じる．

4.1 総当りによる検索時間
ムービングオブジェクトデータが計測順にデータベースに格納されているとする．ある一つの問合せデータを与えた
とき，格納データ一つ一つとの相違度を計算するのにかかる平均コストをそれぞれCpath0とすると，全データ数がnのときの検索時間CExは(1)式の通りである．

C Ex = C path0 × n + C 0 (s)ここでC0はデータ数とは無関係な定数項である．

4.2

(1)

1 次元索引付けによる検索時間

ムービングオブジェクトデータが前章で述べた方法でB+木を用いて 1 次元で索引付けされているとする．ある一つの問合せデータを与えたとき，そのデータの索引と一番近い値

3

(s)

(2)

ここでC’0はデータ数とは無関係な定数項である．

5. 検索時間の性能評価
卓球のラケットの 3 点にカラーマーカを付け，そのフルス
イングの状態を QuickMAG Ⅳで計測しムービングオブジェ
クトデータを取得する．この計測データを上記の 1 次元の索
引構造を用いて構造化したものに対して類似検索を行い，検索に要した時間を計測し，従来の総当り法の検索時間と比較する．また今回は木が最も深くなる最悪の場合を想定し，木のファンアウト数は 2 としている．さらにデータベースから問合せデータをランダムに抽出し，ε の値を変えて類似検索を行う．
データ数を 600 とし，ε = 500，100，50，0 としたときの検索結果を表 2，3，4，5 に示す．これらの表から従来の総当りの場合，どんな問合せデータを与えても，またεがどんな値であっても検索時間はほぼ一定であることが分かる．一方，1 次元索引付けした場合，問合せデータによって検索時間は異なる．この差は(2)式より候補データ数mεの影響といえる．表 2 よりε = 500 では，索引付けしたほうが平均約

日本データベース学会 Letters Vol.4, No.1

論文
DBSJ Letters Vol.4, No.1――――――――――――――――――――――――――――――――――――
50

表 6 総当り法および 1 次元索引構造の検索結果
Table 6 Search Result Ranking

160

性能比

性 40
能
比 30

検索結果数

140
120 検
100

索
結

80 果
20

60 数
40

10

20
0

0
0

5

10 15 20 25 30 35 40 50 60 70 80 90 100ε

図 3 ε と性能比および検索結果数の関係（データ数 600）
Fig.3 Relation between ε and its performance (600data)
80

50

性能比

性 40
能
比 30

検索結果数

70

60 検

索

50 結
40 果
30 数

20

20

10

10
0

0
0

5

10 15 20 25 30 35 40 50 60 70 80 90 100ε

図 4 ε と性能比および検索結果数の関係（データ数 300）
Fig.4 Relation between ε and its performance (300data)
0．897 倍性能が低下してしまっている．この原因としては，検索結果数が全データ数となっていることから，候補データ
数が全データ数（m500 = 600）となってしまったためと考えられる．また，検索結果数はεとともに増減するが，問合せデータによって検索結果数の絞込みに差が生じる．そこで両極端のデータ，ここではdata1 とdata3 を除いたデータの平均値に基づいてεと性能比，および検索結果数の関係を調べたところ図 3 のようになった．同様にデータ数を 300 と固定した検索結果より図 4 の関係が導かれた．図 3，図 4 から，
全データ数の約 5%分のデータを検索結果として取得したいときはε = 50 とすればよい．このように，εの値が増加する
につれ性能比は減少していくが，データ数に関わらずこの 1
次元索引付け手法がムービングオブジェクトデータベース
における類似検索において有効であることが実証された．
また，問合せデータに yumiko1 を与えたときの検索結果
は，総当り法と索引付けした場合の両方において表 6 のようになった．検索結果は類似順に並んでいる．これより過多誤
認や過少誤認が発生していないことが分かる．

6. まとめと今後の課題
本稿では，現行のムービングオブジェクトデータベースにおいて，より効率的な類似検索を実現するため，ムービング
オブジェクトデータをB+木を用いて 1 次元で構造化する方法について述べ，実際に索引付けしたデータに対し類似検索を行い，その有効性を示した．今回の実装では，動きの要素
である位置，向き，傾きデータを各々索引付けしたため，各要素に重み付けした検索には対応していない．今後は，オブジェクトが回転するなど全ての要素データが重要となる複雑な動きの場合の類似検索が可能となるよう，動きの要素を統合させた索引付けを検討する必要がある．

4[文献][1] Y. Masunaga and N. Ukai，“Toward a 3D Moving Object Data
Model -A Preliminary Consideration-，” Proceedings of the1999 International Symposium on Database Applications in
Non-Traditional Environments, pp.306-316，November 1999.
[2] 水崎聡子，増永良文，“ムービングオブジェクトデータベ
ースシステムのための類似検索機能の実現に向けて，”情報処理学会データベースシステム研究会報告, vol.2001,
no.70, pp.217-223, 2001.
[3] 河内聡恵，増永良文，“ムービングオブジェクトの速度変化パターンを識別できる類似検索機能の導入，”日本デー
タベース学会 Letters，Vol.2，No.1, pp.15-18, May 2003.
[4] 澤井美弥，“基準データとの相違度に着目したムービング
オブジェクトデータの一類似検索法，”電子情報通信学会
技術研究報告（DBWS2003），Vol.103，No.191，pp.247-252,
July 2003.
[5] B.-K. Yi, H. Jagadish, and C. Faloutsos, “Efficient Retrieval of
Similar Time Sequences Under Time Warping,”Proceedings ofthe International Conference on Data Engineering, pp.201-208,
IEEE CS, Orlando, FL, February 1998.
[6] R. Agrawal, C. Faloutsos, and A. Swami, “Efficient similarity
search in sequence databases ，” Proceedings of the 4thInternational Conference on Foundations of Data Organizations
and Algorithms (FODO ’93), pp.69-84, Chicago, October 1993.
[7] D. Rafiei and A. O. Mendelzon, “Querying Time Series Data
Based on Similarity,” Proceedings of the 8th DASFAA,
pp.267-274, Kyoto, March 2003.

北原 由美子Yumiko KITAHARA

2005 お茶の水女子大学大学院人間文化研究科博士前期課程
数理・情報科学専攻修了．ムービングオブジェクトデータベ
ースシステムの研究に従事．日本データベース学会学生会員．

増永 良文

Yoshifumi MASUNAGA

お茶の水女子大学理学部情報科学科教授．1970 東北大学大学院工学研究科博士課程修了，工学博士．データベースシス
テムの研究・開発に従事．情報処理学会および電子情報通信学会フェロー．日本データベース学会会長．著書に「リレーショナルデータベース入門［新訂版］」(サイエンス社)など．

日本データベース学会 Letters Vol.4, No.1