The Decode-Work Law: Margin-Governed, Provably-Exact Spatial Joins over Compressed Geometry

Jul 16, 2026

Upload by Hazel

Filter-and-refine spatial joins avoid exact geometry for certified candidate pairs, yet existing models ignore the decompression cost of survivors in compressed multiresolution storage. This work studies provably-exact polygon intersection joins over a Douglas–Peucker LOD ladder, certified via a two-sided Hausdorff-margin test. Contributions include a reproducible mechanism and harness achieving exact results while decoding 3.4–16.8× fewer vertices (median 5.9×) versus naive refinement, and a decode-work law where required decoding is governed by each pair’s signed-clearance margin.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages8

Reading Time20 min

Introduction

Contributions

Method and Certification

Douglas–Peucker LOD ladder and Hausdorff-margin test

Decode-Work Law

arXiv :2607 .01182v2 [ cs .DB] 10 Jul 2026 The Decode-Work Law: Margin-Governed, Provably-Exact Spatial Joins over Compressed Geometry Madhulatha Mandarapu∗ Sandeep Kunkunuru† VaidhyaMegha Private Limited, India [https://samyama. ai/](https://samyama. ai/) July 2026 Changes in v2 . The headline results are unchanged and are now better supported. (i) v1’s fairness paragraph stated “we count all bytes a method reads, including LOD headers.” It did not: only coordinate bytes were counted. Level-directory bytes are now charged to every method (§6) . The vertex-based headline is unaffected, the pooled byte advantage falls from 2 .02 × to 1.91×, and on the adversarial fixture the progressive method loses on bytes (0 .99×) once it pays for its own ladder—as it should. (ii) We pre-registered five negative controls and reported none. All five are now implemented and reported; the random-relabel null (NC3), never previously run, confirms the decode-work law against a permutation baseline (p = 0 .001) . (iii) v1 attributed the selectivity forecaster’s failure to selectivity saturating near one. The real cause is that its gap features are degenerate by construction. (iv) One pre-registered control (NC4) tested the wrong quantity; we say so rather than drop it. Abstract Filter-and-refine spatial joins have always avoided touching exact geometry for certified candidate pairs, but the field never modeled the decompression cost of the pairs that survive the filter. When geometry is stored in a compressed, progressively-decodable multiresolution codec, the join’s true cost is bytes decoded. We study provably-exact polygon intersection joins over a Douglas–Peucker level-of-detail (LOD) ladder, certified by a two-sided Hausdorff-margin test, and make two contributions. First, a reproducible mechanism and harness: on real U.S. Census TIGER water polygons, our progressive certificate join returns the exact result while decoding 3.4–16.8 × (median 5.9×) fewer vertices than naive decompress-then-refine, and about 4.9 × fewer than the single-approximation multi-step baseline of Brinkhoff et al. [1994], with zero correctness violations across 31 workloads. Second, a characterization we call the decode-work law: decode work is governed by each pair’s signed-clearance margin—how close it is to the predicate-flip boundary—independent of object size, because the certificate descends the ladder only until its resolution beats the margin. The law is clean on controlled geometry (held-out R2 = 0 .87, size-independent) and directional on real data (R2 ≈ 0.55) . We are explicit about what does not hold: a near-boundary-vertex predictor is the wrong model (we pre-registered one and rejected it), a selectivity regime forecaster did not materialize, and the worst case is the trivial Ω(v) read bound on adversarially interleaved boundaries. We contribute the mechanism, budget-honest decode accounting, and an open harness; we do not claim a new index. ∗ [madhulatha@samyama.ai](madhulatha@samyama.ai)[ ](madhulatha@samyama.ai)†[sandeep@samyama.ai](sandeep@samyama.ai) 1 Introduction Spatial joins—report all pairs (r, s) ∈ R × S satisfying a topological predicate such as intersects—area workhorse of geographic data systems [Jacox and Samet, 2007] . The dominant architecture is filter-and-refine [Brinkhoff et al. , 1993 , Patel and DeWitt, 1996]: a cheap minimum-boundingrectangle (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 [Saeedan and Eldawy, 2022]), 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 cl

FAQs

What problem does the Decode-Work Law address in spatial joins over compressed geometry?

It addresses that prior filter-and-refine approaches avoid exact geometry but do not model the decompression (bytes decoded) cost for candidate pairs that survive filtering when geometry is stored in a compressed multiresolution codec.

How does the proposed approach certify when two polygons intersect or are disjoint?

It uses a Douglas–Peucker LOD ladder and certifies DISJOINT when η-dilated coarse geometries are disjoint, certifies INTERSECT when η-eroded coarse geometries overlap, and otherwise descends the ladder until a certificate is obtained via a Hausdorff-margin test.

What determines how much decoding work a pair requires under the decode-work law?

Decoding work is governed by each pair’s signed-clearance (margin) relative to the predicate-flip boundary, largely independent of object size, because the certificate descends only until resolution beats that margin.

Jul 16, 2026

Upload by Hazel