PaperlayerView exact revision on arXiv

Source-linked AI summary

Asynchronous Parallel Search for Exact Multi-Objective Shortest Paths with Versioned Frontier Snapshots and Indexed Dominance Pruning

Xiaoqing Xu, Ning Zhang, Liuyihui Qian, Xiaojun Liu, Juan Wu, Hong Tang

arXiv:2609.11944v1cs.DC

TL;DR

Exact MOSP must preserve complete Pareto frontiers despite rapidly growing labels and dominance costs, making efficient parallelization difficult. SIP-MOSP uses one asynchronous cooperative search with immutable versioned snapshots and exact indexed pruning. Across diverse graph topologies, it improves over sequential and parallel exact baselines, with especially large high-dimensional time and memory gains.

  • Problem

    Exact MOSP must preserve complete Pareto sets while managing rapidly growing nondominated labels and costly per-vertex dominance operations, making efficient parallelization an open challenge.

  • Method

    SIP-MOSP separates label expansion from frontier maintenance in one asynchronous cooperative search using immutable versioned snapshots and exact block-minimum or segment-tree-minimum pruning.

  • Results

    SIP-MOSP improves on sequential and parallel exact baselines across road, ISP, and dense graph settings, with particularly large time and memory gains at high objective counts.

  • Takeaways & Limitations

    SIP-MOSP provides a practical shared-memory framework for scaling one exact cooperative MOSP search across structurally diverse graph topologies without replicating complete search state.

Abstract

from arXiv · show

Exact multi-objective shortest-path (MOSP) search computes the complete Pareto set between specified start and goal vertices, and its computational cost can grow rapidly with expanding nondominated label sets and frequent dominance tests over per-vertex Pareto frontiers. Efficiently parallelizing exact MOSP remains an open challenge. This paper presents SIP-MOSP (Snapshot-based Indexed-Pruning MOSP), an asynchronous exact framework that separates label expansion from frontier maintenance within a single cooperative search. SIP-MOSP combines immutable versioned frontier snapshots with indexed dominance pruning, enabling concurrent label processing without concurrent access to the same mutable frontier. Together, these mechanisms reduce synchronization overhead and accelerate dominance testing. We instantiate the framework with block-minimum (SIP-MOSP-BM) and segment-tree-minimum (SIP-MOSP-ST) indices and prove exactness. We evaluate both variants against four state-of-the-art exact MOSP baselines covering sequential and parallel search. Experiments across multiple objective dimensions on a road network, an Internet service provider topology, and an 180-vertex complete directed graph show that SIP-MOSP achieves speedups of up to 46.9* over the best-performing sequential baseline and up to 7.05* over the best-performing parallel baseline on mutually solved instances. In the 20-objective complete-graph setting, where many instances remain unsolved by the sequential baselines within one hour, SIP-MOSP-ST achieves a 3.34* speedup while reducing peak memory by a factor of 60.3 relative to the best-performing parallel baseline. These results demonstrate that SIP-MOSP is an efficient shared-memory framework for exact MOSP across structurally diverse graph topologies.

I. INTRODUCTION

Exact MOSP must preserve complete Pareto frontiers, making frontier growth and dominance checking difficult; SIP-MOSP addresses parallelization by separating asynchronous expansion from exclusive frontier maintenance and indexed snapshot pruning.

  • Motivation: Exact MOSP preserves every nondominated trade-off, but Pareto sets and per-vertex frontier operations can grow rapidly with objectives and graph size.Dominance queries, surviving-label insertion, and deletion of dominated labels become major computational costs during search.
  • Motivation: Parallel exact MOSP must reconcile globally ordered best-first processing with concurrent access to evolving Pareto frontiers.Existing approaches expose concurrency through Pareto batches, replicated order-specific searches, synchronized shared state, or specialized ordered execution.
  • SIP-MOSP: Block-minimum and segment-tree-minimum indexes accelerate exact dominance pruning by discarding impossible ranges while retaining exact verification of survivors.The indexes alter pruning work rather than dominance semantics.
  • SIP-MOSP: SIP-MOSP separates candidate expansion from frontier admission within one cooperative asynchronous search, assigning each vertex frontier to one update worker.Worker-specific queues and direct endpoint-owner delivery avoid centralized redistribution while enabling different vertex frontiers to be updated in parallel.
  • SIP-MOSP: Immutable versioned base–delta snapshots expose recent frontier information without rebuilding a large index after every insertion.Search workers read snapshots rather than mutable frontiers, while version checks support safe reuse of negative pruning results.
  • Evaluation: The framework proves exactness and evaluates four exact baselines across three topology families using solve time, memory, ablations, scaling, and processor utilization.The paper positions the evaluation as covering both sequential and parallel exact MOSP search.

B. Parallel MOSP

Prior parallel MOSP methods expose concurrency through batches, replicated searches, shared state, or specialized execution, while SIP-MOSP targets one cooperative exact search with exclusive frontier updates and immutable reads.

  • Existing parallel methods: Parallel label-setting methods process subsets of globally Pareto-optimal labels, but their efficient queue analysis is strongest for two objectives.For d ≥3, an efficient general Pareto queue is not known.
  • Existing parallel methods: Parallel MOA* runs separate complete searches for selected objective orders, gaining complementary exploration but replicating open lists and node-frontier state.Its natural concurrency follows the number of selected orders.
  • Existing parallel methods: SOPMOA* uses shared OPEN and per-vertex Pareto fronts protected by locks, so synchronization remains on repeatedly accessed queue and frontier operations.SIP-MOSP instead uses worker-local priority queues and exclusive frontier ownership.
  • Existing parallel methods: OPMOS and MPMOS pursue specialized ordered execution, including a GPU-based massively parallel architecture.These designs retain ordering disciplines while processing eligible path extensions concurrently.
  • Problem scope: DynaMOSP returns a user-preference-guided Pareto-optimal or suboptimal route rather than enumerating the complete cost-unique Pareto frontier.It therefore addresses incremental recomputation in a different problem setting from exact complete-frontier search.
  • Relation to prior work: DAMPC separated expansion and path-set updates but lacked centralized-dispatch removal, versioned indexed snapshots, base–delta publication, and version-based validation reuse.SIP-MOSP retains the separation while redesigning communication and frontier management.

B. Labels and Consistent Lower Bounds

SIP-MOSP labels represent concrete paths with accumulated and lower-bound costs, while consistent vector heuristics support safe pruning and versioned snapshots provide read-only frontier state.

  • Labels: Each label represents a concrete s–v(x) path and stores its endpoint, accumulated cost, lower-bound score, parent reference, and observed snapshot versions.The parent reference supports path reconstruction, and the version fields identify endpoint and goal snapshots seen during generation.
  • Consistent lower bounds: Per-objective reverse-graph Dijkstra computations produce exact single-objective distances that form an admissible, consistent vector lower bound.Nonnegative edge costs support consistency.
  • Consistent lower bounds: A label is safely pruned when an existing goal vector weakly dominates its lower-bound score, because every completion is then dominated.Weak dominance requires no larger cost in every objective.
  • Search ordering: Different search workers may use cyclic objective orders and local lexicographic queues; exactness does not require a globally unique minimum because admission remains exact.The ordering is a local scheduling policy rather than a replicated complete search.
  • Canonical frontiers: Each vertex has a canonical mutable frontier modified by exactly one update worker, with the goal frontier assigned to a dedicated goal-update worker.This ownership distinguishes exact maintained state from read-only pruning copies.
  • Published snapshots: Search workers query published snapshots containing a consolidated immutable lexicographic base, a recent immutable delta, and an index over the base.The delta represents recent additions rather than vector subtraction, and snapshots may conservatively retain older dominated vectors.
  • Published snapshots: Because every current canonical vector appears in the snapshot, a positive snapshot dominance result is safe even when older dominated vectors remain.This conservative-superset property supports sound pruning.

IV. THE SIP-MOSP FRAMEWORK

SIP-MOSP combines owner-directed asynchronous queues and private best-first processing with immutable base–delta snapshots whose indexed queries prune impossible dominance ranges before exact verification.

  • Asynchronous architecture: Search workers expand labels using read-only snapshots, while endpoint owners receive candidates through incoming queues and alone maintain their assigned frontiers.A dedicated goal-update worker handles candidates ending at the goal.
  • Asynchronous architecture: Direct owner delivery removes centralized redistribution, and power-of-two-choices routing balances accepted labels without scanning all search workers.The load-balancing policy also preserves some endpoint locality.
  • Versioned base–delta snapshots: Base–delta publication makes newly accepted vectors visible immediately while amortizing base copying and index construction across multiple accepted vectors.Retaining vectors later dominated by newer additions is safe for snapshot pruning.
  • Indexed dominance pruning: The delta is queried first and can be skipped when its component-wise minimum exceeds the candidate in any dimension; otherwise it is scanned exactly.Recent vectors are checked early because they often invalidate queued or newly generated labels.
  • Indexed dominance pruning: Binary search restricts the lexicographically ordered base to the prefix that can contain a dominator, after which range minima discard impossible intervals.A lexicographically larger base vector exceeds the candidate in its first differing dimension.
  • Indexed dominance pruning: Both indexes use component minima only as necessary-condition filters, so every surviving vector still receives an exact dominance test.Component minima may come from different vectors and therefore cannot establish dominance by themselves.
  • Index variants: SIP-MOSP-BM summarizes fixed-size contiguous blocks, whereas SIP-MOSP-ST stores the same minima in segment-tree intervals for range pruning.Block size trades finer pruning against more summaries; the segment tree recursively prunes represented intervals.
  • Index variants: In the three-dimensional example, lexicographic filtering leaves six possible base vectors, and either index reduces six exact comparisons to two.The figure shows the recent delta, ordered base, and index together.

D. Version Reuse

SIP-MOSP uses asynchronous search and update workers, with versioned immutable snapshots allowing negative dominance results to be safely reused or rechecked when frontiers change.

  • D. Version Reuse: Version equality certifies that a search worker and update worker refer to the same immutable snapshot, so a duplicate dominance query can be skipped.A version mismatch instead triggers an exact query against the current snapshot.
  • D. Version Reuse: Initialization computes reverse single-objective distances for each objective, assigns non-goal vertices to update workers, publishes empty snapshots, and launches concurrent worker loops.The search starts by submitting the initial label and terminates after all queues become empty and workers are idle.
  • D. Version Reuse: Search workers expand labels using private best-first queues, prune candidates against endpoint and goal snapshots, and forward survivors to endpoint-specific update workers.This separates expansion from frontier maintenance while avoiding direct reads of mutable frontiers.
  • D. Version Reuse: Update workers validate candidates, update canonical frontiers, publish new base–delta snapshots, and return accepted non-goal labels to lightly loaded search workers.The dedicated goal-update worker applies the same procedure to the goal frontier.
  • D. Version Reuse: Snapshot queries test the recent delta, restrict the ordered base to a feasible lexicographic prefix, and use exact scanning or range-minimum indexes.Consolidation thresholds affect snapshot rebuilding but not the dominance predicate.

F. Termination

SIP-MOSP terminates through stable global quiescence rather than per-transfer global counting, requiring all workers and queues to remain inactive across repeated observations.

  • F. Termination: Termination is declared only when every worker is idle, every private priority queue is empty, and every incoming queue has no published or in-progress item.A worker is idle only when it has no current label and both queue conditions hold.
  • F. Termination: The coordinator confirms that worker states and queue cursors remain unchanged across repeated observations before issuing the stop signal.This checks stable quiescence rather than relying on a global counter for every label transfer.
  • F. Termination: Because the system is closed after submitting the start label, stable empty queues and idle workers cannot generate future labels.The protocol implements the abstract termination condition without affecting search ordering or dominance decisions.

V. CORRECTNESS AND COMPLEXITY

The correctness argument shows that versioned snapshot queries and exact frontier updates preserve canonical-frontier invariants, safe pruning, and complete Pareto-optimal goal results.

  • V. CORRECTNESS AND COMPLEXITY: If a candidate is admitted, the canonical frontier contains exactly the cost-unique nondominated vectors among labels admitted for that vertex.The invariant follows because dominated stored vectors are removed, the candidate is inserted once, and incomparable vectors remain.
  • V. CORRECTNESS AND COMPLEXITY: Indexed snapshot queries are exact because delta vectors are checked directly, lexicographically infeasible prefixes are excluded, and minima discard only ranges that cannot contain dominators.Surviving vectors are tested exactly, so neither dominators nor non-dominators are misclassified.
  • V. CORRECTNESS AND COMPLEXITY: A negative dominance result may be reused only when its observed snapshot version remains current; otherwise, the update worker repeats the query against the latest snapshot.Version equality identifies the same immutable snapshot, while snapshot containment makes positive results safe even after frontier changes.
  • V. CORRECTNESS AND COMPLEXITY: Admissible goal bounds make goal pruning safe because any goal cost dominating a label’s bound would also weakly dominate the corresponding Pareto-optimal completion.This either contradicts Pareto optimality or identifies an already represented equivalent goal cost.
  • V. CORRECTNESS AND COMPLEXITY: SIP-MOSP is exact: without timeout, its goal frontier contains exactly one representative path for every Pareto-optimal start–goal cost vector.Fair processing preserves every Pareto-optimal path, and stable quiescence ensures no queued, active, or in-flight candidate remains.

A. Complexity

Dominance-query cost depends on delta size, lexicographic prefix length, objective count, and the selected block-minimum or segment-tree index, while consolidation amortizes index construction.

  • A. Complexity: The delta test costs O(dδ) in the worst case, lexicographic binary search costs O(d log n), and an unindexed base query costs O(du).Here n is the base size, δ is the delta size, u is the feasible prefix length, and d is the objective count.
  • A. Complexity: SIP-MOSP-BM tests ⌈u/b⌉ block summaries and exactly scans surviving blocks, costing O((d −1)⌈u/b⌉+ ds) when s vectors survive.The block size is b.
  • A. Complexity: SIP-MOSP-ST visits only segment-tree nodes intersecting the feasible prefix and not eliminated by interval minima.Both indexed variants discard only impossible ranges before exact checks.
  • A. Complexity: Consolidation copies and sorts the canonical frontier and builds an O(dn) index, while base–delta publication shares the immutable base between consolidations.Endpoint ownership serializes updates per vertex but allows independent vertices to update in parallel.
  • A. Complexity: The search remains output sensitive because exact MOSP may require work proportional to a potentially exponential Pareto frontier.The base–delta policy avoids rebuilding the index after every insertion.

A. Experimental Setup

The evaluation compares SIP-MOSP with four exact baselines across road, ISP, and complete-graph topologies, measuring solve time and peak memory on mutually solved instances. Results show consistent runtime advantages, with larger speedups and memory savings in higher-dimensional workloads.

  • Experimental Setup: The study uses a 56-core, 112-thread server, a one-hour timeout, and peak resident set size as its memory measure.Means and speedups are computed over mutually solved instances, while the evaluated topologies are NYC-Road, AS3356, and Dense-180.
  • Main Results: Higher-dimensional AS3356 and Dense-180 workloads show both solve-time improvements and substantial memory savings, unlike the low-dimensional road settings where baselines use less memory.The evaluation also isolates mechanism contributions and examines scaling and processor utilization.
  • Main Results: Both SIP-MOSP variants outperform LTMOA* and NWMOA* on mutually solved instances wherever sequential comparisons are available.NWMOA* is used as the conservative sequential reference because it has the lower mean solve time among the two sequential baselines.
  • Main Results: 4.78 s is SIP-MOSP-BM's three-objective NYC-Road mean solve time, compared with 9.88 s for NWMOA* and 6.33 s for Parallel NWMOA*.With four objectives, SIP-MOSP-BM requires 19.57 s, compared with 40.58 s for NWMOA* and 20.29 s for Parallel NWMOA*.
  • Main Results: 46.9× is SIP-MOSP-ST's speedup over NWMOA* on AS3356 with 20 objectives, while Dense-180 reaches 7.05× over Parallel LTMOA* with 10 objectives.The Dense-180 20-objective comparison gives SIP-MOSP-ST a 3.34× speedup over Parallel NWMOA*.
  • Main Results: 60.3× lower peak memory is achieved by SIP-MOSP-ST than Parallel NWMOA* on Dense-180 with 20 objectives.SIP-MOSP-ST uses 2.705 GB versus 163.244 GB for Parallel NWMOA*; sequential methods are excluded because most instances exceed the one-hour limit.

C. Component Ablations

The ablations show that base–delta snapshots and indexed pruning are the strongest contributors to SIP-MOSP performance, while version reuse provides smaller gains and communication effects depend on topology.

  • Base–delta publication: 2.95–16.87× slower eager reconstruction shows that base–delta publication is the most consistent performance contributor across high-dimensional AS3356 and Dense-180 settings.The penalty is larger for SIP-MOSP-ST because each accepted label rebuilds the complete interval hierarchy; eager reconstruction also substantially increases memory.
  • Indexed pruning: 1.22–3.07× slowdowns after removing block minima or segment trees show that indexed pruning is important, especially for large frontiers.The segment tree has the larger measured runtime effect, while no-index variants can sometimes use less memory.
  • Version reuse: 1–7% block-backend and 0.5–10% segment-tree-backend slowdowns show that version reuse has a smaller but measurable effect.Its benefit decreases when queue delays or higher update rates make snapshot-version changes more likely.
  • Communication and ordering: Centralized dispatch nearly doubles runtime and sharply increases memory on NYC-Road but is close to neutral on AS3356 and Dense-180.The topology dependence suggests queue contention or delayed pruning-information publication makes centralized communication harmful in some settings.
  • Communication and ordering: Objective-order diversity matters most on NYC-Road and also slows SIP-MOSP-BM by 1.24× on AS3356 and 1.16× on Dense-180.The ablation therefore indicates that objective-order effects vary with topology and backend.

D. Thread Scaling

Thread-scaling experiments show that both SIP-MOSP variants benefit substantially from more workers, while a cooperative search sustains utilization better than independent objective-order searches on a difficult dense workload.

  • D. Thread Scaling: 4.90× and 4.84× speedups result when total workers increase from 16 to 96 for SIP-MOSP-BM and SIP-MOSP-ST, respectively.Solve times fall from 7.363 to 1.501 s for BM and from 7.680 to 1.587 s for ST over the 40-query Dense-180, ten-objective study.
  • D. Thread Scaling: Memory rises approximately 2.06× for BM and 2.08× for ST as workers increase sixfold, rather than scaling proportionally with worker count.Gains become smaller beyond 64 workers because of scheduling, communication, frontier-update overheads, and changing update-worker partitions.
  • D. Thread Scaling: Both SIP-MOSP variants improve monotonically with additional workers, demonstrating substantial scaling on the representative Dense-180 ten-objective workload.The study varies search and update workers proportionally from 8/8 through 48/48, for 16–96 total workers, and changes the vertex partition simultaneously.
  • D. Thread Scaling: SIP-MOSP sustains approximately 8 busy cores throughout a difficult Dense-180 twenty-objective run, whereas parallel LTMOA* and NWMOA* lose utilization as independent searches finish.The trace compares one cooperative search with one search per objective order; aggregate runtime and memory evidence comes from the multi-query tables.
  • F. Cross-Paper Comparison with OPMOS and MPMOS: 38.9× lower geometric-mean time than OPMOS is reported for the matched 72-thread comparison, while 96-worker SIP-MOSP-BM reaches 1.006 s versus 0.968 s for GPU-based MPMOS.The cross-paper systems were evaluated separately, so this comparison complements rather than replaces controlled comparisons.

G. Discussion

SIP-MOSP’s cooperative architecture combines exclusive frontier ownership, immutable base–delta snapshots, indexed pruning, and asynchronous delivery to scale exact MOSP without replicating complete searches. Discussion results show topology- and workload-dependent trade-offs, with especially strong time and memory benefits at high objective counts.

  • Exclusive vertex ownership and immutable snapshots enable simultaneous updates to different frontiers while allowing lock-free search-side dominance pruning.Direct owner delivery also avoids centralized dispatcher overhead and shortens the delay before newly useful pruning information is published.
  • Base–delta snapshots balance freshness and construction cost by exposing recent vectors immediately without rebuilding an indexed snapshot after every acceptance.This preserves the feedback loop in which newly accepted vectors quickly prune other labels.
  • Block minima favor lower-summary sequential access on NYC-Road and ten-objective Dense-180, whereas segment trees are fastest on AS3356 and twenty-objective Dense-180.Removing either index increases runtime, showing that the benefit is not merely low-level tuning.
  • 60.3× lower memory on Dense-180 and 10.9× lower memory on AS3356 follow from sharing one cooperative search state instead of replicating complete objective-order searches.The memory advantage is strongest when high-dimensional Pareto state, rather than path depth alone, dominates storage.
  • Scheduling effects are topology dependent: direct owner delivery matters on NYC-Road, order diversity helps when one lexicographic order explores an unfavorable region, and version reuse depends on update timing.The reported one-order slowdown is 1.24× on AS3356, while version reuse depends on queue delay, update frequency, and dominance-query cost.
  • SIP-MOSP retains exact frontier admission while exploiting shared-memory parallelism without replicating complete searches or relying on ordered accelerator-style execution.This positions cooperative vertex-local updates as a complementary parallel model to objective-order portfolios.
  • The implementation assumes nonnegative additive edge costs for reverse Dijkstra lower bounds, while ownership and snapshot design are independent of that choice.Future directions include NUMA-aware ownership, adaptive indexing, vectorized scans, and heterogeneous snapshot queries.
  • SIP-MOSP improves on sequential and parallel exact baselines across road, ISP, and dense graph settings, with particularly large gains at high objective counts.Ablations identify base–delta publication and indexed pruning as the most consistent contributors, while direct delivery, order diversity, and version reuse depend on workload structure.
Loading 2609.11944v1…