City-Scale Visibility Graph Analysis via GPU-Accelerated HyperBall
2026-04-09 • Distributed, Parallel, and Cluster Computing
Distributed, Parallel, and Cluster Computing
AI summaryⓘ
The authors improved a technique called Visibility Graph Analysis (VGA), which helps study how space influences human movement, so it can work on very large city maps. They combined three key methods: better data compression to handle bigger graphs, a faster way to estimate distances using a probabilistic method called HyperBall, and hardware acceleration with GPUs. These changes made their system much faster—over 200 times faster in one example—and able to analyze much larger areas than before. Their results closely match traditional methods but with much less computation time.
Visibility Graph Analysisspace syntaxBreadth-First Search (BFS)HyperLogLogHyperBallLEB128 encodingGPU accelerationcompressed sparse row (CSR)topological depthdistance estimation
Authors
Alex Hodge, Melissa Barrientos Trinanes
Abstract
Visibility Graph Analysis (VGA) is a key space syntax method for understanding how spatial configuration shapes human movement, but its reliance on all-pairs BFS computation limits practical application to small study areas. We present a system that combines three techniques to scale VGA to city-scale problems: (i) delta-compressed CSR storage using LEB128 varint encoding, which achieves ~4x compression and enables memory-mapped graphs exceeding available RAM; (ii) HyperBall, a probabilistic distance estimator based on HyperLogLog counter propagation, applied here for the first time to visibility graphs, reducing BFS complexity from O(N|E|) to O(D|E|2^p); and (iii) GPU-accelerated CUDA kernels with a fused decode-union kernel that streams the compressed graph via PCIe and performs LEB128 decoding entirely in shared memory. HyperBall's iteration count equals the topological depth limit, so the radius-n analysis that practitioners already use as standard translates directly into proportional speedup -- unlike depthmapX, whose BFS time is invariant to depth setting due to the small diameter of visibility graphs. Using depthmapX's own visibility algorithm (sparkSieve2) to ensure identical edge sets, our tool achieves a 239x end-to-end speedup at 42,705 cells and scales to 236,000 cells (4.8 billion edges) in 137 seconds -- problem sizes far beyond depthmapX's practical limit. At p=10, Visual Mean Depth achieves Pearson r=0.999 with 1.7% median relative error across 20 matched configurations.