実世界の事象をデータ化しながら活用するフィジタルデータセントリックコンピューティング
高速時空間データ管理技術「Axispot®」と時空間データ高速検索技術
NTTソフトウェアイノベーションセンタ

花舘 蔵之(はなだて まさゆき)/木村 達郎(きむら たつろう)/沖　宣宏(おき のぶひろ)/重松 直子(しげまつ なおこ)/上野 磯生(うえの いそお)/内藤 一兵衛(ないとう いちべえ)/久保 貴司(くぼ たかし)/宮原 和大(みやはら かずひろ)/磯村　淳(いそむら あつし)

実空間上のヒトやモノ、自然環境等に関するさまざまな情報の収集とクラウド上での一元管理を可能にするIoT(Internet of Things)は、ヒトや自動車等の動く物体(動的オブジェクト)を管理する次のような次世代サービスで必要不可欠となってきています。

1. 車両間通信サービス：インターネットとつながる自動車(コネクティッドカー)が収集した情報を、自動車の走行位置や情報送信時刻と合わせてクラウドに蓄え、事故や渋滞等の交通状況を、関係する道路を走行する車両にリアルタイムに通知します。
2. 拡張現実：ヒトが装着したウェアラブルデバイスやスマートフォンが送信するさまざまな情報を、ヒトの歩行位置や情報送信時刻と合わせてクラウドに蓄え、店舗の混み具合やリコメンド情報等、ヒトの行動の意思決定にかかわる情報をリアルタイムに通知します。

NTTソフトウェアイノベーションセンタ(SIC)では、これらの次世代サービスの実現で必要不可欠となる、大量の動的オブジェクトが一斉送信する情報の蓄積と、蓄積した動的オブジェクトの中から、ある時刻に、ある特定の地域にいる動的オブジェクトをリアルタイムに検索する高速時空間データ管理技術 「Axispot®」に取り組んでいます。本稿では、Axispot®が用いるデータベース(時空間データベース)と、その技術課題を解決するために昨年度開発した「時空間データ高速検索技術」⁽¹⁾を紹介します。また、この時空間データ高速検索技術をベース技術として実現されるAxispot®のアーキテクチャ全体像と今後の展望を述べます。

「時空間データベース」とは、緯度や経度といった空間上の位置(空間情報)と、時刻、期間といった時間情報の双方に関連付いたデータ群を効率的に蓄積・検索するデータベースです^(2)、(3)。一方、時間情報や空間情報だけを用いるデータベースとして、それぞれ「時系列データベース」「空間データベース」が知られていますが、時空間データベースは、一般的に空間データベースで時間情報も管理できるように拡張することで実現されます⁽³⁾。そこで、時空間データベースを説明する前に、空間データベースの実現方法を簡単に説明します。
空間データベースは、土地や建物の範囲に関する空間情報を、「点」「線」「面」等の幾何的なデータ形式で格納し、同様に幾何的なデータ形式でクエリとして与えられる空間情報と空間演算を行い、該当する空間情報を返却するデータベースです。このデータ形式と空間演算の例を図1に示します⁽²⁾。例えば、ある地域に含まれる建物群を検索する場合、緯度と経度を用いて建物の範囲(面)を建物ごとに格納し、緯度と経度を用いて地域の範囲(面)をクエリとして与え、そのクエリで与えられた面と、建物の範囲を表す面の包含関係を計算します。
空間データベースは、既存の関係データベース(RDB: Relational Database)や分散キーバリューストア(KVS: Key Value Store)を用いて実現できます。RDBを用いる場合、空間情報をカラムとするテーブルを利用します。しかし、緯度や経度ごとにカラムを用意する場合、カラムごとに検索が発生するため、検索回数が2回となり検索効率が悪くなります。この解決方法として二次元情報向けの検索木(R-Tree⁽⁴⁾等)が提案されています。一方、分散KVSを用いる場合、Key-Value構造のテーブルのキーに格納できるデータ数は1つだけとなるため、空間情報のような多次元情報は、そのままでは格納できません。この解決方法として、「空間重点曲線」を用いて多次元情報を一次元情報に変換する方法が提案されています。特に、空間情報の一次元化では、空間重点曲線の1つであるZ曲線を用いて一次元化する「ジオハッシュ⁽⁵⁾」がもっとも用いられています。その理由として、一次元化された空間情報の長さを変えて、表現できる空間の範囲を拡大・縮小できるズーム効果が挙げられます(図2)。本稿では、このジオハッシュを用いて一次元化された空間情報を「空間コード」と呼びます。
時空間データベースは、このRDBや分散KVSを用いた空間データベースで時間情報も管理できるようにすることで実現できます。しかし、数千万人のヒトや数千万台のコネクティッドカー等、膨大な数の動的オブジェクトを対象とする場合、移動によって頻繁に位置や時刻が変わります。この結果、RDBのような検索木を用いる場合、データ格納時に検索木の更新が頻繁に発生するため、データ格納の処理効率が低下します。そこで、膨大な数の動的オブジェクトの時空間データベースは、RDBを用いるよりも、このような検索木の更新が発生しない分散KVSを用いるほうが適していると考えられます。
次に、この分散KVSを用いてSICが開発した時空間データ高速検索技術を説明します。

時空間データ高速検索技術は、実空間上の大量の動的オブジェクトが収集したセンサ情報と、そのセンサ情報に紐付けられた時間情報と空間情報を格納しつつ、ある特定の時間情報と空間情報を矩形範囲で指定して、そこに含まれるセンサ情報を高速に検索する技術です。特に、本技術は、分散KVSとSICが提案する「時空間コード」と「限定的ノード選択アルゴリズム」を用いることにより、以下の要件を満たします。

1. 多次元情報検索の効率化：「時空間コード」を分散KVSのキーとして用いることにより、時間、緯度、経度、高度等から構成される多次元情報の検索を1…

1. (1)A. Isomura: “Real-time spatiotemporal data utilization for future mobility services、”RedisConf19, Jun 2019。
2. (2)T. Abraham and J. F. Roddick: “Survey of Spatio-Temporal Databases、”GeoInformatica, Vol.3, No.1, pp.61-99, 1999。
3. (3)N. Pant, M. Fouladgar, R. Elmasri, and K. Jitkajornwanich: “A Survey of Spatio-Temporal Database Research、”LNCS, Vol. 10752, 2018。
4. (4)M. Hadjieleftheriou, Y. Manolopoulos, Y. Theodoridis, and V. J. Tsotras: “R-Trees: A Dynamic Index Structure for Spatial Search-ing、”2017。
5. (5)https://blog.labix.org/2008/02/26/geohashorg-is-public