Hacktoberfest 2026: le issue che i maintainer hanno segnato per ottobre, aperte e adatte ai principianti. Sfoglia le issue Hacktoberfest

Efficient encoding of points

Aperta
  • Qualcosa non va?
#35 5 commenti 4 reazioni 0 assegnatari Vedi su GitHub

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
5/5
Tempo stimato
Più di una settimana
Idoneità per principianti
20/100
Tipo di issue
Funzionalità
Chiarezza
Da chiarire
Stato di attività
Ferma
Ambito
data

Direzione di ricerca

Esamina l’attuale esempio di codifica dei punti nell’issue e confronta le ripetizioni elencate con la rappresentazione impacchettata e codificata a delta proposta. Un utile passo successivo sarebbe una prova di concetto su dati campione di punti z15, ma l’issue non indica file, test o criteri di accettazione; il completamento richiederebbe un design concordato per una futura revisione maggiore della specifica.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

3.0 Specification

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

Lingua principale
Nessun dato sulla lingua
Stelle
1k
Fork
213
Nessuna PR unita negli ultimi 30g

Preparare l'ambiente

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di mapbox/vector-tile-spec

Tutte le issue di mapbox/vector-tile-spec

Issue simili

Altre issue su Data Engineering

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.