Engineering journal
Mapsakeがオフラインの旅行地理情報集を作成する方法。
写真の座標を国、地域、都市、および空港に変換するには、最寄りの場所の検索だけでは不十分です。Mapsakeは、オープンな場所データ、境界ジオメトリ、決定論的なルール、およびローカルインデックスを組み合わせて実現しています。
座標はまだ場所ではありません。
旅行写真は、非常に高い精度で緯度と経度を含むことができます。しかし、その2つの数字だけでは、カメラが日本、京都府、京都市、または帰宅途中の関西国際空港に設置されていたかどうかはわかりません。Mapsakeは、その階層構造を必要としています。そうでないと、ポイントは役に立つ旅行記録にはなりません。
それらの質問に答えるコンポーネントは、地理的な名前付き場所の構造化されたディレクトリである地理 Gazetteer です。Mapsake は、国や1次地域の境界線に使用される境界線とともに、地理 Gazetteer をアプリ内にバンドルしています。検索、手動でのマーキング、写真のインポート、場所のストーリー、パスポートの統計、成果、さらにはいくつかの友達のビューも、これに依存しています。
すべての座標をウェブジオコーダーに送信する方が簡単だったかもしれません。しかし、これにより、大量の写真のインポートが遅くなり、ネットワーク環境に依存し、再現が難しくなり、プライバシーが低下します。オフラインルートの作成には、より多くの初期のエンジニアリングが必要でしたが、これにより、Mapsakeは、飛行機内、自宅、ソースデータセットが変更されてから数年後でも、同じように機能する安定した地理的語彙を提供できるようになりました。
このレイヤーがどのように構築されたか、ポイントと線が一致しない場合、そして「最寄りの都市」が正しい答えの始まりに過ぎない理由について説明します。
4つの公開データセット、4つの異なるタスク
Mapsakeに必要なすべての情報が単一のソースにまとまっているわけではないため、ビルドパイプラインは4種類のオープンデータとを組み合わせています。
- GeoNames 国、第一級行政区域、人口のある場所、安定した識別子、別名、座標、および人口を提供します。
- OurAirports 空港、IATAおよびICAOコード、名称、自治体、および座標を提供します。
- Natural Earth 国および admin-1 の境界ジオメトリと、便利な地図ラベル用ポイントを提供します。
- Mapsakeが所有する小さなレイヤーは、サポートされる国ごとのモード数、エイリアス、および一般的なソースから安全に推測できない製品の決定事項を記録します。
各データソースは、異なる機能に優れています。GeoNamesは、都市が地域と国に属していることを知っていますが、都市の座標は単なる1点であり、国境ではありません。Natural Earthは、ポリゴンがどこに描かれているかを知っていますが、そのフィーチャ識別子は、常にGeoNamesの識別子と一致するとは限りません。OurAirportsは、KLAXとLAXが同じ空港を指すことを知っていますが、空港周辺のすべての場所の階層構造ではありません。
ビルドスクリプトは、アップストリームファイルをダウンロードしてキャッシュし、正規化し、関連性を検証し、2つのコミット済みの成果物を作成します。それらは、読み取り専用のSQLiteデータベースと簡略化されたGeoJSONジオメトリです。アプリはこれらの結果を配布します。アプリは、初回起動時にワールドデータベースをダウンロードしたり、旅行中にソースサイトがオンラインになっていることを依存したりしません。
生成された成果物をコミットすることで、再現性を確保できます。 リリースされたビルドには、既知の地理的な世界が含まれています。 ソースコードの更新は、テストおよびレビュー可能な意図的なコード変更であり、誰かの地図を一夜にして変更する、目に見えないサーバー側の変更ではありません。
あえて退屈なSQLiteデータベース。
最初の地理データベースには、252カ国、3,861地域、33,744都市、そして4,564空港が含まれており、約14 MBのサイズでした。これは、オペレーティングシステムで既に提供されているSQLiteライブラリと、小さなローカルラッパーを使用しており、より大きなデータベースフレームワークを追加していません。
このスキーマは、意図的に直接的です。大陸は国を含み、国は地域を含み、地域は都市を含みます。空港には、国コードと座標が含まれます。安定したソース識別子は、Mapsakeマークに保存される識別子になります。国にはISO alpha-2、地域にはGeoNamesの管理コード、都市にはGeoNamesのID、空港にはIATAコードが使用されます。
Mapsake は、読みやすい名前と系統を各保存された場所に二重化します。この重複は役立ちます。個人的な旅行記録は、後で Gazetteer が場所の名前を変更したり、記録を削除したり、存在しなかったりする場合でも、読み取り可能である必要があります。識別子は一致に使用され、スナップショットはユーザーのデータを自己完結的に保ちます。
SQLiteは、このワークロードに適しています。なぜなら、データベースは一度生成され、何度もクエリされるからです。これは、インデックス、ビルド中のトランザクション、およびサービスプロセスなしでフルテキスト検索をサポートしています。アプリは、バンドルされたファイルを読み取り専用で開くため、参照データに対する移行のリスクはなく、中断された書き込みによってデータが破損する可能性もありません。
検索は「含む」という単純な検索ではありません。
手動でのマーキングは、大陸、国、地域、都市、および空港を網羅する単一の検索フィールドから開始されます。「san」という検索では、一般的な都市が、不明なレコードよりも優先されます。「LAX」という検索では、空港が検索されます。また、アクセント記号のない名前でも検索できるようにする必要があります。
このビルドは、表示名、選択された代替名、コード、系統、座標、種類、および重要度値を含む FTS5 テーブルを作成します。Unicode トークナイザーは、マッチングのためにダイアクリティカルマークを削除します。クエリ時には、Mapsake は大文字と小文字、およびダイアクリティカルマークを無視し、フルテキスト構文になりうる文字を削除し、各トークンにプレフィックスマッチを追加し、完全一致の名前をプレフィックスと一般的な一致よりも優先します。
優先順位は、残りの要素の決定に影響を与えます。大陸と国は、同様の名前の村よりも上位に表示されるべきではありません。都市の人口は、主要な場所に適切な重みを付与します。テキストの一致が同じ場合、大きな空港は小さな空港よりも上位にランク付けされます。
代替名は意図的に制限されています。 GeoNamesは、人気のある場所について、非常に長い多言語リストを提供できます。 すべてのスペルをデバイスのインデックスにコピーすると、ノイズとサイズが増加します。 ビルダーは、有用なバリエーションの限られた、重複排除されたセットを保持し、元の表示名を検索フォームとして折りたたんだものとは別に保持します。
検索結果は、階層的な閲覧で使用されるGazetteerPlaceモデルと同じものを使用します。ユーザーは直接検索することも、大陸、国、地域、都市を閲覧することもでき、2つの異なる地理システムを作成する必要はありません。
線は点とは異なる質問に答えます
最初の写真解決機能は、最寄りの都市を選択し、その都市の国と地域を継承しました。 密集した地域では、これは多くの場合、完璧に見えます。 国境の近くでは、気づきにくい方法で間違っている可能性があります。
例えば、モンタナ州の国境付近で撮影された写真があり、データベース内の最も近い人口密集地が北ダコタ州にある場合を想像してください。最寄りの都市の計算は正しく動作していますが、結果は写真が撮影された行政区域とは一致しません。同様の問題は、国際的な国境、囲い込み地域、および海岸線がまばらで近くに人口密集地がない水辺でも発生します。
境界のデータは、近接ではなく、包含を判断します。Mapsakeは、Natural Earthの国とadmin-1のポリゴンをデコードし、座標がどのリングに含まれているかを確認し、その結果を使用して国と地域の割り当てを保護します。次に、ポリゴンの国または地域に制限された最寄りの都市を検索できます。
これにより、有用な役割分担が生まれます。
- ポリゴン包含は、管理区域を確立します。
- Gazetteerの階層構造は、安定したIDと名前を提供します。
- 制約付きの最寄りの都市検索は、境界線を越えない有用な地域情報を提供します。
- 近くの空港のチェックでは、あらかじめ設定された短い距離内の空港のみが追加されます。
線データと場所ディレクトリは、それぞれ単独では不十分です。組み合わせて使用することで、座標が信頼できる経路として機能します。
admin-1 の監査により、体系的な不一致が明らかになりました。
国のポリゴンと地域のポリゴンは、Natural Earthの異なるレイヤーから取得されました。地域レイヤーの識別子は、常にGeoNamesと一致するとは限りませんでした。いくつかの不一致は明らかでしたが、他の不一致は妥当性がありましたが、不正確な表示となっていました。
ある初期の変換テーブルでは、ケベックにニューブランズウィックの地理情報が割り当てられていました。他の機能にはコードが欠けていたり、隣接するシステムからのコードが使用されていたり、または Gazetteer とは異なる管理単位として表現されていたりしました。世界地図を目視で確認しても、これらのエラーをすべて確実に特定できるわけではありません。
新しいモデルの状態では、都市をオラクルとして扱います。 各候補ポリゴンについて、そのポリゴン内に実際にどの地域の都市が含まれているかを問い合わせます。 既存の Natural Earth コードは、盲目的に信頼するのではなく、検証されます。 検証に失敗した機能は、空間的に再割り当てしたり、分割したり、除外したりできます。 生成された出力では、SQLite に既に存在する正確なリージョン ID が使用されます。
これは、クロスデータセットのテストの実際的な形式です。地域であると主張するポリゴンは、同じ地域であると主張する都市の説得力のあるサンプルを含む必要があります。2つのソースが異なる場合、ビルドは証拠を提供し、最初にロードされた値を静かに選択するのではなく、その違いを明らかにします。
同じ監査では、親国の地理に組み込まれている、人が住んでいる関連地域などの特殊なケースが検出されました。Mapsakeは、これらのケースの一部を修正し、写真が、ガゼッターや国数設定が認識する国と同じ国に解決されるようにしています。
ソースファイルサイズの世界データを使用せずに、よりシャープな線を表示します。
最初のAtlasは、Natural Earthの1:110万件の国境データレイヤーを使用しました。コンパクトで高速でしたが、Mapsakeがより詳細な地図、場所の物語、および地域情報を追加すると、海岸線が目に見えて粗くなるようになりました。
地図は、1:10百万層に移動しました。そのソースははるかに詳細であるため、変更せずにバンドルおよびレンダリングすると、ストレージ、デコード時間、オーバーレイの構築、および着色作業が増加します。ビルドパイプラインは、ダグラス・ペッカー法を使用して、おおよそ0.004度の許容範囲で各リングを簡略化し、次に座標を安定した精度で丸めます。
結果の国ファイルは約 6.5 MB です。 Mapsake が表示するズームレベルで役立つ海岸線の詳細を保持しながら、実質的に同じピクセルに配置される頂点を削除します。 Admin-1 ジオメトリも、同様の検証と簡略化のパスを経ます。
簡略化には正確性の制約があります。小さなポリゴンであっても、実際の写真の座標に対して同じ判断を下す必要があります。後で作成されたベンチマークテストでは、意図的に境界線付近に点を配置し、最適化されたヒット検出と、変更されていない参照データとの比較を行っています。高速な線は、同じ包含関係を判定できる場合にのみ有効です。
34,000 から 234,000 までの都市を対象に拡大します。
最初のデータベースでは、人口が15,000人以上のGeoNamesの都市を使用しました。これにより、バンドルサイズはコンパクトになりましたが、農村部の旅行、小さな島、ハイキングタウン、そして多くの自宅の場所で、不必要に遠いラベルが表示されるようになりました。
Mapsakeは、その後、GeoNamesを採用しました。 都市500, は、おおよそ 500 人以上の人口を持つ場所と、行政機関の所在地をカバーしています。都市テーブルは約7倍の約 234,000 件のレコードに増加し、バンドルされたデータベースは約 14 MB から約 69 MB に増加しました。
その取引は、App Clipが削除された後に実施されました。Clipのダウンロード制限は、データベースを制限する最も強い理由でした。メインアプリのみがコンシューマーになったため、より広範囲なカバレッジは、人工的な小都市の制限を維持するよりも価値がありました。
フルテキストインデックスは、マイナーな場所の代替名に対して選択的に動作し、地域ごとの閲覧では、一度に表示される量を制限します。データは広範囲に及ぶ可能性がありますが、すべての画面でテーブル全体を表示する必要はありません。
カバー範囲は、ネットワークジオコーダーが最も信頼できない場所で最も重要です。遠隔地にある小さな町は、コンパクトなデータセットに記載されていないため、何時間もかかる都市として誤って表示されるべきではありません。
最寄りの都市の検索は、共有パフォーマンスの問題になりました。
元の最寄りの都市の検索では、緯度と経度の範囲を広げ、SQLiteに各候補の加重距離を計算させ、一時的なソートを作成し、最も近い行を返していました。理解しやすく、十分に正確でしたが、82,000の写真ライブラリでは、小さなクエリごとのコストが、インポート、思い出、地図の生成、Constellationsにおける繰り返しの作業で数秒に膨らんでいました。
最初の改善点では、広いフォールバックの前に、狭い0.4度の範囲を検索するようにしました。密集した地域では、通常、はるかに小さい候補セットから都市が見つかります。メモ化と、永続的な地理的セルキャッシュにより、近くの写真が同じ作業を繰り返すことがなくなりました。
より大きな改善点は、234,000の都市の数値座標を緯度でソートされたインメモリインデックスにロードすることです。二分探索は、現在の緯度ウィンドウ内のスライスを見つけ、境界付きループは経度と加重距離を確認し、SQLiteから勝者の行のみが取得されます。小さなレコードキャッシュにより、繰り返し発生する勝者は安価になります。
動作は変更されていません。最適化された関数は、依然として最初の空でない検索ウィンドウで最も近い都市を選択し、決定論的なタイブレークを使用します。古いSQLパスのベンチマーク専用のコピーは、境界が豊富な数百の座標について、正確なIDの一致をチェックします。
シミュレーターでは、中程度の近隣都市のバッチ処理時間が、2.11秒から5.2ミリ秒に短縮されました。実際のiPhoneでは、3.06秒から6.35ミリ秒に短縮されました。これらの改善により、インポート画面のプライベートな実装詳細ではなく、共有インフラストラクチャであるガゼッターが使用されるため、いくつかの機能が向上しました。
重複するポリゴンが見つかり、これはバグです。
パフォーマンスの同等性チェックにより、最適化前に存在していたバグが明らかになりました。一部のadmin-1ポリゴンは、特に首都圏が周辺地域に含まれる場合、意図的に重なり合います。ベルリンとブランデンブルク、ソウルと京畿道、およびキーウ市とそのオブラストがその例です。
以前のヒットテストでは、Swiftの辞書内で最初に一致したポリゴンが選択されていました。辞書の反復順序はプロセス間で変化するため、同じ座標が再起動後に別のリージョンを指す可能性があります。
Mapsakeは、現在、重なり合う候補を、ポリゴンの面積でソートし、最も小さく、最も具体的な特徴が優先されるようにしています。参照実装も同じルールに従います。82,000の写真を使用した固定されたテストケースは、コールドとウォームの両方の派生パスで、差がゼロになるようにする必要があります。そうでない場合、ジオメトリの最適化は受け入れられません。
このバグは、ポリゴンの「内側」が常に「はい」または「いいえ」の答えではないことを思い出させるものです。地理データには、エクレク、ネストされた首都、反時計回り、多角形、穴、係争境界、およびソースの慣習が含まれます。決定論的なポリシーは、多角形内アルゴリズムと同じくらい重要です。
オフラインモードは、プライバシー機能であり、製品機能でもあります。
Mapsake の写真インポート機能は、座標をサードパーティのジオコーディングサービスに送信することなく、大量のライブラリを処理できます。これにより、プライベートな旅行先や自宅の場所が保護され、リクエストごとの料金が発生しなくなり、処理速度が安定します。
また、編集をより一貫性のあるものにします。手動検索、写真のインポート、Passportカード、成果、Friendsのスナップショット、スタンプのマッチング、および場所のストーリーは、同じ安定した場所IDを使用するため、同じ言語で表現されます。フライトログからインポートされた空港は、写真の近くで検出された同じ空港と重複を解消できます。検索によって見つかった都市は、Then & Nowで使用される都市と一致できます。
バンドルは、完璧または永続的なものとして扱われません。ソースの帰属はアプリ内で表示されます。ビルドスクリプトはコードの横に保持されます。既知の修正は明示的に示されています。ベンチマークのテストデータは、困難な座標での動作を保護します。地理的な世界の更新は、レビュー可能な影響を伴うリリースイベントです。
もし再構築するとしたら、何を残したいですか？
最も耐久性のある選択肢は、個々のアルゴリズムではありませんでした。それらは、責任の境界でした。
- 名前、安定した識別子、検索、および階層構造のために、ポイントを使用します。
- 包含のために、線と多角形を使用します。
- 携帯電話で4つの異なる形式を解析する代わりに、読み取り専用の製品ファイルを作成します。
- ユーザーデータを含む読み取り可能なスナップショットを保存し、ソースIDを保持して一致させます。
- 高速化する前に、一般的なオフラインパスを決定論的にします。
- 最適化された出力が同等であることを証明するまで、参照実装を十分に長く維持する。
Gazetteerは、当初は検索機能として始まりました。これは、Mapsakeの重要なシステムの一つになりました。なぜなら、ほとんどの高度な機能は、同じ基本的な質問に答える必要があるからです。それは、「これはどの場所ですか？」
正しい回答を得るためには、地理が単一のデータベースや巧妙なクエリではないことを理解する必要があります。それは、名前、ポイント、線、製品ルール、そしてユーザーが認識することを期待する旅行記録との慎重な合意です。