実空間上のヒトやモノ、自然環境等に関するさまざまな情報の収集とクラウド上での一元管理を可能にするIoT（Internet of Things）技術は、ヒトや車などの「動的オブジェクト」を管理することが求められる次世代サービス（レーン単位での渋滞把握、密なルートを回避する経路探索、ドローンによる空中配送など）では必要不可欠となってきています。トヨタ自動車との協業においても「障害物検知ユースケース」という、道路上の障害物の情報を即座に周辺の車両に通知するサービスの実現に向けて、「大量に走行する車両からのリアルタイムデータ格納」および「ある時間・空間に存在する車両のリアルタイム検索」が必要不可欠でした。
NTT人間情報研究所では、これら次世代サービスの実現で必須となる、大量の動的オブジェクトが一斉送信する情報の蓄積と、蓄積した動的オブジェクトの中から、ある時刻にある特定の地域にいる動的オブジェクトをリアルタイムに検索する「高速時空間データ管理技術Axispot^®＊1^{（1）（2）}」に取り組んでいます（図1）。以降では、既存技術が直面している4つの技術課題を提示し、これら技術課題の解決に向けて提案するAxispot^®の4つのコア技術を紹介します。また、これら技術による性能改善を評価し、最後に、本研究開発のさらなる発展に向けて現在取り組んでいる課題や、今後の展望を述べます。

＊1　Axispot^®：多次元の軸（Axis）からデータを高速に特定（Spot）する時空間データ管理技術（商標：https://www.j-platpat.inpit.go.jp/t0201）。

「時空間データベース」とは、緯度や経度といった空間情報と、時刻、期間といった時間情報の双方に関連付いたデータ群を効率的に蓄積・検索・抽出するためのデータベースです^{（3）（4）}。空間情報を用いて時空間データベースに対して検索を行う場合、ある特定の形状（道路、駐車場など）の範囲内に存在するオブジェクトのみを検索することを「ポリゴン検索」といいます。本協業の「障害物検知ユースケース」を実現するには、膨大な数の車両が全国で生成するデータを「時空間データベース」に格納し、さらに、特定の車両のみを「ポリゴン検索」により抽出する必要があります。しかし、本協業の性能目標を達成するには、次の4つの技術課題が発生します。
・課題①：一般的な時空間データベースでは、リレーショナルデータベース（RDB）などで汎用的に利用される検索木＊2を応用したインデックスを用意します。しかし、検索木を用いる場合、データを格納・削除する際に検索木の更新が発生します。これにより、数1000万台という膨大な数の車両を取り扱う場合、データ格納・更新・削除の処理効率が著しく低下してしまい、リアルタイムで格納することが困難となります。
・課題②：大量のデータを扱う場合、データベースを複数のサーバで構成する分散データベースを用意します。この際、通常は各サーバが管理するデータを地域ごとに決定します。しかし、車両は地域・時間帯ごとに稼動している台数が異なるため、分散データベースを構成するサーバ間でデータ量が大きく偏ります。これにより、一部のサーバに負荷が集中することから処理性能が著しく低下し、リアルタイムでの格納・検索が困難となります。
・課題③：ポリゴン検索の計算性能は、対象とするポリゴンの「頂点数が多ければ多いほど」速度が低下します^（5）。一方で、近年普及し始めている「高精度地図＊3」が提供するポリゴンは高精細、つまり頂点数が多いという特徴があります。そのため、高精度地図を基につくられたポリゴンを活用したポリゴン検索の速度は遅く、リアルタイムでの検索が困難となります。
・課題④：データベースに集められた時空間データを基に、全国の各道路に存在する車両数を集計する場合、集計範囲内の地域メッシュやポリゴン数を「走行中の車両台数に応じて」計算機に割り当てる必要があります。この場合、多くの既存サービスでは、あらかじめ「地域メッシュ」や「ポリゴン数」を手動で割り当てます。しかし、先述したように、車両は地域・時間帯ごとに稼動している台数が異なるため、各計算機のジョブ＊4の量が大きく偏り集計が非効率的になってしまいます。

＊2　検索木：r-treeなどのツリー構造を持つデータ索引のためのインデックス技術。
＊3　高精度地図：道路の各レーン単位の情報などを持つ高精細な地図データ。HD（High Definition）-mapとも呼ばれます。
＊4　ジョブ：処理作業のまとまりのこと。

ここでは、前述した技術課題①〜④の解決に向けてNTT人間情報研究所が提案する4つの技術について説明し、最後にAxispot^®全体のアーキテクチャを紹介します。

本技術は、ツリー構造を使わず、モートン曲線という空間充填曲線の特性を応用したインデックス方式です。図2の左側に示す2次元のモートン曲線は、世界地図に対して4分割を繰り返し、分割された領域に対して［0］、［1］というビットを付与するような処理となります。この［0］と［1］のみで構成される1次元のビット配列が長くなるにつれて、空間的に狭い領域が表現されます。そして、このビット配列に対する前方一致検索により、空間の範囲検索が可能となります。例えば、［1001…］という前方ビットを検索すると、図2の世界地図における黄色枠内を検索することができます。私たちは、このような特性を持つモートン曲線に「時間」という次元を追加し、3次元のモートン曲線に拡張しました。さらに、生成されたビット配列をキーバリューストア（KVS）と呼ばれるデータベースの「Key」と「Value」に「前方ビット」「後方ビット」をそれぞれ図2の右側に示すように分割して格納することで、時空間の範囲検索を「Keyへの完全一致検索」により実現しました。この「時空間インデックス技術」により、ツリー構造を使わず高速なデータ格納を実現し、さらにリアルタイムでの時空間範囲検索を可能とします。

本技術は「場所と時刻に応じて、複数のサーバの組合せを決定し、そのうちどれか1つのサーバにデータを振り分ける」という新たなデータ分散方式です。このデータ分散方式により、図3に示す3つの効果が得られます。①地域に応じて特定の1つのサーバではなく複数のサーバが選択されることで負荷を平準化できます。②時間経過に伴い、選択される複数のサーバの組合せが変化するため連続的な負荷を回避できます。③検索時には「時間」と「空間」によりサーバの組合せを一意に特定できるので、すべてのサーバへの不要な検索を回避できます。この「限定的ノード選択技術」により、一部のサーバに「負荷集中」が発生してしまうことを回避し、高速な格納・検索を可能とします。

本技術は「折れ線」の簡易化手法の1つであるDouglas-Peuckerアルゴリズム^（6）を「ポリゴン形状」に適用することで、元のポリゴン形状を保持しながらポリゴンの頂点数を大幅に減らし、ポリゴン検索を高速化する方式です。図4のポリゴン（生データ）に対してDouglas-Peuckerアルゴリズムを適用することで、大幅に頂点数が削減されたポリゴン（提案技術）を生成します。この変換処理を適用した後、ポリゴンを効率的にデータベースで管理する「高速ポリゴン検索技術」により、高精度地図を基に作成されたポリゴンを活用したポリゴン検索の速度が低下することを回避し、リアルタイムでの検索を可能とします。

本技術は、分散処理基盤を活用することで、時空間データの集計対象範囲内のジョブを自動で各計算機に配分するという方式です。図5に示すように、ある空間範囲に対して地域メッシュで集計処理を実行する場合、地域メッシュの位置は空間的にバラバラになりますが、各計算機が担当する「ジョブの量が均等になる」ように振り分けます。この「時空間データ高速集計技術」により、各計算機のジョブの量が大きく偏ることを回避し、集計に要するレスポンス時間を短縮することを可能とします。
Axispot^®はこれら4つの技術を核としており、図6に示すアーキテクチャで構成されています。図中に示す「時空間データベース」は時空間データを格納するためにRedis^（7）やApache Ignite^（8）などを利用することができ、「静的ポリゴンデータベース」はポリゴン情報を格納するためにPostgreSQL^（9）などのオープンソースソフトウェアを利用することができます。

ここでは、同一のデータベースを利用した場合に、「時空間インデックス技術」「限定的ノード選択技術」を利用した場合（提案技術）と利用しなかった場合（既存技術）の比較を示します。検証では、関東規模を常時走行する数100万台規模の車両のデータを収集し、さらに特定の空間・時間内に存在する車両のみを検索することを想定したデータセットを利用しました。図7（左）に示すように、格納性能は3.1倍に向上し、検索性能は246倍にまで向上することを確認しました。また、図7（右）に示すように、提案技術を利用した場合は分散データベースを構成する各サーバに均等にデータが割り振られることから、負荷集中を回避することを確認しました。本技術を協業の場で活用することで、リアルタイムでの車両データ格納・検索の実現に貢献することができました。

NTT人間情報研究所では、現実世界のあらゆる物体を仮想空間にリアルタイムでコピーする「デジタルツインコンピューティング^（10）」という技術に取り組んでいます。これを実現するには、ヒト、車のみならずドローン、船舶、衛星などのあらゆる動的オブジェクトから一斉に送信されてくるデータをリアルタイムで格納・更新し、さらに都市（建物、道路など）・環境（河川など）といったあらゆる形状の中から必要なデータのみを検索することが不可欠です。そのため、現時点ではAxispot^®で対応できない「高さ」方向の次元へのインデックスの拡張や、「3次元ポリゴン」を用いた検索に関する取り組みを検討しています。

■参考文献
（1）　A. Isomura, I. Naito, Y. Iida, and T. Nakamura：“Axispot: A Distributed Spatial-Temporal Data Management System for Digital Twin of Moving Objects,”IEEE Software, Vol. 39, No. 2, pp. 33-38，2022．
DOI: 10.1109/MS.2021.3132899
（2）　A. Isomura, K. Miyahara, I. Naito, and M. Hanadate：“Real-Time Spatial-Temporal Database for Geographic Polygon Data Using HD-Map,”4th ICGDA，pp. 7-13，April 2021．
https://doi.org/10.1145/3465222.3465230
（3）　T．Abraham and J．F. Roddick：“Survey of Spatio-Temporal Databases,” GeoInformatica，Vol. 3，pp. 61-99，1999．
https://doi.org/10.1023/A:1009800916313
（4）　N．Pant，M．Fouladgar，R．Elmasri，and K．Jitkajornwanich ：“A Survey of Spatio-Temporal Database Research,” LNCS, Vol. 10752，pp. 115-126，2018．
（5）　I．E. Sutherland，R．F. Sproull，and R．A. Schumacker：“A characterization of ten hidden-surface algorithms,” ACM Computing Surveys, Vol. 6, No. 1，pp. 1–55，1974.
（6）　M. Visvalingam and J. D．Whyatt：“The Douglas-Peucker algorithm for line simplification: Re-evaluation through visualization,” Computer Graphics Forum, Vol. 9, No. 3, Sept. 1990．
https://doi.org/10.1111/j.1467-8659.1990.tb00398.x
（7）　https://redis.io/
（8）　https://ignite.apache.org/
（9）　https://www.postgresql.org/
（10）　https://group.ntt/jp/newsrelease/2020/11/13/201113c.html