Optimising viewshed storage

[ryan-berger]

CacheTVS is nearing the state where a paper can be written, but we have one more hurdle. The speed of our algorithm has always outstripped the speed at which we could write the raw data to disk, and in many cases the raw data is much too big for a single disk.

Recently we've made big steps in optimizing the storage of the data via PolarSegments. This is much better than the previous storage mechanism we used which relied on a visibility matrix of $$O(\theta * n^3)$$ bits for storage where $n$ is the size of the maximum line of sight. However, during @tombh 's work on Galiano (writeup here) we have hit another scaling limit.

A known limitation of CacheTVS is the lack of coverage at the edges of the viewshed. For example, with Galiano the greatest sweep an arc of one degree can cover at its maximum line of sight (~30km) is roughly ~261m, therefore 260 times bigger than the resolution of the underlying data. This means a smaller arc such as .1 or even .01 degrees must be chosen to respect the resolution of the underlying data which have arc sweeps of 26m and 2.6m respectively.

Note

For Galiano most lines of sight won't be the full maximum line of sight (say 30km) long, and many not even be 1km long, which may make .1 more practical than .01. For example, at a line of sight of 1km an arc of .1 degrees has an arc sweep of .8m which is roughly the resolution of the data. So it's only when we get into the 10s of kms that higher angular resolutions become relevant.

Since storage is currently linear in terms of the number of angles, increasing the angular resolution to .1 would take our custom PolarSegment binary encoding from a 2.7TB database for the whole island to 27TB. And for an arc of .01 degrees that would be 270TB, which is not acceptable for most applications.

Another case where storage optimisation would be critical is for the grand goal of storing every viewshed on the planet, which currently, at a DEM resolution of 100m and an angular resolution of 1 degree, would require multiple petabytes.

So before writing a paper however, we should have a good handle on compressed storage mechanisms for viewsheds. There are a number of optimizations we can do to get us to .1 degree for Galiano Island, and these lay the ground work for .01 degrees and world viewsheds.

Optimisations

Galiano .1 degrees

• Limit the observer's line of sight to within the "area of interest". Namely: don't store visibility data for regions outside of the island. Potential savings: ~10%.
• Order all PolarSegments and compress them with lz4 before finally storing them. Potential savings: ~50%-80%.
• Shard computation based on DEM ID rather than angle to improve data locality at the cost of extra rotations. This is an architectural change that runs the whole algorithm on small squares within the DEM so that we can aggregate all angles and visible segments in memory, before compressing and sending them to disk.
• Write to a flat file instead of SQLite to hopefully use the full SSD bandwidth. This improves computation speed and final web-hosting costs as it can be trivially served from a CDN bucket.

Experiments:

• What is the amortized cost of storing viewsheds as traditional polygons rather than our current PolarSegments? Are there fewer vertices than polar segments? Although a naive approach is likely to actually increase storage, at certain scales are there smoothing algorithms that do work? See Viewshed polygon optimisation #59

Galino .01 degrees and the World

• Only store viewsheds that meet heuristics like: the viewshed with the largest surface area amongst its 16x16 neighbours. Potential savings: 10x-100x.
• Custom polygon encoding. The above experiment with encoding viewsheds as traditional polygons is likely to be suboptimal. Since our usecases and algorithm are so specialized, we think there is a Platonic Ideal of an encoding that would suit us better. An interesting jumping off point might be an encoding that makes use of our polar coordinate system and performs a convex hull on each constituent piece of the viewshed. See Viewshed polygon optimisation #59
• Explore video-codec-inspired storage:
  • Store viewsheds as diffs against an adjacent "keyframe" viewshed.
  • Use "motion vectors" informed by predictable parallax effects to guess the shape of an adjacent viewshed, and store the diff against that prediction.