1 Introduction↩︎

Spatial joins—report all pairs \((r,s)\in R\times S\) satisfying a topological predicate such as intersects—are a workhorse of geographic data systems [2]. The dominant architecture is filter-and-refine [3], [4]: a cheap minimum-bounding-rectangle (MBR) filter produces candidate pairs, and an expensive exact geometric refinement decides each candidate. Modern stores keep geometry compressed: delta/varint coordinate codecs (TWKB), columnar layouts (GeoArrow, GeoParquet, SpatialParquet [5]), and progressively-decodable multiresolution encodings. In this setting the refinement step’s true cost is not comparisons or wall-clock but bytes decoded: an exact predicate needs coordinates, and decoding dominates.

Filter-and-refine already avoids exact geometry for pairs it can certify early—the classic multi-step join of [1] certifies hits and false-hits from conservative and progressive object approximations before touching exact geometry. What the literature never did is model the decode cost of the survivors: how many coordinate bytes must a provably-exact join actually decode, and what governs that number? This paper answers that question empirically and gives the answer a name.

We encode each geometry as a Douglas–Peucker [6] LOD ladder \(\tilde{g}_0,\dots,\tilde{g}_k=g\), level \(\ell\) carrying a guaranteed Hausdorff error bound \(\eta_\ell\) (monotone decreasing, \(\eta_k=0\)). A candidate pair is certified DISJOINT when the \(\eta\)-dilated coarse geometries are disjoint, INTERSECT when the \(\eta\)-eroded coarse geometries overlap, and otherwise descends the ladder—decoding more vertices—until it certifies. The certificate is the Hausdorff-margin instantiation of Brinkhoff’s false-area test; our questions are about its decode cost.

1.0.0.1 Contributions.

• A provably-exact compressed-domain join with measured teeth. On real TIGER water polygons, the progressive certificate join decodes \(3.4\)–\(16.8\times\) (median \(5.9\times\)) fewer vertices than naive decompress-then-refine and \(\approx4.9\times\) fewer than a single-approximation Brinkhoff baseline, at set-equality with a full-precision oracle (Section 4). The multi-level ladder—not a single intermediate approximation—is the source of the gain.

• The decode-work law. Decode work is governed by the per-pair signed-clearance margin \(m\), independent of object size: the certificate must descend until \(\eta_\ell<|m|\), so near-tangent pairs cost \(\Omega(v)\) and robustly-decided pairs cost almost nothing (Section 5). Clean on controlled geometry (\(R^2=0.87\), size-independent), directional on real data (\(R^2\approx0.55\)).

• Honest negatives and a reusable harness. We pre-registered a near-boundary band-vertex predictor and rejected it; a selectivity-based regime forecaster did not materialize; the worst case is the trivial read bound. All numbers regenerate from one command.

We deliberately do not propose a new index or a new codec, and we do not claim a general decompression-sensitive complexity model—that program is owned by [7] and the compact-data-structures literature [8]; we merely instrument in it.

2 Problem and model↩︎

Let \(R,S\) be collections of polygons with vertices quantized to a fixed grid; the quantized geometry is the data of record for both the compressed store and the exact oracle, so certificate pruning can only ever be a sound approximation of the exact stored polygon (no lossy rounding gap). For a geometry \(g\) the LOD ladder keeps a subset of \(g\)’s exact vertices at each level (a property of Douglas–Peucker), with \(\eta_\ell=\mathrm{HausdorffDistance}(g,\tilde{g}_\ell)\) and \(\eta_k=0\). Decoding to level \(\ell\) costs the cumulative vertices/bytes of that level.

2.0.0.1 Two-sided certificate.

For a candidate pair \((r,s)\) at levels \((\ell_r,\ell_s)\) define the outer \(O_g=\tilde{g}_\ell\oplus B(\eta_\ell)\) (a sound superset, \(g\subseteq O_g\)) and inner \(I_g=\tilde{g}_\ell\ominus B(\eta_\ell)\) (an inner approximation). Then \(O_r\cap O_s=\varnothing\) certifies DISJOINT and \(I_r\cap I_s\neq\varnothing\) certifies INTERSECT; otherwise the pair is ambiguous and we descend the coarser side. At \(\eta=0\) the test is the exact predicate. Soundness of the outer test is immediate; the inner (erosion) test is verified empirically on every run by the correctness gate (set-equality against the full-precision oracle) and the adversarial control, and the pre-registration mandates halt-and-harden on any violation—no violation occurred.

2.0.0.2 Signed-clearance margin.

The quantity that turns out to govern decode is the pair’s margin \[m(r,s)=\begin{cases}+\,\mathrm{inradius}(r\cap s) & \text{if } r\cap s\neq\varnothing \text{ (overlap depth)}\\ -\,\mathrm{dist}(r,s) & \text{if disjoint (gap)}. \end{cases}\] \(|m|\) measures how far the pair is from the predicate-flip boundary. Because a level-\(\ell\) certificate can only resolve features coarser than \(\eta_\ell\), the pair certifies at the first level with \(\eta_\ell<|m|\). The metric of interest is the decoded fraction \(\varphi_{\mathrm{pair}}=\text{decoded vertices}/(|r|+|s|)\) and the certifying depth.

2.0.0.3 Decode accounting (fairness).

Every method starts from the same MBR candidate set, so the measured delta is purely refinement depth. We count all bytes a method reads, including LOD headers. The naive-refine baseline decodes all vertices of every MBR survivor then tests exactly; the Brinkhoff [1] baseline is the two-level special case (one coarse approximation, then exact). Ground truth is always full precision.

3 Experimental setup↩︎

Real data. U.S.Census TIGER/Line 2023 AREAWATER (public domain) [9] for three geographically diverse counties—Jefferson, LA (FIPS 22051), St.Louis, MN (27137), King, WA (53033)—water polygons carrying tens to \(\sim\)​6,700 vertices (median \(\approx\)​85–109). The workload is \(\texttt{AREAWATER}\bowtie\mathrm{translate}(\texttt{AREAWATER}, \delta)\) with the translation \(\delta\) swept as a fraction \(\{0.1,0.25,0.5,1.0\}\) of the median polygon diagonal—a controlled real-geometry self-join (a standard spatial-join stress pattern [2]) that sweeps the margin regime while preserving real vertex-count heterogeneity. Synthetic control. Independently-placed rough blobs with varied vertex counts (so the size-independence test can be isolated) plus adversarial interlocking-comb fixtures and a hand-checked known-answer fixture. Apparatus. Single-thread Python with Shapely 2.1/GEOS 3.13 as the exact oracle; a custom Douglas–Peucker LOD ladder and delta/varint decode counter; fully deterministic (seeds only in synthetic generation). One command regenerates every number and figure.

3.0.0.1 Pre-registration.

Hypotheses, decision rules, and negative controls were frozen before any confirmatory run. We pre-registered a primary predictor (a near-boundary band-vertex count), rejected it on the pilot, and logged an amendment reframing the predictor to the margin before the confirmatory run; both the failure and the reframe are reported (Section 5).

4 Results: the teeth↩︎

Table 1 and Figure 1 report decode reduction on the real TIGER workloads. Across all \(12\) county\(\times\delta\) workloads the progressive join decodes a median \(5.9\times\) fewer vertices than naive decompress-then-refine (range \(3.4\)–\(16.8\times\)) and a median \(4.9\times\) fewer than the single-approximation Brinkhoff baseline, decoding only \(6\)–\(29\%\) of vertices (\(\varphi_{\mathrm{pair}}\)) for a provably-exact result. Every workload returns exactly the oracle’s pair set (correctness column). The multi-level ladder is decisive: it roughly quintuples Brinkhoff’s single-approximation savings, because most decode budget is spent on the small population of near-tangent pairs that a single coarse approximation cannot resolve.

5 Results: the decode-work law↩︎

5.0.0.1 Margin governs decode; size does not.

Figure 2 plots the per-pair decoded fraction \(\varphi_{\mathrm{pair}}\) against \(|m|\). The relationship is a clean collapse: near-tangent pairs (\(|m|\!\to\!0\)) decode essentially everything, robustly-decided pairs (\(|m|\) large) decode almost nothing. On controlled synthetic geometry a quadratic-in-\(\log_{10}|m|\) fit predicts the certifying depth with held-out \(R^2=0.87\), and after controlling for margin the standardized partial effect of object size is \(\beta_{\text{size}}=0.002\)—decode depth is margin-governed and size-independent, the instance-optimal invariant [10]. On real TIGER geometry the law is directional but weaker: best held-out \(R^2\approx0.55\), with the decoded fraction size-independent (\(\beta_{\text{size}}=0.07\)). Real multi-scale water boundaries add noise the controlled setting does not; we report the gap rather than paper over it.

5.0.0.2 What the law is not (rejected predictor).

We pre-registered a different predictor—the count of exact vertices lying near the other polygon’s boundary (an “\(\eta\)-band”). It was rejected on the pilot (held-out \(R^2\approx0.06\), wrong-signed): it proxies overlap robustness, which anti-correlates with decode, because a deep robust overlap has many near-boundary vertices yet certifies instantly. The margin is the correct, non-circular, geometry-only predictor, and we froze the reframe before the confirmatory run.

5.0.0.3 Regime and worst case.

The regime axis on real data is the margin (equivalently \(\delta\)), not selectivity: a selectivity-based forecaster we pre-registered did not materialize because translated self-joins hold selectivity near one, yet the decoded fraction genuinely spans \(0.06\)–\(0.29\) across the sweep. On adversarial interlocking-comb fixtures the certificate cannot prune—decoded fraction \(0.99\)—matching the trivial \(\Omega(v)\) read bound (and the \(\Omega(n\log n+K)\) reporting bound of [11] for the within-pair variant). Average, redundant geometry is cheap; adversarial geometry is not.

6 Related work↩︎

Multi-step spatial joins. [1] and its companion introduced conservative and progressive object approximations, certifying hits/false-hits before exact geometry; the false-area test is our \(\eta\)-margin certificate. Our delta is (i) a continuum of LOD levels rather than one intermediate approximation, which we benchmark and beat \(\approx4.9\times\), and (ii) modeling the decode cost rather than filter yield. Compressed-domain refinement. APRIL [12] refines intersection joins over a secondary raster-interval approximation; compact-structure joins [8], [13] operate over in-memory self-indexes for point/distance joins. We differ by operating on the native progressively-decodable geometry codec and by deriving a decode-cost law with boundary semantics. Bounded-error approximations. [14] advocate distance-bounded approximate answers; we return provably-exact results and use the bound only to decide decode depth. Complexity framing. [7] formalize decompress-and-solve versus compressed-size complexity; we instrument in that model rather than extend it, and frame our result as instance-optimal [10]. Columnar/scan pushdown [5] pushes filters, not join refinement, into the encoded domain.

7 Limitations and honest negatives↩︎

(1) The margin law is only partially predictive on real geometry (\(R^2\approx0.55\), below the \(\ge0.80\) we pre-registered)—a directional characterization, not a tight predictor. (2) Our pre-registered band-vertex predictor was rejected; the paper reports the failure and the reframe. (3) The selectivity-based regime forecaster did not hold; the real regime axis is the margin. (4) The worst case is the trivial \(\Omega(v)\) read bound—we prove no hardness result. (5) Scope: single-thread, polygon intersects (contains/within-\(\epsilon\) are sanity-only), a self-join-under-translation real workload (cross-county AREAWATER yields no candidates because TIGER clips water at county lines), and no new index or codec. (6) The inner-erosion certificate’s soundness is established empirically (zero violations across \(31\) workloads including adversarial), not proved in closed form.

8 Conclusion↩︎

The cost of a provably-exact spatial join over compressed geometry is the number of coordinate bytes it must decode, and that number is governed by how close each candidate pair sits to the predicate-flip boundary—its signed-clearance margin—not by how big the polygons are. A progressive certificate join that descends a multiresolution ladder only as deep as the margin demands decodes \(3.4\)–\(16.8\times\) less than decompress-then-refine on real data, exactly. We contribute the mechanism, the decode-work law (clean on controlled geometry, directional on real), budget-honest accounting, and an open one-command harness. Predicate-aware codecs whose error levels are designed jointly with the join, and a recall-free lower bound on decode versus margin, are natural next steps we do not claim here.

8.0.0.1 Reproducibility.

Code, data pointers, pre-registration, and one-command reproduction: https://github.com/samyama-ai/spatial-join-on-compressed.

References↩︎