fbpx

CL LAB

HOME > Blog > Ippei Suzuki > Neo4j at TomTom(地図ナビゲーションにNeo4jを採用した事例)

Neo4j at TomTom(地図ナビゲーションにNeo4jを採用した事例)

 ★ 15

neo4j_blog001

テーマ:グラフデータベースを利用してナビゲーションが出来る燈籠のネットワークを構築する

neo4j_blog002

Peter Calliau: Software Devolper @ TomTom

neo4j_blog003

渋滞の履歴データを利用して、運転ルートを算出アルゴリズムを長年研究

neo4j_blog004

TomTomという会社:
グローバルで地図情報とナビゲーションシステムを開発する会社
3500人の従業員がいて、グローバルに点在する
本社はアムステルダム
開発拠点はPune, IndiaLebanon, New Hampshire (US)が中心

 

会社は4つのビジネスユニットを持つ

 

一つ目はコンシューマビジネス(最も知られている部門)

neo4j_blog005

PNPを製造:10年の歴史
TomTomスポーツウォッチも製造

 

2つ目は自動車部門

neo4j_blog006

インダッシュナビゲーションシステムを開発

 

 

3つ目はライセンス事業

neo4j_blog007

地図情報などはこの分野。さらに
TomTom Traffic等、交通情報を提供するシステム
TomTom IQ Route: ベストなルートを算出するアルゴリズム

4つ目はテレマティクス

neo4j_blog008

Fleet Management等、運行管理を制御するシステム

 

neo4j_blog009

Neo4jを使っているのはMap Editing Process: 地図情報を編集する機能

 

neo4j_blog010

これがMap Editorのスクリーンショット
3次元の画像もある。

neo4j_blog011

処理の手順
カメラマン(DCA)が撮影した画像を取り込む。
UIツールを使って地図に対して変更を加える
変更点は、Core Map APIに対して入力される
変更点は、QAシステムを通して、内容の審査が行われる
審査が合格したのち、本番運用システムに対して変更があてがわれる

このようなステップは、本番運用システムを常に稼働状態に維持するために取り入れている。

 

neo4j_blog012

QAチェックのサンプル

neo4j_blog013

例:交差点に一方通行サインの矛盾:graveyard(墓場)と呼ぶ

neo4j_blog014

例:ロータリーの方向(国によって異なる)

言葉のチェックも行う(言語によって道路標識等の表現方法がかなり違うらしい)

 

neo4j_blog015

最も工数のかかるQAチェック項目

 

neo4j_blog016

Restricted Access Island: ローカルではルート処理できるがグローバルでは到達する事ができなもの(意味不明)

neo4j_blog017

図での解説:ノード(丸)は交差点、エッジ(線)は道路
この図では、次が明らか
緑の領域以内であれば自由にナビゲーションできる
赤の領域内も自由にナビゲーション可能
任意の緑から赤の点にも行く事は可能
任意の赤の点から緑の点には移動不可能

 

neo4j_blog018

この問題を解説するためにはRAI(Restricted Access Island)アルゴリズムを知る事が必要

 

neo4j_blog019

このアルゴリズムの例:
青の道は他と繋がっている道
緑の道はローカルな道

 

neo4j_blog020

また、ロードカテゴリー、という概念も理解する必要が有る。
地元の細かい道路はカテゴリーが低い
高速道路などはカテゴリーは高い。

 

neo4j_blog021

TomTomのRoute Plannerを使ったナビゲーション例

 

neo4j_blog022

それをグラフに表したもの
サンフランシスコ市内の会場から、Mountain Viewのオフィスに向かうルート
通常は、会場を出てカテゴリーの低いローカル道路を通る
すぐにカテゴリーの高い高速道路に乗る
Mountain View近くになると、カテゴリーの低い道路に降りる
目的地に近づくとさらにカテゴリーの低い道に推移する

 

neo4j_blog023

RAIアルゴリズムとは、この例のように、A地点からB地点に行く際に、必ず、カテゴリーの低い道から高い道に推移し、目的地に近づくと、逆にカテゴリーの高い道から低い道に推移するパターンを通り、というルールに基づく。
この方法が必ず早い、というわけでは無い==>最も論理的な方法である、という事

 

neo4j_blog024

QA工程で必要なのは、この工程の初期段階(サンフランシスコ市内)の地図情報に変更を加えた場合、上記のRAIアルゴリズムに基づいたナビゲーションが算出可能なのかどうか、というテストである。

 

neo4j_blog025

この図のような変更の場合は、RC3からRC4への移動がRAIアルゴリズムに基づいて推移できるので、RAI(Restricted Access Island)ではなく、問題なく地図に組み込む事ができる。

 

neo4j_blog026

このような変更が加わった場合には、RAIの問題が発生する
左の図の場合は明らか一方通行が加わるので、RC4の領域に入る事ができない、という矛盾が発生する。
右の図の場合は、RC2からスタートする路線は、RAIアルゴリズムに基づいて自分より低いカテゴリーの道に推移する事ができ無いので、RAIアルゴリズムの基づいたナビゲーションの算出ができなくなる。

neo4j_blog027

従って、このような問題を摘出するためには、明確なルールの定義が必要になってくる。

 

neo4j_blog028

地図に変更を加えた場合のQA作業において、これらの問題を検出するために、Breadth First Searchという手法をとる。
これは、任意のスタート地点から任意のゴール地点に対してルートを算出する際に、RAIアルゴリズムに基づいてロードカテゴリーを網羅的に検索する手法

 

neo4j_blog029

この作業は非常に重要であるが、どれだけネスト深く検索をするかによって、そのルート算出能力の精度(完成度)が決まってくる。
図は、ルートの深さを、6層、10層、30層、130層と変える事によって、ルートチェックのカバー率が変わるグラフ。
TomTomの地図データに関しては、130層までチェックすると、99%に達する。
FacebookのようなSNSの場合は、だいたい7層までカバーすれば誰とでもつながるが、地図の場合はネストが著しく深い、という点が特徴

 

neo4j_blog030

QA工程を見積もる場合は、グラフの密度も考慮する必要もあるが、それを計算する方程式がこれ。
0〜1の値を出すが、SNSの場合は密度が非常に濃いのに対して、地図情報は非常に分散している、という特徴もある。

 

neo4j_blog031

Neo4jを選択した理由

 

neo4j_blog032

元はRDBで地図情報を全て運用してた。
位置情報も含めてRDBでデータモデル化
地図情報の一つの変更に対して、平均的なQAにかかる時間は40秒
チェックのネストの深さは100層までに制限:全体のルートの97%をカバー
新規に報告された問題点は個別に追加

 

neo4j_blog033

これをビジュアライズするツールとして、Zipkinを使用。
Twitterで使われている、分散トレーシングシステム
様々な分散サービスの所用時間を収集して表示するツール
これによると、データの処理に以上に長い時間がかかる事が判明
結果として、データモデリングをグラフする事が必要、という判断につながった

 

neo4j_blog034

地図情報をグラフ化する事によって偉れるメリット事例
これはヨーロッパのとあるロータリーの写真

 

neo4j_blog035

このロータリーをグラフ表示すると図のようになる。
実際には5つのロータリーが組み合わさっている
ルートの可視化が非常に簡単になる

 

neo4j_blog036

Neo4jへの移行:
地図情報と、ナビゲーションに必要なデータを全てRDBからNeo4jに移行
Neo4jのデータベースはインスタンス一つで管理可能
結果として、変更に対する平均的な検査時間は、5.2秒と大幅に短縮
チェックするネストの深さも従来の100層、という制限も無くし、100%のカバー率
従って、全てのRAI問題を解決する事に成功

 

neo4j_blog037

Neo4jの利用モデル
Embeddedモデル
HA機能を採用
上位に独自のSemanticレイヤーを開発、独自のアルゴリズムの開発の寄与
アルゴリズムは全てJavaで書く

 

neo4j_blog038

採用したグラフモデルは図のとおり
赤い点は交差点
線は道路(一方通行は矢印で指定)
黄色い点はManeuver地点

 

neo4j_blog039

Neo4jから学んだ事

 

neo4j_blog040

Blueprints APIを採用
もし、別のグラフデータベースを採用したい場合に、Blueprints仕様を通して移行が可能

 

neo4j_blog041

RDBとNeo4jの共存は運用管理工数が必要
データの同期を保全するためにデータベース間の2 phase commitを行っている
Neo4jのアルゴリズム開発よりもずっと時間がかかっている

 

neo4j_blog042

アプリのコードをデータの方に持っていく事の重要性

 

neo4j_blog043

今後の計画
チェックの件数をより細かくする:精度の高いルート検索を実現
Crawling Agents: 地図情報をクローリングし、潜在的な問題を検出するツールの開発

デモ

 

neo4j_blog044

ベルギー市内のルートマップ
真ん中の黒っぽいところがブリュッセル

 

neo4j_blog045

ルートの整合性検査を実際に動かしてみる。
データベースのサイズはかなり大きいが、ベルギー全体のチェックは約4分で終了する
毎秒600の道路情報を処理している

 

neo4j_blog046

チェックされているルートが緑色に表示される。

CL LAB Mail Magazine

CL LABの情報を逃さずチェックしよう!

メールアドレスを登録すると記事が投稿されるとメールで通知します。

メールアドレス: 登録

※登録後メールに記載しているリンクをクリックして認証してください。

Related post