| Axis | k2-acc/tree/raster lineage | Our work |
|---|---|---|
| Compression mechanism | Spatial homogeneity (quadtree pruning) or per-value bitmap indicator | Value-magnitude/bit-width (bitpacking/FoR/PFOR) |
| Data validated on | Primarily SGI/IGN’s MDT05 elevation DEM (Spain), same source across nearly every paper. | |
| One paper (Silva-Coira et al. ‘23) also benchmarked WorldClim Temperature for map algebra. | ||
| Another benchmarked cloud-cover but for temporal benchmarks only, not map algebra | Broad collection: optical (Landsat & Sentinel), DEM (SRTM & ETOPO1), climate (WorldClim Temp & Precipitation) | |
| Cardinality regime | k2-acc & k3-tree: fail beyond 10^3 - 10^4 distinct values. | |
| k2-raster: scales to >10^6, no hard failure | High-cardinality continuous sensor data; not cardinality-constrained | |
| Query shape optimized for | Selective (point/window/range/join/top-K). Sublinear via pruning | Dense full-raster elementwise/reduction - no pruning possible |
| Operators benchmarked | Analytical: thresholding, scalar sum/mult, point-wise sum, zonal sum. All unary or linear/associative (GeoInformatica for k2-acc fusion; Silva-Coira et al. for k2-raster fusion). No nonlinear multi-operand kernel like NDVI. | |
| Other: cell/window/range retrieval (SPIRE'13, SSDBM'16); spatial join, top-K (PLOS ONE) | General kernel (NDVI, nonlinear) + associative reductions (sum, count; min/max TODO) | |
| Operator generality | New structure or new bespoke algorithm per query type. |
Uneven performance. Pruning-friendly ops (scalar add, thresholding) get major speedups; full-scan ops (point-wise sum, scalar multiply, zonal sum) get limited speedups - k2-raster drops to on-par/slower than a heavy compressed baseline (DEFLATE via NetCDF).
Same structure, wildly different results depending on whether pruning happens to apply. | Generic full-correction decode stream (any kernel) + optional deferred-correction fast path (associative kernels).
Currently limited to sequential streaming. |
| Uncompressed baseline | • libtiff, chunk-copying artifact (SPIRE'13 + Inf. Sci. ext.) - unfair.
• decompress → recompress (GeoInformatica, Silva-Coira et al.) - unfair.
• deflate-compressed in-memory via NetCDF (Silva-Coira et al.) - unfair. performs terribly so comparisons to it are very unfair.
**** • Plain-Ints/Bits, in-memory (PLOS ONE) - fair.
Only one paper has a fair/hard/comparable uncompressed baseline. | In-memory array, direct-access/zero-copy - fair. | | Honest speedup range (when fair baseline used) | 1.21–5x (PLOS ONE, vs. dominant Plain-Ints baseline). Only for join / top-K - different query class to ours. Can’t quote speedups of the other papers / operations as they don’t have a fair uncompressed baseline! | 1.23–2.28x (vs. flat in-memory array). NB: increases up to 1.67–5x with enough concurrency to approach the 1/CR limit. Not yet done in general, only for NDVI with bitpacking, but should be possible. | | Ceiling for the reported speedup | Not stated/bounded. Sublinear pruning has no fixed ceiling | 1/CR (compression ratio). Known, statable physical limit | | Parallelisability | Not evaluated in any paper. All single-core setups, no concurrency variable. Structurally uneven if attempted - pruning gives variable per-region work, no fixed-block SIMD decode path. Silva-Coira et al. (most recent paper) noted parallelisation as future work. | Spatial decomposition - N regions in parallel, read-only, combine at end. Demonstrated; drives speedup toward the 1/CR limit | | Correctness verification | Formal: induction-based correctness proofs. | Empirical: verified against ground-truth output, no formal proof. Arguably overkill for our work. |