mapbox / mapbox/vector-tile-spec

Efficient encoding of points

Open
#35 5 comments 4 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

3.0 Specification
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

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.