Efficient encoding of points
まだ誰も着手していません。
評価
- 難易度
- 5/5
- 見積もり時間
- 1週間以上
- 初心者へのやさしさ
- 20/100
- issue の種類
- 機能追加
- 明瞭さ
- 説明が足りない
- 活発さ
- 停滞
- 領域
- data
調査の方向性
issue にある現在のポイントエンコーディングの例を確認し、記載されている繰り返しと、提案されているパック済みのデルタエンコード表現を比較してください。次の有用なステップは、サンプルの z15 ポイントデータを使った概念実証ですが、issue ではファイル、テスト、受け入れ基準が指定されていません。完了には、将来の仕様のメジャー改訂に向けた合意済みの設計が必要になります。
索引モデルが issue の本文から書いたものです。
説明
Encoding a huge number of points in VT is currently pretty inefficient in terms of output size. This is especially a big problem on the highest zoom levels where POIs and address points are encoded. Let's discuss what we could do about that in a future major spec revision to make encoding optimal.
This is how points are currently encoded in a layer:
{
"id": 3359,
"tags": [0, 561, 1, 123, 2, 456],
"type": 1,
"geometry": [9, 1050, 8692]
},
{
"id": 3360,
"tags": [0, 548, 1, 234, 2, 457],
"type": 1,
"geometry": [9, 1071, 8694]
},
{
"id": 3361,
"tags": [0, 549, 2, 458],
"type": 1,
"geometry": [9, 1072, 8693]
},
...
Problems with the current approach:
- each point is a separate message, so each needs at least two bytes for a tag + message length
- tag for each field (id, tags, type, geometry) is repeated over and over
- additionally, tags and geometry are packed fields so need 2 bytes for lengths
- the same type is repeated everywhere
- each geometry has a superfluous moveTo command
- the same key indexes are typically repeated over and over
- geometries are not delta-encoded
Some of the repetition gets compressed away by gzip, but there's still a lot of data we could eliminate with a smarter encoding approach. Here a rough idea how the sample above could be encoded optimally:
{
"id": [3359, 3360, 3361, ...],
"tags": [561, 123, 456, 548, 234, 457, 549, 0, 458, ...],
"geometry": [3336, 8692, 21, 2, 1, 1, ...]
}
- a set of points is one big message with a few packed fields
- ids are packed together
- tags are packed together and only have value indexes; each layer key has a corresponding value encoded, so if a particular key is not present in a feature, we encode 0 (this won't occur too often so the gain from dropping keys should far outweigh the need to include such zeroes)
- point geometries are packed together and delta-encoded (which should be a big size win); for efficiency of delta-encoding, we sort points before encoding (e.g. in a z-curve order, by a morton hash)
To understand how much of a win this will be in terms of compression, I'll make a quick proof of concept encoding on sample z15 point data and post back here.
cc @yhahn @springmeyer @flippmoke @kkaefer @tmcw @sgillies @ericfischer
- 主要言語
- 言語のデータがありません
- スター
- 1k
- フォーク
- 213
- PR マージ指標
- 30日以内にマージされた PR はありません
環境構築
- Dockerfile・Docker Compose ファイルなし
- プルリクエストのテンプレートなし
- コントリビューションガイドを読む
はじめの一歩
- issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
- 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
- リポジトリをフォークし、ブランチを切って変更します。
- issue 番号を参照したプルリクエストを送ります。
mapbox/vector-tile-spec のほかの issue
-
難易度 5/5 1週間以上 初心者へのやさしさ 25/100
mapbox/vector-tile-spec#157 ·
-
難易度 5/5 1週間以上 初心者へのやさしさ 20/100
mapbox/vector-tile-spec#153 ·
-
難易度 5/5 1週間以上 初心者へのやさしさ 25/100
mapbox/vector-tile-spec#149 ·
-
Typo in §4.4オープン
難易度 1/5 1時間未満 初心者へのやさしさ 55/100
mapbox/vector-tile-spec#148 ·
-
難易度 5/5 1週間以上 初心者へのやさしさ 20/100
mapbox/vector-tile-spec#145 · コメント 2 件 · リアクション 1 件 ·
mapbox/vector-tile-spec の issue をすべて見る
似ている issue
-
難易度 2/5 1〜3時間 初心者へのやさしさ 65/100
-
feedback
難易度 2/5 1〜3時間 初心者へのやさしさ 65/100
useagenthq/useagent#183 ·
メンテナーはふだん 2 日以内に返信
-
難易度 1/5 1時間未満 初心者へのやさしさ 68/100
openstreetmap/id-tagging-schema#3121 · コメント 1 件 ·
メンテナーはふだん 1 日以内に返信
-
bug
難易度 2/5 1〜3時間 初心者へのやさしさ 62/100
bioepic-data/bervo#177 · コメント 1 件 ·
メンテナーはふだん 1 日以内に返信
-
bug Filter
難易度 2/5 1〜3時間 初心者へのやさしさ 75/100
BlueQuartzSoftware/simplnx#1825 ·
メンテナーはふだん 3 日以内に返信