Coordinate Quantization Before Delta Encoding

This guide solves a sequencing problem that is easy to get backwards: when a GPS stream is about to be delta-encoded for transmission over a metered link, should you quantize the coordinates first and then difference the integers, or difference the raw floats and quantize the result? Within the Bandwidth & Async Sync Optimization practice, and specifically inside delta sync for spatial datasets, the order matters more than it looks: quantize-then-delta gives you a bounded, non-compounding error and small integers that varint and zigzag encoding compress well; delta-then-quantize looks equivalent on a single pair of points but silently accumulates rounding error across a long chain of fixes.

Sizing the quantization step against GPS accuracy #

The quantization step, Δ, is the smallest coordinate change the wire format can represent. Pick it too fine and you waste bits encoding noise the receiver’s hardware never actually resolved; pick it too coarse and you throw away real movement, snapping a slow-moving asset’s track to a grid coarser than its true path. The right anchor is the GPS unit’s own accuracy budget, not an arbitrary decimal count. A step of one part in 10^n degrees converts to a ground distance by the same relation used to size any coordinate precision contract:

$$\Delta_{\text{lat}} \approx \frac{111{,}320}{10^{n}}\ \text{m}, \qquad \Delta_{\text{lon}} \approx \frac{111{,}320 \cdot \cos\varphi}{10^{n}}\ \text{m}$$

where φ is latitude in radians and 111,320 is meters per degree of latitude. A consumer-grade GNSS module without RTK correction rarely holds better than 1–3 m even when stationary, so n = 5 (Δ ≈ 1.11 m at the equator) is the usual sweet spot for fleet tracking: fine enough that quantization error stays well under the receiver’s own noise floor, coarse enough that the resulting deltas fit comfortably in one or two encoded bytes. Survey-grade RTK streams can justify n = 7 (Δ ≈ 1.1 cm), but only if the downstream wire format and every buffer along the way are sized for the larger integers that finer step implies — the same accuracy-tiering already laid out in spatial data precision standards.

Quantizing first converts each absolute coordinate to an integer count of steps: q = round(x / Δ). Because that rounding happens once, against the true position, the maximum error any single quantized point carries is Δ / 2 — a fixed, bounded quantity that never grows no matter how many fixes follow it. Delta-encoding the quantized integers afterward is then exact integer subtraction with no further rounding: d_i = q_i − q_{i-1}, and reconstructing the track is q_i = q_0 + Σd, which recovers the quantized positions exactly.

Quantize, delta, zigzag, varint: the complete encoder #

The reason this ordering compresses well is arithmetic, not incidental: a stationary or slowly moving asset produces deltas of 0, ±1, or ±2 quantization steps almost every cycle. Zigzag mapping folds small negative integers next to small positive ones (0 → 0, -1 → 1, 1 → 2, -2 → 3, 2 → 4, …) so that small magnitudes — positive or negative — always produce small unsigned values, which varint then packs into a single byte for the overwhelming majority of fixes.

# quantize_delta_varint.py
# Quantize-then-delta encoder for a GPS coordinate stream. Targets a
# gateway with no floating-point delta math on the wire path: every
# value on the wire is an integer, packed to its natural byte length.
from typing import Iterator

def quantize(x: float, step: float) -> int:
    """Round a coordinate to the nearest quantization step, as an integer
    count of steps. Error introduced here is bounded to +/- step/2 and
    never grows, no matter how many later deltas are chained off it."""
    return round(x / step)

def zigzag_encode(n: int) -> int:
    """Map a signed integer to an unsigned one so small magnitudes in
    either direction stay small: 0,-1,1,-2,2,... -> 0,1,2,3,4,..."""
    return (n << 1) ^ (n >> 63)  # arithmetic shift assumes 64-bit signed input

def varint_encode(n: int) -> bytes:
    """Standard LEB128 varint: 7 payload bits per byte, high bit set on
    all but the last byte. Small deltas cost 1 byte; large ones grow."""
    out = bytearray()
    while True:
        byte = n & 0x7F
        n >>= 7
        if n:
            out.append(byte | 0x80)
        else:
            out.append(byte)
            return bytes(out)

def encode_stream(fixes: list[tuple[float, float]], step: float = 1e-5) -> bytes:
    """Quantize each fix, delta against the previous quantized integer,
    zigzag, and varint-pack. The first fix is emitted as an absolute
    anchor (two varints, no zigzag needed since it's not a delta)."""
    out = bytearray()
    prev_lat_q = prev_lon_q = None
    for lat, lon in fixes:
        lat_q = quantize(lat, step)
        lon_q = quantize(lon, step)
        if prev_lat_q is None:
            out += varint_encode(zigzag_encode(lat_q))
            out += varint_encode(zigzag_encode(lon_q))
        else:
            out += varint_encode(zigzag_encode(lat_q - prev_lat_q))
            out += varint_encode(zigzag_encode(lon_q - prev_lon_q))
        prev_lat_q, prev_lon_q = lat_q, lon_q
    return bytes(out)

def zigzag_decode(z: int) -> int:
    """Inverse of zigzag_encode."""
    return (z >> 1) ^ -(z & 1)

def iter_varints(payload: bytes) -> Iterator[int]:
    """Decode a byte stream back into the sequence of unsigned varints."""
    n = shift = 0
    for byte in payload:
        n |= (byte & 0x7F) << shift
        if not (byte & 0x80):
            yield n
            n = shift = 0
        else:
            shift += 7

A stationary asset with a 1e-5 degree step and typical 1–3 m GPS jitter produces zigzag values under 10 on most cycles, which varint_encode packs into a single byte per coordinate — two bytes per fix instead of the sixteen a float64 pair costs, before any general-purpose entropy coder even runs. That is the same layering discipline the parent compression guide applies at the structural and semantic reduction stages: quantize-then-delta is the semantic layer, and it should always run before a codec like Zstandard or Brotli sees the bytes, not after.

Constraint validation table #

Gotchas and edge cases #

• Delta-then-quantize compounds error; quantize-then-delta does not. If you instead compute raw_delta = lat_i - lat_{i-1} in floating point and then round that delta to the step grid, each rounding decision is made relative to the previous fix’s own rounding error, not the true position — over a long chain the reconstructed track can drift meters away from the true path. Quantizing the absolute coordinate first, before any subtraction, keeps every point’s error independently bounded to Δ/2 regardless of chain length.
• A silently drifting reference needs periodic anchors. Even with bounded per-point error, a dropped packet partway through a long delta chain desynchronizes the receiver’s running sum from the sender’s. Emit a full absolute anchor on a fixed cadence — the same 300–600 second or 10,000-delta cadence used in implementing delta sync for GPS coordinate streams — so a lost frame only corrupts one interval, not the whole track.
• Zigzag needs a fixed bit width on both ends. The n >> 63 shift above assumes 64-bit signed arithmetic; porting this encoder to a 32-bit embedded target without adjusting the shift silently mishandles the sign bit for large deltas. Pin the width explicitly rather than relying on the host platform’s native integer size.
• Step size is a wire-format contract, not a runtime parameter. If the sender and receiver disagree on step, every decoded coordinate is off by a constant scale factor that looks like a plausible but wrong position — never let step vary per message without also transmitting it, and prefer fixing it once in firmware alongside the other constants in your precision policy.
• Varint growth is not free for erratic movement. A cold-start jump or a receiver re-acquiring signal after a tunnel can produce a delta many steps wide, growing to two or three encoded bytes. That is expected and bounded — the format degrades gracefully rather than overflowing — but a delta that would require more than a few bytes is also a good trigger to force an anchor rather than keep encoding an implausible jump.

Integrating with the delta sync pipeline #

This encoder replaces the fixed-width struct.pack('<ii', ...) framing used in the delta sync guide’s binary-packing stage with a variable-length one that shrinks further for the common case of small or zero movement. Wire the quantization step into the same syncer that already tracks hysteresis and monotonic time:

def pack_fix_for_wire(lat: float, lon: float, tracker_state: dict, step: float = 1e-5) -> bytes:
    """Drop-in replacement for a fixed-width pack call: quantize, delta
    against the tracker's last quantized position, zigzag, and varint-pack."""
    lat_q, lon_q = quantize(lat, step), quantize(lon, step)
    prev_lat_q = tracker_state.get("lat_q", lat_q)
    prev_lon_q = tracker_state.get("lon_q", lon_q)
    frame = varint_encode(zigzag_encode(lat_q - prev_lat_q))
    frame += varint_encode(zigzag_encode(lon_q - prev_lon_q))
    tracker_state["lat_q"], tracker_state["lon_q"] = lat_q, lon_q
    return frame

Feed the variable-length frames into the same bounded ring buffer and asyncio drain loop the parent delta sync pipeline already uses; the only change is that flush_to_upstream now concatenates variable-length frames instead of fixed 13-byte ones, so the receiver must delimit frames by re-running iter_varints in pairs rather than slicing at a fixed stride.

Related #

• Delta Sync for Spatial Datasets — the parent pattern for change detection, framing, and reconciliation this quantization step feeds.
• Implementing Delta Sync for GPS Coordinate Streams — the fixed-width syncer this variable-length encoder can drop into.
• Spatial Data Precision Standards — choosing the decimal budget that sets the quantization step in the first place.