Measuring the Priority Profile of Exact Distance Labels on Real Networks

Many systems need fast exact shortest-path distances between nodes of a large network. Examples include routing on road maps, measuring proximity in social graphs, and serving queries in web-scale indexes. A standard way to get these distances is a distance labeling: each node stores a short list of (hub, distance) pairs, and the distance between two nodes is computed from their two lists alone, with no graph search at query time. Theory has recently asked a sharper question. When some nodes matter more than others (emergency facilities, backbone routers, popular destinations), can the $j$-th most important node get a label whose size depends only on $j$, and not on the size of the network? Labelings vs. Embeddings: On Distributed and Prioritized Representations of Distances proves several answers. General graphs need, and can achieve, about $j$ entries for the $j$-th node. Trees need only about $\log j$. Planar graphs, which are close to road networks, are as hard as general graphs. None of these bounds has ever been implemented or measured.

This proposal starts from a simple observation that connects the theory to practice. Pruned Landmark Labeling, the most widely used exact labeling method, run with nodes processed in priority order instead of degree order, already meets the theoretical $O(j)$ guarantee: every hub in a node's label is processed no later than that node. So the open questions are empirical. On real web, social and road graphs, how far below the worst-case curve $j$ do the labels of high-priority nodes actually fall? Does this depend on topology the way the theory predicts, close to $\log j$ on tree-like regions and close to $j$ on road-like graphs? What does the guarantee cost in total index size when priorities disagree with the structural order that makes practical labeling efficient? We would answer these questions with a priority-first construction whose remaining ordering adapts to the topology. We would also test whether allowing $(1+\epsilon)$ approximation breaks the planar $\Omega(j)$ barrier in practice.

Core Claim

We define the priority profile of a labeling as $s(j) = |L(v_j)|$, the number of hub entries stored by the node of priority rank $j$. We summarize it by fitting

$$ s(j) \approx c\, j^{\alpha} $$

over a range of ranks, where $c$ is a constant and $\alpha$ is the empirical growth exponent. The theory brackets $\alpha$: the trivial scheme and the general and planar lower bounds give $\alpha = 1$, and trees give near-logarithmic growth, so $\alpha \to 0$. Our claim has three parts. First, priority-first pruned labeling gives the exact $s(j) \le j$ guarantee by construction. Second, its measured $\alpha$ on real graphs is well below 1 and differs systematically between small-world and road topologies. Third, putting the top-$k$ priority nodes first and ordering the rest by a topology-appropriate rule keeps total index size close to the best topology-specific labelers for moderate $k$. The new contribution is not another labeling algorithm. It is the first measurement of priority-indexed label growth, together with a construction that makes the theoretical guarantee usable across topologies, rather than leaving it to either degree-ordered methods for small-world graphs or cut-hierarchy methods for road networks.

Research Program

Role of the theory. The theory sets the targets and constrains the design. Labelings vs. Embeddings: On Distributed and Prioritized Representations of Distances provides the $O(j)$ upper bound, the $\Omega(j)$ planar lower bound, the $O(\log j)$ tree bound, and the $O(\epsilon^{-2}\log j)$ bound for approximate labels in $\ell_p$ spaces. Its companion Labelings vs. Embeddings: On Distributed Representations of Distances explains why labels, unlike shared coordinate embeddings, let one node's size be independent of another's. The prioritized paper also proves that prioritized embeddings into $\ell_\infty$ coordinates are impossible below distortion 3. That result rules out an embedding-based design, so we work only with labels.

Role of practical labelers. The practical labelers supply the method and the failure modes. Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling (PLL) performs one pruned search per node in a chosen order. It uses degree order as a heuristic, which works because web and social graphs have a dense core of hubs. Scaling Distance Labeling on Small-World Networks (PSL) parallelizes this process. It also reports that low-degree peripheral nodes carry the largest labels, and that the method runs up to two orders of magnitude slower than specialized methods on high-diameter road networks. Hierarchical Cut Labelling - Scaling Up Distance Queries on Road Networks (HC2L) orders nodes by depth in a recursive balanced-cut hierarchy, which suits road networks but not graphs without small separators. None of these methods lets an external priority control label size. The low-degree observation from PSL is exactly the tension we measure: under degree order, low-priority periphery nodes have large labels, and we ask what happens to the profile and to total size when priority overrides structure.

Construction. We implement a priority-prefix labeler. The top-$k$ priority nodes are processed first, in priority order. The remaining nodes follow a pluggable suffix order: degree order for small-world graphs, and HC2L-style cut-depth order for road networks. For $j \le k$ the bound $s(j) \le j$ holds by construction. For $j > k$ we report the measured profile. We count label size in entries, matching the theory's accounting.

Approximate variant. In a second variant, a search is pruned whenever the existing labels already certify a distance within factor $(1+\epsilon)$. This tests whether approximation moves road networks from the exact planar regime toward the logarithmic regime that theory proves for trees and $\ell_p$ spaces. Theory proves neither direction for approximate prioritized labels in planar graphs, so the outcome is genuinely open. The compact approximate labels in Labeled Nearest Neighbor Search and Metric Spanners via Locality Sensitive Orderings give $O(\epsilon^{-1}\log^2 N)$ entries on planar graphs but are not prioritized. They are a reference point for what approximation can buy, not a competitor we reimplement.

Priority models. We use three priority models, because the answer should depend on how well priority agrees with structure. The first is priority equal to degree (full agreement). The second is uniformly random priority (no agreement). The third is spatially or community-clustered priority, for example all nodes in one metropolitan area or one detected community, which mimics domain-defined importance.

Baselines

The do-nothing reference is standard degree-ordered PLL, run unmodified on each graph, with the priority profile read off for the designated priority nodes. It is the most dangerous competitor. If priority nodes already receive small labels without any change, the guarantee is free and the construction adds nothing. As a scale anchor, PLL reportedly indexes the 194-million-edge Indochina graph in 6,068 seconds into a 22 GB index, with queries of 0.5 to 16 microseconds across its datasets (Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling).

The upper reference is the trivial prioritized table, in which every node stores its distance to all higher-priority nodes. It realizes $s(j) = j$ exactly. Its measured profile and size quantify what pruning buys on each topology.

The strongest existing method on road networks is HC2L. Its authors report queries 1.5 to 4 times faster than Hub Labelling, Highway Labelling and H2H, and labels up to 60% smaller than some baselines (Hierarchical Cut Labelling - Scaling Up Distance Queries on Road Networks). The file gives these only as ratios, and I found no absolute per-network label size for HC2L on Lacuna. We will therefore rerun it ourselves. On small-world graphs the strongest existing method is PSL with its compression extension, which for SK-2005 reportedly cut index size by over 50% (Scaling Distance Labeling on Small-World Networks).

All methods run on the same machine, on the same graph files, with the same thread count and a 24-hour time limit, matching PSL's protocol. Each method's own published defaults are used, with no extra tuning given to ours. Total index size, construction time and mean query latency are measured over the same one million random query pairs. A separate set of query pairs is drawn with at least one endpoint among the priority nodes.

The key ablation varies the prefix length $k$ from zero (pure topology order, which equals the baseline) up to the full graph (pure priority order). This isolates the cost of the guarantee. A second ablation swaps the suffix rule between degree order and cut order on both topology families. This tests whether topology-aware suffixes are what keep the inflation small.

The proposal beats the baselines if three things hold for the random and clustered priority models. First, the prefix labeler guarantees $s(j) \le j$ for $j \le k$ at a $k$ of at least $10^4$. Second, total index size stays within a modest factor of the best topology-specific method; we pre-register 1.5x. Third, query latency for priority-endpoint queries is no worse than the baseline's. Separately, the profile result counts as informative if the fitted $\alpha$ differs between small-world and road graphs by more than its bootstrap confidence interval.

Why not just…?

Why not just use degree-ordered PLL and report what priority nodes get? When priority equals degree, this probably is enough, and we expect to confirm that. The proposal only matters when priority disagrees with structure. PSL's finding that low-degree peripheral nodes carry the largest labels (Scaling Distance Labeling on Small-World Networks) suggests that randomly or regionally chosen important nodes will get large labels under degree order. The $k=0$ arm of the prefix ablation measures this directly. If priority nodes' labels under degree order already fall below $j$ in the random model, we will report that the guarantee is unnecessary in practice. That would itself be a negative result about the practical value of the theory.

Why not just store each node's distances to all higher-priority nodes? This trivial table is the theory's own $O(j)$ scheme and is correct. But it has no pruning, so it says nothing about how real topology lowers label growth, and its total size grows with $k$ times the number of nodes. It is included as the upper reference. If its size turns out comparable to the pruned prefix labeler on road graphs, that is evidence that the planar lower bound is nearly tight in practice, which is a finding we would report.

Why not just use HC2L or CTL on roads and PSL on social graphs, and add a lookup table for priority nodes? This is the real threat. A topology-specific index plus a $k$-column landmark table could match our guarantee for $j \le k$. We would run this hybrid as an explicit baseline. Our prediction is that it pays roughly $k$ extra entries per node. The pruned prefix pays less, because early priority searches also prune later ones. If the hybrid matches our total size, we would recommend it and present our contribution as the profile measurement. Customization Meets 2-Hop Labeling: Efficient Routing in Road Networks (CTL), which builds tree-hierarchy labels whose size is tuned by a threshold $\theta$ for road networks with changing edge weights, controls size globally rather than per node, so it does not supply this guarantee on its own.

Proposed Experiments

The small-world corpus is Indochina, LiveJournal, Pokec, Youtube, Skitter, DBLP and SK-2005, drawn from the PLL and PSL evaluations. The road corpus is the DIMACS networks NY, BAY, COL, FLA, CAL and the full USA graph, plus Western Europe, as used by HC2L and CTL. Synthetic trees and grid graphs serve as calibration cases where theory predicts the answer: near-logarithmic growth for trees and near-linear worst-case behavior for planar-like grids.

First check: calibration. On trees, the fitted $\alpha$ from priority-first pruned labeling must approach 0. If it does not, our measurement or implementation is flawed, and every other result is suspect.

Second check: profiles across topologies. We fit $\alpha$ with bootstrap intervals for each graph and priority model, using the trivial table as the $\alpha = 1$ reference. This test can fail. A finding that real road and web graphs both sit near $\alpha \approx 1$ under random priority would mean the worst-case bounds describe practice, and that would also be a result worth publishing.

Third check: cost of the guarantee. We plot total index size and construction time against $k$ for each suffix rule. We compare these curves with degree-ordered PLL and PSL on small-world graphs, with HC2L on roads, and with the landmark-table hybrid on both.

Fourth check: approximation on roads. For $\epsilon$ in {0.01, 0.05, 0.1}, we test whether approximate pruning lowers road-network $\alpha$ substantially relative to exact labeling while keeping the measured stretch over the query set within $(1+\epsilon)$. A large drop would be empirical evidence that approximation escapes the exact planar $\Omega(j)$ barrier. That would motivate the open theoretical question of approximate prioritized labeling for planar graphs.

We will release all code and per-node label profiles. No implementation of a prioritized distance scheme currently exists, so this release fills the measurement gap that the theory papers explicitly leave open.