mapbox / mapbox/vector-tile-spec
Efficient encoding of points
Nobody has claimed this yet.
- Dominant language
- No language data
- Stars
- 1k
- Forks
- 213
- PR merge metrics
- No merged PRs in 30d
Description
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:
``` js
{
"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:
``` js
{
"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
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Review the current point-encoding example in the issue and compare its listed repetitions with the proposed packed, delta-encoded representation. A useful next step would be a proof-of-concept on sample z15 point data, but the issue does not name files, tests, or acceptance criteria; completion would require an agreed design for a future major specification revision.
Written by the indexing model from the issue text.
Assessment
- Domain
- data
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 20/100