C ITY-S CALE V ISIBILITY G RAPH A NALYSIS VIA GPU-ACCELERATED H YPER BALL A P REPRINT
arXiv:2604.08374v1 [cs.DC] 9 Apr 2026
Alex Hodge Independent Researcher, London, UK [email protected]
Dr. Melissa Barrientos Triñanes School of Geography, University of Leeds, UK [email protected]
April 10, 2026
A BSTRACT 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 ∼4× 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|·2p ); 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 [1] 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 239× end-to-end speedup at 42 705 cells and scales to 236 000 cells (4.8 billion edges) in 137 s—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. Keywords visibility graph analysis · space syntax · HyperLogLog · GPU computing · urban morphology
1
Introduction
Space syntax [2] studies how the geometric configuration of space shapes human behaviour: movement patterns, social co-presence, and land-use distribution. Visibility Graph Analysis (VGA) [3] extends space syntax from street networks to continuous open space by placing a regular grid of points over the study area, connecting mutually visible pairs, and computing graph-theoretic metrics on the resulting structure. Metrics such as visual integration, mean depth, and clustering coefficient reveal spatial properties—visual accessibility, topological remoteness, convex-versus-linear character—that are invisible to purely geometric analysis. The computational cost of VGA grows rapidly with problem size. The key bottleneck is all-pairs shortest-path computation: metrics like mean depth require BFS from every node, costing O(N · |E|) for the main connected component. At fine grid resolution (1 m to 5 m) over city-scale areas (> 1 km2 ), graphs reach tens of thousands of nodes with hundreds of millions of edges. depthmapX [4], the standard tool, is single-threaded and in-memory; in our benchmarks it scales as O(N 2 ) and timed out at 30 min beyond 42 705 cells. We present a system that overcomes these limits through three contributions: 1. Delta-compressed CSR storage. Neighbour indices are delta-encoded as LEB128 varints, achieving ∼4× compression. Memory-mapping allows graphs exceeding RAM to be processed.
City-Scale Visibility Graph Analysis via GPU-Accelerated HyperBall
A P REPRINT
2. HyperBall for VGA with depth-proportional speedup. We apply HyperBall [5]—a probabilistic distance estimator based on HyperLogLog counter propagation—to visibility graphs for the first time, reducing allpairs BFS from O(N ·|E|) to O(D ·|E|·2p ) where D is the graph diameter. Unlike depthmapX’s BFS, which runs in constant time regardless of depth setting due to the small diameter of visibility graphs, HyperBall converges in exactly min(d, D) iterations. At depth limit 3—the standard local measure in VGA practice [6, 7]—this yields a 352× BFS-phase speedup. 3. GPU-accelerated CUDA pipeline. A fused decode-union kernel streams the compressed graph to the GPU and performs LEB128 decoding in shared memory. To ensure a fair comparison, we use depthmapX’s own visibility algorithm (sparkSieve2 angular sweep), ported to Rust with data-parallel execution via Rayon, producing identical edge sets and isolating accuracy differences to the HLL approximation alone. Across 20 matched configurations, Visual Mean Depth achieves Pearson r = 0.999 at HLL precision p = 10 with 1.7 % median relative error, while our tool delivers a 239× end-to-end speedup at 42 705 cells and scales to 236 000 cells (4.8 billion edges) in 137 s.
2
Background and Related Work
2.1
Space Syntax and VGA
Space syntax [2] is a family of theories and analytical methods that relate the geometric configuration of space to patterns of human movement and co-presence. The core insight is that the topology of the street network—how each segment connects to every other—predicts where people walk, where retail activity concentrates, and which spaces feel lively or deserted, often more strongly than deliberate planning interventions. Visibility Graph Analysis (VGA), introduced by Turner et al. [3] and building on Benedikt’s isovist framework [8], extends space syntax from street networks to continuous open space. A regular grid of points is placed over the study area; points inside buildings are removed; and any two remaining points that share an unobstructed line of sight within a radius r are connected by an edge in the visibility graph. Graph-theoretic metrics are then computed on this structure to characterise each location’s visual integration within the whole. The thirteen standard metrics span local and global properties: connectivity (immediate degree); visual mean depth (mean shortest-path distance); three integration variants (Hillier-Hanson [HH] [2], Teklenburg [Tekl] [9], and P-value [6]); control and controllability (local visual dominance); clustering coefficient [10]; visual entropy and relativised entropy; and point first and second moments [3]. Visually integrated locations—those with low mean depth and high integration—attract pedestrian movement and anchor social activity; clustering coefficient distinguishes convex plaza-like spaces from linear corridor-like spaces [3, 7]. VGA has been applied to urban public space, building interiors, and, as in the present work, city-scale open-space analysis [11]. 2.2
Computational Challenges in VGA
VGA poses three compounding computational challenges at city scale. Graph density. The mean degree of a visibility graph node grows as π(r/s)2 times the open-space occupancy fraction, where r is the visibility radius and s is the grid spacing. At 2 m spacing and 300 m radius the expected mean degree is approximately 20 800, giving roughly 60 billion directed edges for 2.9 million nodes. In standard 32-bit CSR format this requires approximately 240 GB for the index array alone. BFS metric cost. Mean depth and all derived integration metrics require all-pairs shortest-path distances. Exact BFS from every node costs O(N · |E|); at N = 2.9 × 106 with billions of edges, exact computation is infeasible on commodity hardware. The standard tool depthmapX [4] is a single-threaded, in-memory implementation whose practical limit is approximately 50 000–100 000 nodes. Existing approximations and their limitations. Tiling—processing overlapping spatial sub-regions independently—was an early strategy for reducing memory demand, but BFS metrics are truncated at tile boundaries, introducing severe artefacts. Testing on a 950 m study area with 200 m tiles showed 84 % error in Visual Node Count and 59 % error in Mean Depth. The errors are structural, not implementation-specific, and arise because boundary truncation shortens apparent shortest paths and artificially inflates integration values. Viraph [12] avoids full BFS by decomposing the floor plan into convex sub-areas and computing interspatial depth via weighted Dijkstra on the resulting convex-region graph, enabling faster analysis for small study areas. Landmark BFS [13, 14]—running exact √ BFS from K ≈ N spatially stratified source nodes and averaging the resulting distances—provides artefact-free 2
City-Scale Visibility Graph Analysis via GPU-Accelerated HyperBall
A P REPRINT
√ approximations with O(1/ K) convergence and 3–5% relative error, but requires K · |E| edge traversals: at K = 1709 and 60 billion edges, this takes more than 24 h on the hardware described in Section 4.1. 2.3
HyperLogLog and HyperBall
HyperLogLog (HLL) [15] is a probabilistic cardinality estimator that represents a set as m = 2p registers, each storing the maximum leading-zero count seen among √ hashed elements. It estimates set cardinality from the harmonic mean of 2−register values with standard error 1.04/ m; at p = 8 (m = 256) the standard error on raw cardinality is approximately 6.5 %. The union of two HLL sketches is computed in O(m) time by taking the element-wise maximum of their register arrays—a property that enables efficient propagation over graph edges. HyperBall [16, 5] exploits this property to estimate the neighbourhood function |B(v, t)|—the number of nodes within t hops of v—for every node simultaneously. In each iteration t, each node’s HLL counter is unioned with the counters of all its neighbours; after t iterations, counter v encodes an estimate of |B(v, t)|. The key identity relating the neighbourhood function to mean depth is X
d(v, u) =
u̸=v
D X
t · |B(v, t)| − |B(v, t − 1)| ,
(1)
t=1
where D is the diameter. This allows mean depth to be computed from the sequence of cardinality estimates accumulated across iterations, without storing any per-node distance array. The algorithm converges in O(D) iterations, each requiring one scan over all edges to propagate m = 2p registers per union, for total time O(D · |E| · 2p ). HyperBall has been applied to web and social graphs at scales of billions of nodes [5]; to our knowledge, this work is the first application to visibility graphs.
3
Method
3.1
Visibility Graph Construction
The construction pipeline takes building footprints and a study area boundary as input and produces a delta-compressed CSR graph. Building edges are first rasterised into a per-cell CSR structure at the grid spacing resolution; grid points are sampled at spacing s and filtered to exclude cells inside building footprints, yielding the set of visibility nodes V . SparkSieve angular sweep. Visibility is determined using the sparkSieve2 algorithm from depthmapX [4], ported to Rust. For each source cell, eight octants expand outward ring-by-ring, maintaining a list of angular gaps in [0, 1] tan-space. At each depth ring, obstacle line segments crossing the ring are projected into tan-space and subtracted from the gap list; grid cells that fall within remaining gaps are visible and added to the neighbour list. When all gaps close, the octant terminates. Work is proportional to the number of visible cells, not the search area, making the algorithm efficient in obstacle-rich environments. Using depthmapX’s own visibility algorithm is a deliberate design choice: it produces identical edge sets, isolating all accuracy and performance differences to the HyperBall BFS approximation alone. Source nodes are processed in parallel via Rayon [17]; neighbour lists are delta-encoded and appended to the compressed CSR store in batched writes. Connected components are computed incrementally during construction via Union-Find (path halving, union by rank), requiring no post-hoc graph traversal. 3.2
Delta-Compressed CSR Representation
Standard CSR stores neighbour indices as a flat array of 32-bit integers. At 60 billion edges this requires approximately 240 GB for the index array alone—far exceeding available RAM and precluding in-memory graph operations. The delta-compressed CSR format solves both the storage problem and, crucially, enables GPU-accelerated HyperBall by keeping the on-wire graph size within the PCIe streaming budget (Section 3.4). The key observation is that visibility graph neighbour lists, when sorted by node index, have small successive differences. Nodes are numbered in raster scan order, so neighbours within the same row of the grid differ in index by 1 or 2; neighbours in adjacent rows differ by the grid width. At 3 m spacing and 200 m radius a representative node has approximately 13 800 within-row neighbours with deltas ∆ < 128 (one byte in LEB128) and approximately 133 between-row jumps of roughly 1200 (two bytes), giving approximately 14 kB per node compressed versus 56 kB uncompressed—a 4× compression ratio. 3
City-Scale Visibility Graph Analysis via GPU-Accelerated HyperBall
A P REPRINT
Sorted 1042 1043 1044 1045 2245 2246 2247 indices within-row Δ < 128, 1 B
Deltas 1042
1
LEB128 x92 x08 bytes
1
1
1
1
1
1200
xB0 x09
2B
1
1
1
1
row jump Δ ≈ width, 2 B
2B
7 indices × 4 B = 28 B → 9 B encoded (3.1×) Figure 1: Delta-compressed CSR encoding. Sorted neighbour indices yield small deltas that fit in one or two LEB128 bytes. The byte stream is memory-mapped for graphs exceeding physical RAM. The sequential structure of HyperBall iterations enables the compressed stream to be transferred directly to the GPU and decoded on-device.
Encoding. The first neighbour index in each row is stored as an absolute unsigned LEB128 varint; subsequent entries encode the non-negative delta from the previous index. The CompressedCsr struct stores a u64 byte-offset array (length N + 1), a u32 degree array, and the byte stream. A lazy NeighborIter decodes varints on demand via a streaming Rust iterator with zero copying, requiring only two integer additions and two bit shifts per neighbour. Because graph traversal is memory-bandwidth-limited, the smaller working set more than offsets the decode overhead. Memory management. For graphs that fit in RAM the byte stream is heap-allocated; for larger graphs it is written to an anonymous temporary file during batched parallel construction (Rayon) and then memory-mapped with memmap2. In the mmap case the OS page cache manages which pages reside in physical memory, and peak RSS during construction is bounded by the offset and degree arrays (approximately 35 MB for 2.9 million nodes) plus one streaming construction batch. Graphs are persisted in a binary format (VGACSR03) that appends pre-computed connected-component metadata (Union-Find component IDs and sizes) so that this information is immediately available on reload without a post-hoc BFS pass. Optional Hilbert reordering. For unlimited-depth analysis requiring many HyperBall iterations, an optional Hilbert space-filling curve reordering improves GPU L2 cache locality. The reordering maps 2D grid cells to a 1D index where spatially adjacent cells receive nearby indices, then rebuilds the CSR with remapped and re-sorted neighbour lists. Compression is unaffected—the permuted CSR is within 1 % of the original size—because Hilbert-ordered neighbours still produce small deltas. The inverse permutation (4 B per node) is stored in the VGACSR03 file for coordinate restoration. At depth-limited radii (3–5 iterations), the working set already fits in GPU L2 cache and Hilbert reordering provides negligible benefit; it is most useful for large unlimited-depth runs where many iterations amplify cache miss costs. GPU streamability. A critical property of the level-synchronous HyperBall algorithm is that each iteration scans every node’s compressed neighbour byte-range exactly once in a predictable sequential pattern. This allows compressed data to be streamed to the GPU in contiguous batches with the LEB128 decode performed on-device in CUDA shared memory (Section 3.4). Landmark BFS, by contrast, accesses neighbour lists in frontier-determined order that depends on graph structure and cannot be pre-scheduled for sequential streaming; it is therefore confined to the CPU, where the NeighborIter decoder handles irregular access efficiently. 4
City-Scale Visibility Graph Analysis via GPU-Accelerated HyperBall
3.3
A P REPRINT
HyperBall for VGA Metrics
HyperBall [16, 5] estimates the neighbourhood function |B(v, t)|—the number of nodes within t hops of v—for all nodes simultaneously by propagating HyperLogLog (HLL) sketches level-synchronously over the graph. We adapt it for VGA to compute all BFS-derived metrics in O(D · |E| · 2p ) time, where D is the graph diameter and p the HLL precision, instead of the O(N · |E|) required by exhaustive BFS. Initialisation. Each node v is assigned an HLL counter comprising m = 2p registers (typically p = 8 to 14; we recommend p = 10 as the default, giving m = 1024 registers). Node v is inserted into its own counter using the SplitMix64 finalizer hash, which matches the hash used in the CUDA kernels (Section 3.4) for consistent crossplatform behaviour. Two register arrays are double-buffered in a flat N × m/2 byte layout (two 4-bit registers per byte) for cache-efficient SIMD access. Iteration. At each step t, every node v propagates its neighbourhood estimate to its neighbours by computing the element-wise maximum (register-wise union) of its current HLL counter with those of all adjacent nodes: next[v][j] = max cur[v][j], max cur[w][j] , j = 0, . . . , m − 1. (2) w∈N (v)
After the union step the HLL estimator [15] (with αm bias correction and small-range linear counting) converts each register set to a cardinality estimate ĉt [v] ≈ |B(v, t)|. Distance accumulation. The increase in estimated neighbourhood size between iterations t − 1 and t approximates the number of nodes first reached at distance t. Sum-of-distances is accumulated as sum_d[v] += t · ĉt [v] − ĉt−1 [v] . (3) Visual Mean Depth then follows as MD(v) = sum_d[v]/(Nv − 1), where Nv = |C(v)| is the exact component size stored in the VGACSR03 file. Using exact component sizes for the denominator of integration formulas avoids amplifying HLL noise through division by an approximate quantity. Convergence. Propagation terminates when no node’s cardinality estimate increases by more than 0.5 (i.e. the rounded change is zero), which occurs after at most D iterations where D is the diameter. In practice the iteration count equals the graph diameter D, which depends on study area extent, visibility radius, and grid spacing: boundedradius configurations at fine spacing converge in fewer than 10 iterations, while city-scale unlimited-radius graphs can require 40 or more. When a depth limit d is set, HyperBall terminates after exactly d iterations, so the runtime is directly proportional to the depth parameter. Metric derivation. From MD(v) and exact component size Nv , the five BFS-derived metrics are computed in closed form: Integration [HH] as the reciprocal of Real Relative Asymmetry (RRA) [2]; Integration [Tekl] as log2 ((MD + 2)/3); Integration [P-value] as max(0, 1 − RA) [6] where RA = 2(MD − 1)/(Nv − 2); and Point First Moment as MD(v) × deg(v). Local metrics (Connectivity, Control, Controllability, Clustering, Point Second Moment) are computed exactly from the 1-hop neighbourhood and are unaffected by the HLL approximation. Entropy and Relativised Entropy require the full depth distribution and are returned as NaN, consistent with landmark BFS. 3.4
GPU Acceleration
The CPU HyperBall implementation (Section 3.3) is bottlenecked by DRAM bandwidth: each iteration reads every node’s m-register counter and those of all its neighbours from main memory. At 2.9 million nodes with p = 8 (m = 256 registers, packed to 128 B per node) and 60 billion edges, each iteration performs approximately 7.7 TB of random register reads at 40 GB s−1 DDR4 bandwidth, yielding approximately 190 s per iteration and 1.6 h total for D ≈ 30 iterations. The GPU solution moves the HLL registers to device memory, where the RTX 3080 Ti Laptop GPU’s 512 GB s−1 peak GDDR6 bandwidth largely eliminates the register-access bottleneck. When the compressed graph exceeds 16 GB VRAM it is streamed from host memory to the device in batches per iteration, with LEB128 decoding performed ondevice. This is the critical enabling property of the delta-compressed CSR format: the sequential scan pattern of HyperBall allows contiguous byte ranges to be transferred and decoded without frontier-dependent random access. CUDA kernels.
Four kernels implement the GPU HyperBall pipeline (Figure 2): 5
City-Scale Visibility Graph Analysis via GPU-Accelerated HyperBall
A P REPRINT
Algorithm 1 HyperBall for VGA metrics Require: Graph G = (V, E) in delta-compressed CSR; precision p; exact component sizes {Nv } 1: m ← 2p ; allocate cur[N × m/2], next[N × m/2] (zero-initialised; 4-bit packed) 2: for each v ∈ V do 3: Insert v into cur[v] using SplitMix64 hash 4: end for 5: Estimate initial cardinalities ĉ0 [v] for all v 6: for t = 1, 2, . . . do 7: for each v ∈ V in parallel do 8: next[v] ← cur[v] 9: for each w ∈ N (v) do 10: next[v] ← max(next[v], cur[w]) {register-wise} 11: end for 12: end for 13: Estimate ĉt [v] for all v {HLL estimator} 14: sum_d[v] += t · (ĉt [v] − ĉt−1 [v]) for all v 15: if maxv (ĉt [v] − ĉt−1 [v]) ≤ 0.5 then 16: break {converged} 17: end if 18: swap cur ↔ next 19: end for 20: Derive VGA metrics from sum_d[v] and exact Nv
1. hll_init_kernel (one thread per node): zeros all registers and inserts each node into its own counter using the SplitMix64 hash, identical to the Rust CPU implementation. 2. hll_decode_union_kernel (one block per node): thread 0 decodes the LEB128 delta stream for its node’s neighbours into a 4096-entry shared-memory buffer. All threads then stride over the m HLL registers, computing the element-wise maximum against the decoded neighbours’ registers in device memory. Nodes with more than 4096 neighbours are handled in chunks with synchronisation between each chunk. 3. hll_cardinality_kernel (one block per node): threads stride over the m registers accumulating the harmonicmean sum; warp-level shuffle reduction followed by shared-memory cross-warp reduction yields the per-node cardinality estimate, applying HLL++ bias correction and small-range linear counting. 4. hll_accumulate_kernel (one thread per node): accumulates the distance sum via Equation (3) and sets an atomic convergence flag (atomicOr) if any node’s cardinality increased by more than 0.5. All kernels use 4-bit packed register format (two registers per byte) and support precisions up to p = 16 via register striding with block sizes up to 1024. When optional Hilbert reordering is enabled (VGACSR03 format), the decodeunion kernel benefits from improved L2 cache locality as consecutive blocks access overlapping neighbour sets; this is most beneficial for unlimited-depth runs with many iterations. Dual-stream execution. A second CUDA stream handles host-to-device transfers of compressed graph batches, overlapping PCIe data movement with kernel execution on the compute stream. The HLL register arrays (N × m/2 bytes × 2 buffers) remain resident in VRAM throughout all iterations.
4
Experimental Evaluation
4.1
Experimental Setup
All experiments run on a laptop workstation with an Intel i7-12700H (20 logical cores), 32 GB DDR4 RAM, and an NVIDIA RTX 3080 Ti Laptop GPU (16 GB GDDR6, 256-bit bus, PCIe 4.0 x8), running CUDA 12.0 (sm_86). The study area is Valdivia, Chile (EPSG:32718), with building footprints from OpenStreetMap and a municipal boundary polygon. To evaluate both accuracy and scaling, we construct circular sub-regions of increasing radius (200 m, 300 m, 500 m, 750 m and 1000 m) centred on the city centre, with grid spacings of 3 m, 5 m, 7 m, 10 m and 20 m and unlimited visibility radius, producing problem sizes ranging from 235 to 236 000 grid cells. All runs use the sparkSieve2 visibility backend (Section 3.1), which produces identical edge sets to depthmapX, isolating accuracy 6
City-Scale Visibility Graph Analysis via GPU-Accelerated HyperBall
Host (CPU)
A P REPRINT
Device (GPU) Transfer Stream
Compressed CSR
Compute Stream
hll_init_kernel
(mmap, LEB128)
1 thread/node
iteration 0 only
hll_decode_union_kernel
GPU buffer chunk b
fused LEB128 decode + union × B batches
PCIe →
sync (all batches complete)
t = 1…D
hll_cardinality_kernel warp-shufÒe reduction
hll_accumulate_kernel atomicOr convergence check
swap buffers GPU compute kernel
HLL registers (VRAM) N × m/2 bytes × 2 buffers
PCIe transfer batch VRAM-resident data
Figure 2: GPU HyperBall execution pipeline. HLL register arrays reside in VRAM throughout. Compressed graph data is streamed to the device in batches of 10 000 nodes via a transfer stream, overlapping with kernel execution on the compute stream. The fused decode-union kernel decodes LEB128 varints in shared memory and performs register max-union in a single pass.
differences to the HLL approximation alone. Both tools are run at topological depth limit 3 (the standard local measure in VGA practice [6, 7]). The baseline is depthmapXcli [4] (version 0.8.0), run with a 30 min timeout per configuration. Our tool is tested at HLL precisions p ∈ {8, 10, 12}, with p = 10 as the recommended default balancing accuracy and speed.
4.2
Accuracy Validation
We validate HyperBall metric estimates against depthmapX across 20 matched configurations (all area/spacing combinations where depthmapX completed within the timeout and both tools produced spatially coincident grid points, all at depth limit 3). For each configuration, we spatially join the output point sets and compute Pearson r on Visual Mean Depth and Spearman ρ on Integration [HH]. We use Spearman rank correlation for Integration [HH] because the Hillier–Hanson normalisation applies a nonlinear transform that amplifies small mean-depth errors into large absolute integration differences, particularly for nodes near the distribution extremes; R2 in the original scale is unreliable as an accuracy metric for this quantity. Table 1 summarises accuracy across HLL precisions. At p = 10 (the recommended default), Mean Depth achieves Pearson r = 0.999 with median relative error 1.7 %, and Integration [HH] achieves Spearman ρ = 0.893 on average. Increasing to p = 12 reduces median error to 0.8 % with ρ = 0.964, at the cost of ∼4× longer BFS time (Section 4.3). At depth limit 3, Mean Depth values cluster in a narrow range (most nodes are reached within 3 hops in high-connectivity visibility graphs), so Pearson r is more sensitive to small absolute errors than in unlimited-depth configurations; median relative error is a more stable accuracy indicator. Figure 3 shows representative per-node scatter plots for the validation configuration. Local metrics (connectivity, control, controllability, clustering coefficient, point second moment) are computed exactly from the 1-hop neighbourhood and are unaffected by the HLL approximation. Accuracy improves monotonically with precision; it also varies with problem geometry, as larger study areas contain more spatially diverse subgraphs that provide better averaging of HLL noise (Figure 9). 7
City-Scale Visibility Graph Analysis via GPU-Accelerated HyperBall
A P REPRINT
Table 1: HyperBall accuracy vs depthmapX across HLL precisions (depth limit 3). Mean Depth uses Pearson r; Integration [HH] uses Spearman ρ. Values are averages over 20 matched configurations (235–42 705 cells). Ranges in parentheses.
3.00
p
MD r (range)
MD med. err
IHH ρ (range)
n
8 10 12
0.996 (0.983–0.999) 0.999 (0.998–1.000) 1.000 (0.999–1.000)
4.0% 1.7% 0.8%
0.789 (0.301–0.974) 0.893 (0.708–0.994) 0.964 (0.882–0.994)
20 20 20
r = 0.9998
40
Spearman = 0.9344 log r = 0.9917
2.75
30
2.25
Ours
Ours
2.50 2.00 1.75
20 10
1.50 1.25
0 1.5
2.0
depthmapX
2.5
0
3.0
(a) Visual Mean Depth
10
20
depthmapX
30
40
(b) Integration [HH]
Figure 3: Our tool (p = 10, depth limit 3) vs depthmapX for a representative configuration. Mean Depth (left) annotated with Pearson r; Integration [HH] (right) annotated with Spearman ρ.
4.3
Performance and Scaling
Figure 6 shows wall-clock time versus grid cells on a log-log scale, with visibility construction (Figure 6a) and HyperBall metric computation (Figure 6b) plotted separately for each HLL precision. Because configurations with the same cell count but different radius/spacing combinations produce different edge counts, the cell-based view exhibits scatter at each cell count. Figure 7 re-plots the same data against edge count |E|, which collapses this scatter into coherent scaling trends and enables direct comparison with the city-scale run (§5). depthmapX completed 20 of the 25 configurations within the 30 min timeout; its largest completed run was 42 705 cells (1000 m radius, 7 m spacing) in 1732 s (∼29 min). Speedup grows rapidly with problem size: 34× at 4100 cells, 152× at 11 500 cells, and 214× at 24 000 cells (all at p = 10; Figure 8). At the largest matched configuration (42 705 cells, 161 million edges), our tool completes in 7.25 s versus depthmapX’s 1732 s—a 239× speedup. Beyond depthmapX’s timeout, our tool handles 236 000 cells (1000 m radius, 3 m spacing, 4.8 billion edges) in 137 s at p = 10. Edge density and superlinear scaling. Both tools exhibit superlinear scaling because unlimited visibility radius causes edge density to grow with problem size. Table 2 quantifies this: average degree rises from 106 at 235 cells to 20 237 at 236 000 cells, meaning |E| grows nearly quadratically (∼N 1.9 ) with N under unlimited visibility. HyperBall’s theoretical cost is O(D × |E| × 2p ): with |E| ∝ N 2 the analysis phase becomes the bottleneck at high precision. In practice, most urban VGA studies use a bounded visibility radius (100 m to 400 m), which caps average degree and restores O(N ) edge growth—the superlinear tail is an artefact of the unbounded benchmark configuration, not the algorithm. 8
City-Scale Visibility Graph Analysis via GPU-Accelerated HyperBall
A P REPRINT
Table 2: Edge density growth under unlimited visibility. Average degree rises with problem size because larger study areas expose more inter-visible cell pairs. With a bounded visibility radius, average degree stabilises and |E| grows linearly with N . Cells
Edges
Avg. degree
235 1007 4106 11 555 42 705 61 005 128 943 235 983
25K 404K 6.5M 50M 161M 808M 2.3B 4.8B
106 401 1576 4321 3775 13 237 17 836 20 237
Config 200 m / 20 m 200 m / 10 m 200 m / 5 m 200 m / 3 m 1000 m / 7 m 500 m / 3 m 750 m / 3 m 1000 m / 3 m
Table 3: Pipeline phase breakdown: visibility graph construction (VIS) versus GPU HyperBall BFS (BFS) time in seconds, with BFS share of total time in parentheses. Grid generation time is omitted (<2 s in all cases). All runs at depth limit 3. p=8
p = 10
p = 12
Cells
Edges
Config
VIS
BFS
VIS
BFS
VIS
BFS
11 555 23 991 61 005 128 943 235 983
50M 207M 808M 2.3B 4.8B
200 m / 3 m 300 m / 3 m 500 m / 3 m 750 m / 3 m 1000 m / 3 m
0.8 3.0 11.9 32.2 78.6
0.4 (35%) 1.1 (26%) 3.5 (23%) 9.6 (23%) 20.6 (21%)
0.7 3.1 12.1 32.3 79.5
0.6 (47%) 2.0 (40%) 7.9 (39%) 22.2 (41%) 51.6 (39%)
0.8 3.0 11.8 31.4 81.3
1.9 (72%) 7.4 (71%) 32.2 (73%) 104 (77%) 286 (78%)
Pipeline phase breakdown. Total runtime comprises three phases: grid generation (constant per area), visibility graph construction, and GPU HyperBall BFS. At depth limit 3, the BFS and visibility phases are roughly balanced: BFS accounts for 39 % to 47 % of combined phase time across configurations at p = 10 (Table 3). At p = 8, BFS drops to 21 % to 35 %; at p = 12, BFS dominates at large scale (78 % at 236 000 cells) as the 4× register count increase outweighs the visibility phase. Depth-limited analysis. Both depthmapX and our tool support topological depth limits (called radius-n in axial analysis [2]), restricting BFS to a maximum of n hops from each source node. Depth-3 local integration is the canonical local VGA measure [6, 7], widely used for predicting pedestrian movement at neighbourhood scale [18, 1]. Global (unlimited-depth) integration captures macro-scale structure but is sensitive to study area boundary definition [19]—a limitation noted by Ericson et al. [20], who showed that VGA metrics vary with both resolution and boundary placement. Table 4 compares BFS time for both tools across depth limits at 11 555 cells (200 m radius, 3 m spacing, 50M edges). depthmapX’s BFS time shows no substantial reduction with depth limiting at this configuration (Figure 4a). Inspection of the depthmapX source code (vgavisualglobal.cpp) confirms that the BFS frontier is correctly pruned: nodes beyond the depth limit are counted but not expanded. The flat timing arises instead from the topology of visibility graphs. With unlimited visibility radius and 3 m spacing, each node sees hundreds of others at hop distance 1 (average degree 4321 at this configuration; Table 2). The graph diameter is consequently very small—typically 3–6 hops—so a depth-3 BFS already reaches the vast majority of reachable nodes and performs nearly the same work as an unlimited traversal. Additionally, depthmapX’s per-source BFS clears a dense visited-flag matrix covering the full grid (rows × cols) before each source node, imposing a fixed O(G) overhead per source regardless of how many nodes the BFS actually visits. HyperBall, by contrast, converges in exactly min(d, D) iterations where d is the depth limit and D the diameter. At depth limit 3, our BFS completes in 0.72 s versus depthmapX’s 253 s—a 352× BFS-phase speedup (Figure 4; endto-end speedup is lower as visibility construction cost is shared across depth settings). With early stopping enabled, unlimited-depth HyperBall converges at the graph diameter in 1.72 s—2.4× slower than depth-3 but still 157× faster than depthmapX. The architectural difference is fundamental: per-source BFS cost depends on the number of nodes visited, which plateaus rapidly in high-connectivity graphs; HyperBall cost depends on the number of iterations, which scales linearly with the depth limit regardless of graph connectivity. BFS time increases monotonically with depth setting (Table 4): 0.72 s at d = 3, 0.91 s at d = 5, 1.70 s at d = 20—while depthmapX remains at 252 s to 270 s throughout. Since practitioners routinely use radius-3 or radius-5 for local VGA, this depth-proportional speedup applies to the most common analytical workflow. Mean Depth accuracy at p = 10 is Pearson r ≥ 0.999 across all 9
City-Scale Visibility Graph Analysis via GPU-Accelerated HyperBall
A P REPRINT
Table 4: Depth-limited BFS comparison at 11 555 cells (200 m radius, 3 m spacing, 50M edges, p = 10). depthmapX BFS time varies little across depth settings; HyperBall converges in min(d, D) iterations, directly exploiting the reduced depth. Depth
dmX BFS (s)
Ours BFS (s)
BFS Speedup
MD r
270.3 252.3 263.5 261.1 253.4
1.72 1.70 1.55 0.91 0.72
157× 148× 170× 287× 352×
1.000 1.000 1.000 1.000 0.999
Unlimited 20 10 5 3
200 m radius, 3 m spacing (11,555 cells) depthmapX Ours
102
101
100 3
5
10
Depth limit
(b) Depth-limiting speedup
2.5
BFS speedup vs unlimited
BFS / HyperBall time (s)
(a) Analysis time
2.0 1.5 1.0 0.5 0.0
20
depthmapX Ours
3
5
10
Depth limit
20
Figure 4: Depth-limited BFS comparison at 11 555 cells (p = 10). (a) Absolute BFS time: depthmapX shows no reduction with decreasing depth, while HyperBall cost scales linearly with iteration count. (b) Speedup relative to each tool’s own unlimited-depth time: our depth-3 BFS is 2.4× faster than our unlimited run, while depthmapX shows negligible benefit from depth limiting.
tested depth settings including unlimited (Figure 5), confirming that the SparkSieve visibility port produces identical edge sets and the HLL approximation introduces minimal error regardless of convergence depth.
5
Case Study: Valdivia, Chile
To demonstrate city-scale applicability, we ran our full pipeline on the 49.45 km2 Valdivia study area at 5 m grid spacing with a 400 m visibility radius and depth limit 3, producing a graph of 2 706 968 nodes and 12.1 × 109 edges. The complete analysis—grid generation, SparkSieve visibility construction, delta-compressed CSR serialisation, and GPU HyperBall metric computation at p = 10—completed in 333 s (∼5.5 min) on a single laptop GPU (RTX 3080 Ti, 16 GB). Figure 10 shows Visual Integration [HH] at four zoom levels. At the city scale, the commercial core along Avenida Picarte and the central grid around Plaza de la República exhibit the highest integration, consistent with prior neighbourhood vitality analysis by Zumelzu & Barrientos-Trinanes [11]. The river corridor and peripheral residential areas show lower values. At street level, the 5 m resolution reveals fine-grained variation: individual building footprints create local shadows in the integration field, and through-block passages appear as narrow high-integration corridors. This configuration is far beyond the practical reach of exact BFS tools such as depthmapX, which timed out on graphs exceeding 42 705 cells in our benchmarks (§4.3). The two dominant phases—visibility construction (146 s) and GPU HyperBall BFS (133 s)—account for 279 s of the 333 s total, with the remainder spent on grid generation (32 s), obstacle rasterisation (11 s), and GeoPackage output (2 s). Both dominant phases fall within the 95% prediction 10
City-Scale Visibility Graph Analysis via GPU-Accelerated HyperBall
A P REPRINT
200 m radius, 3 m spacing (11,555 cells) (b) Integration [HH]
0.9998
Spearman vs depthmapX
Pearson r vs depthmapX
(a) Mean Depth 0.9996 0.9994 0.9992 0.9990 3
5
10
Depth limit
0.92 0.91 0.90 0.89 0.88
20
3
5
10
Depth limit
20
Figure 5: Accuracy across depth limits at 11 555 cells (p = 10, depths 3–unlimited). (a) Mean Depth Pearson r ≥ 0.999 at all depths. (b) Integration [HH] Pearson r remains above 0.97 at all tested depths.
(a) Visibility graph construction
depthmapX depthmapX (est.) depthmapX ( 30 min) p=8 p=10 p=12
105
102
104
Analysis time (s)
Visibility construction time (s)
(b) HyperBall metric computation
depthmapX Ours (SparkSieve) SparkSieve
103
101 100
103 102 101 100
10 1
10 1
10 2
10 2 102
103
104
Grid cells
105
102
103
104
Grid cells
105
Figure 6: Log-log scaling by grid cells. (a) Visibility graph construction: our SparkSieve implementation compared with depthmapX. Both use the same algorithm; our parallelised Rust port is consistently faster. (b) HyperBall metric computation by HLL precision: p = 8 and p = 10 remain well below depthmapX at all sizes; p = 12 approaches depthmapX cost at scale. Dashed curves are quadratic fits in log-log space. bands extrapolated from the benchmark surface (Figure 7), confirming that performance scales predictably to city-scale graphs.
6
Discussion
Accuracy of HLL-based metrics. The HyperLogLog approximation introduces a precision-dependent bias in BFS√ derived metrics. At p = 10, the standard error on raw cardinality is 1.04/ 210 ≈ 3.2 %, but per-iteration HLL noise partially cancels in the distance sum, yielding empirical median relative errors of 1.7 % on Mean Depth (Table 1). The Hillier–Hanson Integration normalisation amplifies errors for nodes near the distribution extremes, making R2 in the original scale an unreliable accuracy metric. We recommend reporting Spearman ρ or log-space Pearson r for 11
City-Scale Visibility Graph Analysis via GPU-Accelerated HyperBall
(a) Visibility graph construction
101
depthmapX depthmapX O(E1.2) HyperBall (p=10) p=10 (pred.) City run (p=10)
2 min
103 102
Analysis time (s)
Visibility construction time (s)
(b) HyperBall metric computation
depthmapX depthmapX O(E0.7) Ours (SparkSieve) SparkSieve O(E0.8) City run (2.7M cells)
102
A P REPRINT
100 10 1
2 min
101 100 10 1
10 2
104
105
106
107
108
Graph edges
109
10 2
1010
104
105
106
107
108
Graph edges
109
1010
Figure 7: Log-log scaling by graph edges. Plotting time against |E| collapses the radius/spacing scatter visible in Figure 6, because runtime depends on edge count, not cell count alone. Shaded bands are 95% prediction intervals from quadratic log-log fits. Star markers show the city-scale run (§5; 2.7 × 106 cells, 12.1 × 109 edges), which falls within both prediction bands.
Integration [HH], and note that the Teklenburg formulation is more robust to approximation error due to its logarithmic transform. Resolution sensitivity. Ericson et al. [20] showed that VGA metrics vary with grid spacing. Our system’s speed makes multi-resolution analysis practical: a full sweep across five spacings and five area sizes at p = 10 completes in under 5 min (Table 3), enabling practitioners to assess robustness without the days-long depthmapX runs previously required. Depth-proportional speedup as a practical advantage. The most significant practical consequence of HyperBall for VGA is that computation time scales with topological depth. In standard VGA practice, local integration at depth-3 or depth-5 is the primary analytical tool for neighbourhood-scale studies, while global (unlimited-depth) metrics are used selectively and are known to be sensitive to study area boundaries [1, 19]. depthmapX’s per-source BFS correctly prunes the frontier at the depth limit, but this yields negligible speedup because visibility graphs have very small diameters (typically 3–6 hops): high node connectivity means that even a depth-3 BFS visits nearly every reachable node, performing essentially the same work as an unlimited traversal. This is not a missed optimisation in depthmapX—it is an inherent property of per-source BFS on high-connectivity graphs. Moreover, depthmapX’s per-source BFS is the natural architecture for a general-purpose space syntax platform that also supports axial, segment, and angular analysis, all of which require exact per-node distances or full depth distributions that HyperBall cannot provide (our system returns NaN for entropy and relativised entropy). The tradeoff we make—approximate cardinalities in place of exact distances—is specifically suited to VGA’s distance-sum metrics. Our system sidesteps the frontier plateau entirely: HyperBall’s cost depends on iteration count, not nodes visited, so converging in min(d, D) iterations gives a speedup proportional to D/d regardless of graph connectivity. At depth-3 this yields a 352× BFS-phase speedup at the tested configuration—the depth-3 analysis that practitioners already prefer is also the fastest to compute. At unlimited depth, HyperBall converges at the graph diameter (typically 3–6 iterations) in 1.72 s—still 157× faster than depthmapX, while depth-3 provides an additional 2.4× speedup over unlimited. This alignment between analytical best practice and computational efficiency means that city-scale local VGA becomes routine rather than exceptional. For the less common case of unlimited-depth global analysis, a bounded visibility radius (typically 100 m to 400 m) caps edge density and graph diameter, keeping total work manageable [6, 7]. Limitations. The current implementation uses 2D line-of-sight visibility with no terrain model; hilly cities would require a 2.5D or 3D extension. Vegetation is included as a sightline obstruction but not as a spatial barrier (pedestrians can walk through vegetated areas). The GPU pipeline requires CUDA-capable hardware; without a GPU, the CPU HyperBall fallback is available but substantially slower. 12
City-Scale Visibility Graph Analysis via GPU-Accelerated HyperBall
A P REPRINT
Speedup over depthmapX by precision p=8
p=10
p=12
102
101
Grid spacing
Grid spacing
Grid spacing
5m 35.1x 99.7x 204.8x >30m >30m 5m 34.4x 97.0x 166.9x >30m >30m 5m 31.7x 60.8x 96.2x >30m >30m
7m 13.8x 33.5x 88.2x 174.3x244.3x 7m 13.1x 29.6x 75.4x 157.4x239.0x 7m 11.2x 25.2x 56.6x 101.9x145.5x 100
10m 2.6x 10.1x 25.1x 58.3x 111.1x10m 2.6x 10.3x 25.6x 59.0x 104.7x10m 2.6x 9.7x 21.6x 45.8x 79.7x
Speedup (T_depthmapX / T_ours)
3m 164.8x263.4x >30m >30m >30m 3m 151.6x214.4x >30m >30m >30m 3m 78.2x 111.3x >30m >30m >30m
10 1 20m 0.6x 1.2x 2.6x 4.8x 9.2x 20m 0.5x 1.3x 2.6x 4.9x 9.0x 20m 0.5x 1.3x 2.6x 4.7x 8.6x 200m300m500m750m1000m
Area radius
200m300m500m750m1000m
Area radius
200m300m500m750m1000m
Area radius
Figure 8: Speedup of our tool over depthmapX (Tdm /Tours ) by area radius and grid spacing, at four HLL precisions. Hatched cells indicate depthmapX timeouts (no reference time available). Values below 1× at coarse spacings reflect GPU initialisation overhead dominating small graphs (see crossover discussion in text). GPU scaling ceiling. The quadratic log-log fits in Figure 7 show that our GPU curves steepen at high edge counts, while depthmapX maintains consistent power-law scaling. This reflects GPU resource saturation: at the city-scale run (12.1 × 109 edges), batch streaming across PCIe and VRAM pressure cause per-edge throughput to degrade. Extrapolating both fits, the BFS-phase crossover—where depthmapX’s linear-memory exact BFS would match HyperBall— occurs around 1012 edges, corresponding to roughly 50 million cells at 5 m spacing (a ∼35 km × 35 km metropolitan area with unlimited visibility). At that scale both tools would require years of compute, so the crossover is theoretical rather than practical. Moreover, the saturation point is hardware-dependent rather than algorithmic: our benchmarks use a 2021-era laptop GPU with 16 GB VRAM and a PCIe 4.0 ×8 link—a modest configuration by current standards. Unified-memory architectures such as Apple Silicon, where GPU compute shares the full system memory pool without PCIe streaming, would eliminate the batch-transfer bottleneck entirely and push the superlinear regime to substantially higher edge counts. Future work. Warp-cooperative decoding of the LEB128 stream could further reduce per-node overhead in the decode-union kernel. Multi-GPU scaling would enable metropolitan-scale analysis at fine resolution. A QGIS plugin wrapping the Rust core, in the spirit of the Space Syntax Toolkit [21], would make the tool accessible to space-syntax practitioners without command-line expertise. Multi-radius blending—weighting HyperBall results across several visibility radii—is a natural extension that we defer to a follow-up study.
7
Conclusion
We presented a system that enables city-scale Visibility Graph Analysis by combining delta-compressed CSR storage, HyperBall distance estimation, and GPU acceleration, using the SparkSieve visibility algorithm ported from depthmapX to ensure identical edge sets. The most consequential property of HyperBall for VGA practice is that computation time scales with topological depth: at radius-3—the standard local measure in space syntax [2, 1]—the BFS phase achieves a 352× speedup over depthmapX, whose BFS time is invariant to depth setting. This alignment between analytical best practice and computational efficiency means that the analyses practitioners most commonly 13
City-Scale Visibility Graph Analysis via GPU-Accelerated HyperBall
A P REPRINT
0.92
0.3 5m
7m
10 m
Grid spacing
20 m
0.96 0.82 0.88
0.89 0.92 0.97
0.95
0.5 0.4
p=8 p=10 p=12
3m
0.6
p=8 p=10 p=12
3m
0.30
0.94
0.7 0.59
Spearman
Pearson r
0.96
0.81
0.8
0.98
0.90 0.91
0.9
(b) Integration [HH] 0.83
1.00 1.00
1.0
0.98
1.00 1.00 1.00
1.00 1.00 1.00
0.99 1.00 1.00
1.00
1.00 1.00 1.00
(a) Mean Depth
1.02
0.99 0.99
Accuracy vs depthmapX (200 m, 300 m, 500 m, 750 m, 1000 m radius)
5m
7m
10 m
Grid spacing
20 m
Figure 9: Accuracy heatmaps by area radius and grid spacing. Top row: Pearson r for Mean Depth; bottom row: Spearman ρ for Integration [HH]. Accuracy improves monotonically with precision and problem size.
perform are also the fastest to compute. End-to-end, our tool achieves a 239× speedup over depthmapX at the largest matched configuration (42 705 cells, p = 10), and scales to 236 000 cells (4.8 × 109 edges) in 137 s. At city scale, the full pipeline completes 2.7 million cells in 5.5 min. Mean Depth accuracy is Pearson r = 0.999 (median relative error 1.7 %) at p = 10, and users can tune HLL precision to trade accuracy for speed. Together, these contributions open VGA to study areas and resolutions previously infeasible with existing tools.
References [1] Bill Hillier. Space is the Machine: A Configurational Theory of Architecture. Cambridge University Press, Cambridge, 1996. [2] Bill Hillier and Julienne Hanson. The Social Logic of Space. Cambridge University Press, Cambridge, 1984. [3] Alasdair Turner, Maria Doxa, David O’Sullivan, and Alan Penn. From isovists to visibility graphs: a methodology for the analysis of architectural space. Environment and Planning B: Planning and Design, 28(1):103–121, 2001. [4] Tasos Varoudis. depthmapX: Multi-platform spatial network analysis software. https://github.com/ SpaceGroupUCL/depthmapX, 2012. Open-source implementation of space syntax methods. [5] Paolo Boldi and Sebastiano Vigna. In-core computation of geometric centralities with HyperBall: A hundred billion nodes and beyond. In Proceedings of the IEEE 13th International Conference on Data Mining Workshops (ICDMW), pages 784–791. IEEE, 2013. [6] Alasdair Turner. Depthmap 4: A researcher’s handbook. Technical report, Bartlett School of Graduate Studies, University College London, London, 2004. [7] Petros Koutsolampros, Kerstin Sailer, Tasos Varoudis, and Rosie Haslem. Dissecting visibility graph analysis: the metrics and their role in understanding workplace human behaviour. In Proceedings of the 12th International Space Syntax Symposium, pages 191:1–191:24, Beijing, China, 2019. [8] Michael L Benedikt. To take hold of space: Isovists and isovist fields. Environment and Planning B: Planning and Design, 6(1):47–65, 1979. [9] Jan AF Teklenburg, Harry JP Timmermans, and Anton F van Wagenberg. Space syntax standardised integration measures and some simulations. Environment and Planning B: Planning and Design, 20(3):347–357, 1993. 14
City-Scale Visibility Graph Analysis via GPU-Accelerated HyperBall
A P REPRINT
[10] Duncan J Watts and Steven H Strogatz. Collective dynamics of ‘small-world’ networks. Nature, 393(6684):440– 442, 1998. [11] Antonio Zumelzu and Melissa Barrientos-Trinanes. Analysis of the effects of urban form on neighborhood vitality: five cases in Valdivia, Southern Chile. Journal of Housing and the Built Environment, 34:897–925, 2019. [12] Peiman Amini Behbahani, Ning Gu, and Michael Ostwald. Viraph: exploring the potentials of visibility graphs and their analysis. Visualization in Engineering, 5(17), 2017. Open Access. [13] David Eppstein and Joseph Wang. Fast approximation of centrality. Journal of Graph Algorithms and Applications, 8(1):39–45, 2004. [14] Michalis Potamias, Francesco Bonchi, Carlos Castillo, and Aristides Gionis. Fast shortest path distance estimation in large networks. In Proceedings of the 18th ACM Conference on Information and Knowledge Management, pages 867–876, 2009. [15] Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. HyperLogLog: the analysis of a nearoptimal cardinality estimation algorithm. Discrete Mathematics and Theoretical Computer Science, AH:137– 156, 2007. [16] Paolo Boldi, Marco Rosa, and Sebastiano Vigna. HyperANF: Approximating the neighbourhood function of very large graphs on a budget. In Proceedings of the 20th International Conference on World Wide Web, pages 625–634, 2011. [17] Rayon Contributors. Rayon: A data parallelism library for Rust. https://github.com/rayon-rs/rayon, 2024. Version 1.10. [18] Bill Hillier, Alan Penn, Julienne Hanson, Tadeusz Grajewski, and Jin Xu. Natural movement: Or, configuration and attraction in urban pedestrian movement. Environment and Planning B: Planning and Design, 20(1):29–66, 1993. [19] Jorge Gil. Street network analysis “edge effects”: Examining the sensitivity of centrality measures to boundary conditions. Environment and Planning B: Urban Analytics and City Science, 44(5):819–836, 2017. [20] John David Ericson, Elizabeth R Chrastil, and William H Warren. On the robustness of visibility graph analysis in the built environment: Repeat measures, boundary effects, and the impact of grid resolution. Environment and Planning B: Urban Analytics and City Science, 48(4):879–896, 2021. [21] Jorge Gil, Tasos Varoudis, Kayvan Karimi, and Alan Penn. The space syntax toolkit: Integrating depthmapX and exploratory spatial analysis workflows in QGIS. In Proceedings of the 10th International Space Syntax Symposium (SSS10), pages 148:1–148:12, London, UK, 2015. Space Syntax Laboratory, The Bartlett, UCL.
15
City-Scale Visibility Graph Analysis via GPU-Accelerated HyperBall
Valdivia VGA
A P REPRINT
2,706,968 cells, 12.1B edges, 5 m grid, 400 m radius
Full Study Area (10.5 × 12.5 km)
City Centre (4.0 × 4.0 km)
16
2 km
Visual Integration [HH]
15
1 km
14 13
Street Detail (0.5 × 0.5 km)
Central Core (1.5 × 1.5 km)
12 11 10
200 m
100 m
Figure 10: Visual Integration [HH] for Valdivia at 5 m spacing with 400 m radius (2.7 × 106 cells, 12.1 × 109 edges). Successive panels zoom from the full 49.45 km2 study area to a 500 m × 500 m street-level detail. Dashed boxes indicate the extent of the next zoom level.
16