Neo4j at TomTom（地図ナビゲーションにNeo4jを採用した事例）
この記事は1年以上前に投稿されました。情報が古い可能性がありますので、ご注意ください。
テーマ：グラフデータベースを利用してナビゲーションが出来る燈籠のネットワークを構築する
Peter Calliau: Software Devolper @ TomTom
渋滞の履歴データを利用して、運転ルートを算出アルゴリズムを長年研究
TomTomという会社：
グローバルで地図情報とナビゲーションシステムを開発する会社
3500人の従業員がいて、グローバルに点在する
本社はアムステルダム
開発拠点はPune, IndiaLebanon, New Hampshire (US)が中心
会社は4つのビジネスユニットを持つ
一つ目はコンシューマビジネス（最も知られている部門）
PNPを製造：10年の歴史
TomTomスポーツウォッチも製造
2つ目は自動車部門
インダッシュナビゲーションシステムを開発
3つ目はライセンス事業
地図情報などはこの分野。さらに
TomTom Traffic等、交通情報を提供するシステム
TomTom IQ Route: ベストなルートを算出するアルゴリズム
4つ目はテレマティクス
Fleet Management等、運行管理を制御するシステム
Neo4jを使っているのはMap Editing Process: 地図情報を編集する機能
これがMap Editorのスクリーンショット
3次元の画像もある。
処理の手順
カメラマン(DCA)が撮影した画像を取り込む。
UIツールを使って地図に対して変更を加える
変更点は、Core Map APIに対して入力される
変更点は、QAシステムを通して、内容の審査が行われる
審査が合格したのち、本番運用システムに対して変更があてがわれる
このようなステップは、本番運用システムを常に稼働状態に維持するために取り入れている。
QAチェックのサンプル
例：交差点に一方通行サインの矛盾：graveyard(墓場）と呼ぶ
例：ロータリーの方向（国によって異なる）
言葉のチェックも行う（言語によって道路標識等の表現方法がかなり違うらしい）
最も工数のかかるQAチェック項目
Restricted Access Island: ローカルではルート処理できるがグローバルでは到達する事ができなもの（意味不明）
図での解説：ノード（丸）は交差点、エッジ（線）は道路
この図では、次が明らか
緑の領域以内であれば自由にナビゲーションできる
赤の領域内も自由にナビゲーション可能
任意の緑から赤の点にも行く事は可能
任意の赤の点から緑の点には移動不可能
この問題を解説するためにはRAI(Restricted Access Island)アルゴリズムを知る事が必要
このアルゴリズムの例：
青の道は他と繋がっている道
緑の道はローカルな道
また、ロードカテゴリー、という概念も理解する必要が有る。
地元の細かい道路はカテゴリーが低い
高速道路などはカテゴリーは高い。
TomTomのRoute Plannerを使ったナビゲーション例
それをグラフに表したもの
サンフランシスコ市内の会場から、Mountain Viewのオフィスに向かうルート
通常は、会場を出てカテゴリーの低いローカル道路を通る
すぐにカテゴリーの高い高速道路に乗る
Mountain View近くになると、カテゴリーの低い道路に降りる
目的地に近づくとさらにカテゴリーの低い道に推移する
RAIアルゴリズムとは、この例のように、A地点からB地点に行く際に、必ず、カテゴリーの低い道から高い道に推移し、目的地に近づくと、逆にカテゴリーの高い道から低い道に推移するパターンを通り、というルールに基づく。
この方法が必ず早い、というわけでは無い＝＝＞最も論理的な方法である、という事
QA工程で必要なのは、この工程の初期段階（サンフランシスコ市内）の地図情報に変更を加えた場合、上記のRAIアルゴリズムに基づいたナビゲーションが算出可能なのかどうか、というテストである。
この図のような変更の場合は、RC3からRC4への移動がRAIアルゴリズムに基づいて推移できるので、RAI(Restricted Access Island)ではなく、問題なく地図に組み込む事ができる。
このような変更が加わった場合には、RAIの問題が発生する
左の図の場合は明らか一方通行が加わるので、RC4の領域に入る事ができない、という矛盾が発生する。
右の図の場合は、RC2からスタートする路線は、RAIアルゴリズムに基づいて自分より低いカテゴリーの道に推移する事ができ無いので、RAIアルゴリズムの基づいたナビゲーションの算出ができなくなる。
従って、このような問題を摘出するためには、明確なルールの定義が必要になってくる。
地図に変更を加えた場合のQA作業において、これらの問題を検出するために、Breadth First Searchという手法をとる。
これは、任意のスタート地点から任意のゴール地点に対してルートを算出する際に、RAIアルゴリズムに基づいてロードカテゴリーを網羅的に検索する手法
この作業は非常に重要であるが、どれだけネスト深く検索をするかによって、そのルート算出能力の精度（完成度）が決まってくる。
図は、ルートの深さを、6層、10層、30層、130層と変える事によって、ルートチェックのカバー率が変わるグラフ。
TomTomの地図データに関しては、130層までチェックすると、99％に達する。
FacebookのようなSNSの場合は、だいたい7層までカバーすれば誰とでもつながるが、地図の場合はネストが著しく深い、という点が特徴
QA工程を見積もる場合は、グラフの密度も考慮する必要もあるが、それを計算する方程式がこれ。
0〜1の値を出すが、SNSの場合は密度が非常に濃いのに対して、地図情報は非常に分散している、という特徴もある。
Neo4jを選択した理由
元はRDBで地図情報を全て運用してた。
位置情報も含めてRDBでデータモデル化
地図情報の一つの変更に対して、平均的なQAにかかる時間は40秒
チェックのネストの深さは100層までに制限：全体のルートの97％をカバー
新規に報告された問題点は個別に追加
これをビジュアライズするツールとして、Zipkinを使用。
Twitterで使われている、分散トレーシングシステム
様々な分散サービスの所用時間を収集して表示するツール
これによると、データの処理に以上に長い時間がかかる事が判明
結果として、データモデリングをグラフする事が必要、という判断につながった
地図情報をグラフ化する事によって偉れるメリット事例
これはヨーロッパのとあるロータリーの写真
このロータリーをグラフ表示すると図のようになる。
実際には5つのロータリーが組み合わさっている
ルートの可視化が非常に簡単になる
Neo4jへの移行：
地図情報と、ナビゲーションに必要なデータを全てRDBからNeo4jに移行
Neo4jのデータベースはインスタンス一つで管理可能
結果として、変更に対する平均的な検査時間は、5.2秒と大幅に短縮
チェックするネストの深さも従来の100層、という制限も無くし、100％のカバー率
従って、全てのRAI問題を解決する事に成功
Neo4jの利用モデル
Embeddedモデル
HA機能を採用
上位に独自のSemanticレイヤーを開発、独自のアルゴリズムの開発の寄与
アルゴリズムは全てJavaで書く
採用したグラフモデルは図のとおり
赤い点は交差点
線は道路（一方通行は矢印で指定）
黄色い点はManeuver地点
Neo4jから学んだ事
Blueprints APIを採用
もし、別のグラフデータベースを採用したい場合に、Blueprints仕様を通して移行が可能
RDBとNeo4jの共存は運用管理工数が必要
データの同期を保全するためにデータベース間の2 phase commitを行っている
Neo4jのアルゴリズム開発よりもずっと時間がかかっている
アプリのコードをデータの方に持っていく事の重要性
今後の計画
チェックの件数をより細かくする：精度の高いルート検索を実現
Crawling Agents: 地図情報をクローリングし、潜在的な問題を検出するツールの開発
デモ
ベルギー市内のルートマップ
真ん中の黒っぽいところがブリュッセル
ルートの整合性検査を実際に動かしてみる。
データベースのサイズはかなり大きいが、ベルギー全体のチェックは約4分で終了する
毎秒600の道路情報を処理している
チェックされているルートが緑色に表示される。
