City-Scale Space Syntax: GPU-Accelerated Graph Analysis for Urban Movement Prediction
I don’t have web fetch access, but I have enough from the abstract and my knowledge of the underlying techniques to write a solid explainer.
Urban planners have long known that the shape of a street or corridor influences how people move through it — not just because of physical distance, but because of what is visible from any given point. Quantifying that relationship at scale has been the hard part. This paper removes a significant computational barrier, making city-scale visibility analysis practical for the first time.
The Problem: All-Pairs BFS Doesn’t Scale
Visibility Graph Analysis (VGA) is a core method in space syntax — a field that models built environments as graphs where nodes represent locations and edges connect points with unobstructed sightlines. From this graph, researchers compute metrics like integration (a measure of how accessible a point is from everywhere else) and mean depth (average shortest path length). These metrics predict pedestrian flow with striking accuracy.
The catch: computing them requires all-pairs shortest-path traversal — essentially running BFS from every single node in the graph. For a building or small plaza, that’s tractable. For a city grid sampled at 1-meter resolution, you’re looking at tens or hundreds of millions of nodes. The quadratic blowup makes naive computation completely infeasible. Most VGA tools in practice cap out at small neighborhoods or require aggressive downsampling that throws away spatial detail.
Three Techniques, One System
The authors combine three complementary ideas to break this wall.
1. Delta-Compressed CSR with LEB128 Encoding
Visibility graphs are stored in Compressed Sparse Row (CSR) format — a standard adjacency representation that stores edge lists contiguously in memory. The key insight here is that in a spatial visibility graph, neighbors of a node tend to have nearby indices (because nearby grid points see each other). This locality means delta encoding — storing the difference between successive neighbor IDs rather than the IDs themselves — produces small integers.
Small integers compress well with LEB128 (Little Endian Base 128), a variable-length encoding where values under 128 cost just one byte. The result is roughly 4x compression compared to uncompressed CSR. More importantly, the compressed representation is small enough to memory-map: the OS can page in only the portions of the graph currently needed, allowing the working set to exceed available RAM without explicit out-of-core logic in application code. This sidesteps one of the most painful engineering constraints in large-scale graph processing.
2. HyperBall for Approximate Centrality
Instead of exact BFS, the system uses HyperBall — a probabilistic algorithm built on HyperLogLog sketches. The core idea: rather than tracking exact sets of nodes reachable within distance k, each node maintains a compact probabilistic sketch of its k-neighborhood. In each round, nodes merge their sketches with their neighbors’, approximating the growth of reachable sets across the whole graph simultaneously.
HyperBall computes closeness centrality and related metrics in O(diameter × m) time with sublinear memory per node, where exact BFS would need O(n × (n + m)). The tradeoff is an approximation error controlled by the sketch size — typically a few percent, which is well within the tolerance of urban planning applications where the goal is comparative analysis across space, not precise path lengths.
3. GPU Parallelism
The sketch-merging rounds of HyperBall map naturally to GPU execution: each node’s update in a given round is independent of other nodes in the same round, making the algorithm embarrassingly parallel at the per-node level. The paper implements this on GPU hardware, exploiting the massive thread-level parallelism that makes GPUs well-suited to graph algorithms with regular memory access patterns — which the delta-compressed CSR largely preserves.
What This Unlocks
The combination targets a practical ceiling that has constrained the field for years. City-scale VGA means analysts can study how visibility-based accessibility varies across an entire metropolitan grid — comparing a dense historic center against suburban sprawl, or evaluating how a proposed development changes sightline integration across surrounding blocks. These are questions practitioners have wanted to ask for decades but couldn’t run in reasonable time.
The memory-mapping approach deserves particular attention from a systems perspective: it’s a clean example of letting the OS do heavy lifting. Rather than building explicit tiered storage, the compressed graph just lives on disk, and the kernel’s page cache handles locality. For graphs that don’t fit in RAM but aren’t orders of magnitude larger, this is often the right tradeoff — minimal engineering complexity, good real-world performance.
What to Watch For
The probabilistic approximation in HyperBall introduces error that’s worth understanding before adopting this approach. For applications where exact integration values matter — say, calibrating a pedestrian simulation model against empirical counts — it’s worth auditing whether the approximation error stays bounded across different urban morphologies. Dense, highly connected grids may behave differently than sparse suburban layouts with long sightlines.
The compression scheme also assumes spatial locality in node indexing. If a graph is indexed in a way that breaks this locality (arbitrary IDs, shuffled inputs), the delta encoding degrades toward uncompressed size. Any practical deployment should include a preprocessing step to ensure spatially coherent ordering — a Morton/Z-order curve reindexing is the standard approach here.
Overall, this is a well-engineered combination of existing tools — sketch algorithms, varint compression, GPU parallelism — applied to a domain where the status quo was genuinely stuck. The full paper is available at arxiv.org/abs/2604.08374.