pith. sign in

arxiv: 2506.16488 · v3 · submitted 2025-06-19 · 💻 cs.DC · cs.DS

Parallel Point-to-Point Shortest Paths and Batch Queries

Xiaojun Dong , Andy Li , Yan Gu , Yihan Sun This is my paper

Pith reviewed 2026-05-19 08:23 UTC · model grok-4.3

classification 💻 cs.DC cs.DS
keywords parallel shortest pathspoint-to-point queriesbidirectional searchA star searchbatch queriesgraph algorithmsparallel computing
0
0 comments X

The pith

Orionet speeds up parallel point-to-point shortest path queries by layering bidirectional search and pruning onto existing single-source frameworks.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops Orionet as a way to turn parallel single-source shortest path code into efficient point-to-point solvers by adding pruning conditions and early-termination rules. It shows how the same idea supports bidirectional search, A* search, and bidirectional A* with only modest extra logic. The work then models batches of queries as a small query graph so that multiple source-target pairs can share distance information during execution. A reader would care because point-to-point distance queries appear in navigation, network analysis, and logistics, and parallel speed matters once graphs grow beyond what fits comfortably on one core.

Core claim

By grafting pruning conditions and early-termination rules from bidirectional search and A* onto parallel SSSP frameworks, Orionet produces simple, fast parallel algorithms for single and batched point-to-point shortest paths; on 14 graphs the bidirectional variant runs 2.9 times faster than GraphIt and 6.8 times faster than MBQ on average, while bidirectional A* improves by 4.4 times and 6.2 times over the same baselines.

What carries the argument

Pruning conditions and early-termination rules taken from bidirectional and A* search, applied inside existing parallel SSSP frameworks, together with a query-graph abstraction that represents batches of source-target pairs as edges.

If this is right

  • Bidirectional search yields average speedups of 2.9 times versus GraphIt and 6.8 times versus MBQ across the tested graphs.
  • Bidirectional A* yields average speedups of 4.4 times versus GraphIt’s A* and 6.2 times versus MBQ’s A*.
  • Batch queries can reuse distance information across pairs once they are represented as a query graph.
  • The resulting code stays simple because it reuses existing parallel SSSP primitives rather than building new data structures from scratch.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same pruning-layer idea could be tried on other heuristic graph searches that already have parallel single-source implementations.
  • On distributed-memory machines the reduction in explored vertices might translate into lower communication volume.
  • Dynamic or time-dependent graphs could be tested by updating the query graph on the fly without restarting the entire search.

Load-bearing premise

The pruning rules and early stops derived from bidirectional and A* search stay effective and do not create enough extra synchronization cost to erase their benefit on parallel hardware.

What would settle it

A set of graphs where bidirectional search or bidirectional A* in Orionet finishes slower than the unidirectional baselines on the same parallel SSSP framework.

Figures

Figures reproduced from arXiv: 2506.16488 by Andy Li, Xiaojun Dong, Yan Gu, Yihan Sun.

Figure 1
Figure 1. Figure 1: Illustration for PPSP algorithms with early termination, bidirectional search, A [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Illustration for the proof of Thm. 3.3 for our BiDS algo￾rithm. facilitates our BiD-A∗ in Sec. 3.5 and our batch PPSP algorithms in Sec. 4. Surprisingly, we did not find existing work that employs such a simple heuristic for BiDS. We attribute such a gap to the inherent difference between sequential and parallel SSSP—sequentially, since only one vertex is processed at a time, it is natural (and easy) to fi… view at source ↗
Figure 3
Figure 3. Figure 3: Illustration for the query graph construction. [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Running time vs. distance percentile for single PPSP algorithms on four representative graphs from each category. [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Self-relative speedups of our single PPSP algorithms on four representative graphs from each category. [PITH_FULL_IMAGE:figures/full_fig_p012_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Relative performance over ET with and without memoiza [PITH_FULL_IMAGE:figures/full_fig_p012_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Heatmap on batch PPSP queries. The numbers are the running times normalized to the fastest algorithm on each test instance. Smaller or green is better. “GEOMEAN” = geometric means on all graphs. We run two BiDS-based algorithms and two SSSP-based algorithms as introduced in Sec. 4. For BiDS-based algorithms, Multi is to evaluate all queries in a batch, Plain is to runs each query with our parallel BiDS alg… view at source ↗
Figure 8
Figure 8. Figure 8: Heatmap on large batch PPSP queries. The numbers are the running times normalized to the fastest algorithm on each test instance. Smaller or green is better. “GEOMEAN” = geometric means on all graphs. We run two BiDS-based algorithms and two SSSP-based algorithms as introduced in Sec. 4. For BiDS-based algorithms, Multi is to evaluate all queries in a batch, Plain is to runs each query with our parallel Bi… view at source ↗
Figure 9
Figure 9. Figure 9: Running time vs. distance percentile for single PPSP algorithms on each graph. [PITH_FULL_IMAGE:figures/full_fig_p017_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Self-relative speedups of our single PPSP algorithms on each graph. [PITH_FULL_IMAGE:figures/full_fig_p018_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Relative performance over ET with and without memoization on each graph. [PITH_FULL_IMAGE:figures/full_fig_p018_11.png] view at source ↗
read the original abstract

We propose Orionet, efficient parallel implementations of Point-to-Point Shortest Paths (PPSP) queries using bidirectional search (BiDS) and other heuristics, with an additional focus on batch PPSP queries. We present a framework for parallel PPSP built on existing single-source shortest paths (SSSP) frameworks by incorporating pruning conditions. As a result, we develop efficient parallel PPSP algorithms based on early termination, bidirectional search, A$^*$ search, and bidirectional A$^*$ all with simple and efficient implementations. We extend our idea to batch PPSP queries, which are widely used in real-world scenarios. We first design a simple and flexible abstraction to represent the batch so PPSP can leverage the shared information of the batch. Orionet formalizes the batch as a query graph represented by edges between queried sources and targets. In this way, we directly extended our PPSP framework to batched queries in a simple and efficient way. We evaluate Orionet on both single and batch PPSP queries using various graph types and distance percentiles of queried pairs, and compare it against two baselines, GraphIt and MBQ. Both of them support parallel single PPSP and A$^*$ using unidirectional search. On 14 graphs we tested, on average, our bidirectional search is 2.9$\times$ faster than GraphIt, and 6.8$\times$ faster than MBQ. Our bidirectional A$^*$ is 4.4$\times$ and 6.2$\times$ faster than the A$^*$ in GraphIt and MBQ, respectively. For batched PPSP queries, we also provide in-depth experimental evaluation, and show that Orionet provides strong performance compared to the plain solutions.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The manuscript proposes Orionet, a framework for parallel point-to-point shortest path (PPSP) queries that extends existing single-source shortest paths (SSSP) implementations with pruning conditions to support bidirectional search (BiDS), A* search, and bidirectional A*. It further introduces a query-graph abstraction to handle batch PPSP queries by representing shared source-target information as edges. Experiments on 14 graphs across distance percentiles report average speedups of 2.9× (bidirectional) and 4.4× (bidirectional A*) versus GraphIt, and 6.8× / 6.2× versus MBQ.

Significance. If the performance claims hold after addressing synchronization details, the work would supply a practical, low-effort method for adding bidirectional and heuristic pruning to parallel SSSP frameworks, which is useful for route-planning and network-analysis workloads. The query-graph abstraction for batches is a clean and extensible idea. Credit is given for the multi-graph, multi-percentile evaluation and direct comparison to two established baselines.

major comments (3)
  1. [§4] §4 (Pruning and early-termination rules): the bidirectional and A* pruning conditions are stated to be “simple and efficient,” yet the text provides no description or measurement of the synchronization primitives (global barriers, atomic distance checks, or lock-free meeting-point detection) required to realize early termination in a parallel relaxation loop. This is load-bearing for the central speedup claim.
  2. [Experimental evaluation] Experimental section (speedup tables): reported averages of 2.9× and 6.8× are given without error bars, standard deviations, or statistical significance tests across the 14 graphs. Without these, it is impossible to determine whether the observed factors are robust or sensitive to particular graph topologies or distance percentiles.
  3. [§5.2] §5.2 (Batch-query extension): the query-graph abstraction is presented as a direct, low-overhead extension of the single-query framework, but no separate timing breakdown isolates the cost of maintaining or traversing the query graph versus the underlying bidirectional search; this leaves unclear how much of the reported batch performance is attributable to the new abstraction.
minor comments (2)
  1. [Abstract and §1] The abstract and §1 use “Orionet” both for the overall framework and for the specific bidirectional implementation; a clearer nomenclature would help readers distinguish the general approach from its concrete realizations.
  2. [Figures] Figure captions for the speedup plots should explicitly state the number of runs per data point and whether the plotted values are means or medians.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We are grateful to the referee for the positive evaluation of Orionet's contributions, particularly the query-graph abstraction for batch queries and the comprehensive experimental comparison. We address each of the major comments below, proposing specific revisions to strengthen the manuscript.

read point-by-point responses

  1. Referee: [§4] §4 (Pruning and early-termination rules): the bidirectional and A* pruning conditions are stated to be “simple and efficient,” yet the text provides no description or measurement of the synchronization primitives (global barriers, atomic distance checks, or lock-free meeting-point detection) required to realize early termination in a parallel relaxation loop. This is load-bearing for the central speedup claim.

    Authors: We thank the referee for pointing out this important detail. The pruning conditions build upon standard bidirectional and A* techniques, but we agree that the parallel synchronization mechanisms for early termination were not sufficiently described. In the revised manuscript, we will add a detailed explanation in §4 of the atomic operations for distance updates and the use of a global barrier for detecting termination across threads. Additionally, we will include measurements of the synchronization overhead to substantiate the efficiency of these primitives. revision: yes

  2. Referee: [Experimental evaluation] Experimental section (speedup tables): reported averages of 2.9× and 6.8× are given without error bars, standard deviations, or statistical significance tests across the 14 graphs. Without these, it is impossible to determine whether the observed factors are robust or sensitive to particular graph topologies or distance percentiles.

    Authors: We agree that providing measures of variability would improve the robustness assessment of our results. The reported averages aggregate performance across 14 diverse graphs and various distance percentiles. In the revision, we will augment the speedup tables with error bars indicating standard deviation and discuss the consistency of speedups across different graph topologies and query distances. Although we did not conduct formal statistical significance tests, the improvements were observed uniformly without significant variance. revision: partial

  3. Referee: [§5.2] §5.2 (Batch-query extension): the query-graph abstraction is presented as a direct, low-overhead extension of the single-query framework, but no separate timing breakdown isolates the cost of maintaining or traversing the query graph versus the underlying bidirectional search; this leaves unclear how much of the reported batch performance is attributable to the new abstraction.

    Authors: We appreciate the suggestion to clarify the overhead of the query-graph abstraction. This abstraction allows leveraging shared information in batches with minimal additional cost. In the revised §5.2, we will provide a separate timing breakdown that isolates the costs of query-graph construction, edge traversals, and the core bidirectional search, showing that the abstraction overhead is small relative to the overall performance benefits. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's core contribution is an algorithmic framework (Orionet) that extends existing parallel SSSP implementations with pruning/early-termination rules derived from bidirectional and A* search, plus a query-graph abstraction for batch queries. All performance claims (2.9×–6.8× speedups) are obtained from direct empirical timing on 14 external graphs against independent baselines (GraphIt, MBQ), not from any fitted parameters, self-referential equations, or load-bearing self-citations. No derivation step reduces a claimed result to its own inputs by construction; the pruning rules are presented as straightforward additions whose correctness and overhead are evaluated experimentally rather than assumed via prior author work.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claims rest on standard parallel graph algorithms and the assumption that bidirectional pruning works efficiently; no new physical constants or fitted parameters are introduced.

axioms (1)
  • domain assumption Existing parallel SSSP frameworks can be extended with pruning conditions without changing their asymptotic complexity or introducing prohibitive synchronization cost.
    Invoked when the paper states it builds PPSP on top of SSSP frameworks by incorporating pruning conditions.
invented entities (1)
  • Query graph no independent evidence
    purpose: Represent batch PPSP queries as edges between sources and targets to share information across queries.
    New abstraction introduced to extend the PPSP framework to batches in a simple way.

pith-pipeline@v0.9.0 · 5849 in / 1350 out tokens · 36431 ms · 2026-05-19T08:23:42.061103+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

77 extracted references · 77 canonical work pages · 2 internal anchors

  1. [1]

    GraphHopper

    2024. GraphHopper. https://www.graphhopper.com/

    work page 2024

  2. [2]

    Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. 2013. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. InACM SIGMOD International Conference on Management of Data (SIGMOD) . 349–360

    work page 2013

  3. [3]

    Lars Backstrom, Dan Huttenlocher, Jon Kleinberg, and Xiangyang Lan. 2006. Group formation in large social networks: membership, growth, and evolution. In ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD). 44–54

    work page 2006

  4. [4]

    Michael Barley, Patricia Riddle, Carlos Linares López, Sean Dobson, and Ira Pohl. 2018. GBFHS: A generalized breadth-first heuristic search algorithm. In Proceedings of the International Symposium on Combinatorial Search, Vol. 9. 28–36

    work page 2018

  5. [5]

    Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Mü ller Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F Werneck. 2016. Route planning in transportation networks. Algorithm engineering: Selected results and surveys (2016), 19–80

    work page 2016

  6. [6]

    Holger Bast, Stefan Funke, Peter Sanders, and Dominik Schultes. 2007. Fast routing in road networks with transit nodes. Science 316, 5824 (2007), 566–566

    work page 2007

  7. [7]

    Scott Beamer, Krste Asanović, and David Patterson. 2012. Direction-optimizing breadth-first search. In International Conference for High Performance Computing, Networking, Storage, and Analysis (SC) . 1–10

    work page 2012

  8. [8]

    Scott Beamer, Krste Asanović, and David Patterson. 2015. The GAP benchmark suite. arXiv preprint arXiv:1508.03619 (2015)

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  9. [9]

    Richard Bellman. 1958. On a routing problem. Quarterly of applied mathematics 16, 1 (1958), 87–90

    work page 1958

  10. [10]

    Blelloch, Daniel Anderson, and Laxman Dhulipala

    Guy E. Blelloch, Daniel Anderson, and Laxman Dhulipala. 2020. ParlayLib — a toolkit for parallel algorithms on shared-memory multicore machines. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) . 507–509

    work page 2020

  11. [11]

    Blelloch, Jeremy T

    Guy E. Blelloch, Jeremy T. Fineman, Yan Gu, and Yihan Sun. 2020. Optimal parallel algorithms in the binary-forking model. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 89–102

    work page 2020

  12. [12]

    Blelloch, Yan Gu, Yihan Sun, and Kanat Tangwongsan

    Guy E. Blelloch, Yan Gu, Yihan Sun, and Kanat Tangwongsan. 2016. Parallel Shortest Paths Using Radius Stepping. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 443–454

    work page 2016

  13. [13]

    Paolo Boldi and Sebastiano Vigna. 2004. The webgraph framework I: compression techniques. In Proceedings of the 13th international conference on World Wide Web . 595–602

    work page 2004

  14. [14]

    Gerth Stølting Brodal, Jesper Larsson Träff, and Christos D Zaroliagis. 1998. A parallel priority queue with constant time operations. J. Parallel and Distrib. Comput. 49, 1 (1998), 4–21

    work page 1998

  15. [15]

    Fineman, and Katina Russell

    Nairen Cao, Jeremy T. Fineman, and Katina Russell. 2020. Efficient construction of directed hopsets and parallel approximate shortest paths. In ACM Symposium on Theory of Computing (STOC) . 336–349

    work page 2020

  16. [16]

    Cormen, Charles E

    Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein

    work page

  17. [17]

    MIT Press

    Introduction to Algorithms (3rd edition) . MIT Press

    work page

  18. [18]

    George Dantzig. 1963. Linear programming and extensions . Princeton university press

    work page 1963

  19. [19]

    Laxman Dhulipala, Changwan Hong, and Julian Shun. 2020. ConnectIt: a frame- work for static and incremental parallel graph connectivity algorithms. Proceed- ings of the VLDB Endowment (PVLDB) 14, 4 (2020), 653–667

    work page 2020

  20. [20]

    Julian Dibbelt, Ben Strasser, and Dorothea Wagner. 2016. Customizable contrac- tion hierarchies. J. Experimental Algorithmics 21 (2016), 1–49

    work page 2016

  21. [21]

    Dijkstra

    Edsger W. Dijkstra. 1959. A note on two problems in connexion with graphs. Numerische mathematik 1, 1 (1959)

    work page 1959

  22. [22]

    Xiaojun Dong, Yan Gu, Yihan Sun, and Letong Wang. 2024. Brief Announcement: PASGAL: Parallel And Scalable Graph Algorithm Library. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)

    work page 2024

  23. [23]

    Xiaojun Dong, Yan Gu, Yihan Sun, and Yunming Zhang. 2021. Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) . 184–197

    work page 2021

  24. [24]

    Xiaojun Dong, Andy Li, Yan Gu, and Yihan Sun. 2025. Orionet: Parallel Point-to- Point Shortest Paths and Batch Queries. https://github.com/ucrparlay/Orionet

    work page 2025

  25. [25]

    Xiaojun Dong, Andy Li, Yan Gu, and Yihan Sun. 2025. Parallel Point-to-Point Shortest Paths and Batch Queries. arXiv preprint:2506.16488 (2025)

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  26. [26]

    Xiaojun Dong, Letong Wang, Yan Gu, and Yihan Sun. 2023. Provably Fast and Space-Efficient Parallel Biconnectivity. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP) . 52–65

    work page 2023

  27. [27]

    Dheeru Dua and Casey Graf. 2017. UCI Machine Learning Repository. http: //archive.ics.uci.edu/ml/

    work page 2017

  28. [28]

    Michael Elkin and Ofer Neiman. 2019. Hopsets with constant hopbound, and applications to approximate shortest paths. SIAM J. Comput. 48, 4 (2019), 1436– 1480

    work page 2019

  29. [29]

    Jordi Fonollosa, Sadique Sheik, Ramón Huerta, and Santiago Marco. 2015. Reser- voir computing compensates slow response of chemosensor arrays exposed to fast varying gas concentrations in continuous monitoring. Sensors and Actuators B: Chemical 215 (2015), 618–629

    work page 2015

  30. [30]

    Lester R Ford Jr. 1956. Network flow theory. Technical Report. Rand Corp Santa Monica Ca

    work page 1956

  31. [31]

    Robert Geisberger and Peter Sanders. 2010. Engineering time-dependent many-to- many shortest paths computation. In 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS’10) . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik

    work page 2010

  32. [32]

    Robert Geisberger, Peter Sanders, Dominik Schultes, and Daniel Delling. 2008. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In International Workshop on Experimental Algorithms (WEA). Springer, 319–333

    work page 2008

  33. [33]

    Robert Geisberger, Peter Sanders, Dominik Schultes, and Christian Vetter. 2012. Exact routing in large road networks using contraction hierarchies.Transportation Science 46, 3 (2012), 388–404. 14

    work page 2012

  34. [34]

    Andrew V Goldberg and Chris Harrelson. 2005. Computing the shortest path: A search meets graph theory. In ACM-SIAM Symposium on Discrete Algorithms (SODA), Vol. 5. 156–165

    work page 2005

  35. [35]

    Andrew V Goldberg, Haim Kaplan, and Renato F Werneck. 2006. Reach for A*: Efficient point-to-point shortest path algorithms. In2006 Proceedings of the Eighth Workshop on Algorithm Engineering and Experiments (ALENEX) . SIAM, 129–143

    work page 2006

  36. [36]

    Peter E Hart, Nils J Nilsson, and Bertram Raphael. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics 4, 2 (1968), 100–107

    work page 1968

  37. [37]

    Robert Holte, Ariel Felner, Guni Sharon, and Nathan Sturtevant. 2016. Bidirec- tional search that is guaranteed to meet in the middle. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 30

    work page 2016

  38. [38]

    Takahiro Ikeda, Min-Yao Hsu, Hiroshi Imai, Shigeki Nishimura, Hiroshi Shimoura, Takeo Hashimoto, Kenji Tenmoku, and Kunihiko Mitoh. 1994. A fast algorithm for finding better routes by AI search techniques. In Proceedings of VNIS’94-1994 Vehicle Navigation and Information Systems Conference . IEEE, 291–296

    work page 1994

  39. [39]

    Dan Klein and Christopher D Manning. 2003. A* parsing: Fast exact Viterbi parse selection. In Proceedings of the 2003 Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics . 119–126

    work page 2003

  40. [40]

    Sebastian Knopp, Peter Sanders, Dominik Schultes, Frank Schulz, and Dorothea Wagner. 2007. Computing many-to-many shortest paths using highway hierar- chies. In Algorithm Engineering and Experiments (ALENEX) . SIAM, 36–45

    work page 2007

  41. [41]

    Sunita Kumawat, Chanchal Dudeja, and Pawan Kumar. 2021. An extensive review of shortest path problem solving algorithms. In 2021 5th International Conference on Intelligent Computing and Control Systems (ICICCS) . IEEE, 176–184

    work page 2021

  42. [42]

    Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. 2010. What is Twitter, a social network or a news media?. In International World Wide Web Conference (WWW). 591–600

    work page 2010

  43. [43]

    YongChul Kwon, Dylan Nunley, Jeffrey P Gardner, Magdalena Balazinska, Bill Howe, and Sarah Loebman. 2010. Scalable clustering algorithm for N-body simulations in a shared-nothing cluster. In International Conference on Scientific and Statistical Database Management . Springer, 132–150

    work page 2010

  44. [44]

    Michael Luby and Prabhakar Ragde. 1989. A bidirectional shortest-path algorithm with good average-case behavior. Algorithmica 4 (1989), 551–567

    work page 1989

  45. [45]

    Dennis Luxen and Christian Vetter. 2011. Real-time routing with OpenStreetMap data. In SIGSPATIAL international conference on advances in geographic informa- tion systems. 513–516

    work page 2011

  46. [46]

    Thomas L Magnanti and Prakash Mirchandani. 1993. Shortest paths, single origin-destination network design, and associated polyhedra. Networks 23, 2 (1993), 103–121

    work page 1993

  47. [47]

    Abbas Mazloumi, Xiaolin Jiang, and Rajiv Gupta. 2019. Multilyra: Scalable dis- tributed evaluation of batches of iterative graph queries. In2019 IEEE International Conference on Big Data (Big Data) . IEEE, 349–358

    work page 2019

  48. [48]

    Abbas Mazloumi, Chengshuo Xu, Zhijia Zhao, and Rajiv Gupta. 2020. BEAD: Batched Evaluation of Iterative Graph Queries with Evolving Analytics Demands. In 2020 IEEE International Conference on Big Data (Big Data) . IEEE, 461–468

    work page 2020

  49. [49]

    Robert Meusel, Oliver Lehmberg, Christian Bizer, and Sebastiano Vigna. 2014. Web Data Commons — Hyperlink Graphs. http://webdatacommons.org/ hyperlinkgraph

    work page 2014

  50. [50]

    Ulrich Meyer and Peter Sanders. 2003. Δ-stepping: a parallelizable shortest path algorithm. Journal of Algorithms 49, 1 (2003), 114–152

    work page 2003

  51. [51]

    Joseph SB Mitchell et al. 2000. Geometric Shortest Paths and Network Optimiza- tion. Handbook of computational geometry 334 (2000), 633–702

    work page 2000

  52. [52]

    T Alastair J Nicholson. 1966. Finding the shortest route between two points in a network. The computer journal 9, 3 (1966), 275–280

    work page 1966

  53. [53]

    Nils J Nilsson. 2009. The quest for artificial intelligence . Cambridge University Press

    work page 2009

  54. [54]

    OpenStreetMap contributors. 2010. OpenStreetMap. https://www.openstreetmap. org/

    work page 2010

  55. [55]

    Judea Pearl. 1984. Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley Longman Publishing Co., Inc

    work page 1984

  56. [56]

    Ira Pohl. 1969. Bi-directional and heuristic search in path problems. Technical Report. Stanford Linear Accelerator Center, Calif

    work page 1969

  57. [57]

    Miao Qiao, Hong Cheng, Lijun Chang, and Jeffrey Xu Yu. 2012. Approximate shortest distance computing: A query-dependent local landmark scheme. IEEE Transactions on Knowledge and Data Engineering 26, 1 (2012), 55–68

    work page 2012

  58. [58]

    Luis Henrique Oliveira Rios and Luiz Chaimowicz. 2011. Pnba*: A parallel bidirectional heuristic search algorithm. InENIA VIII Encontro Nacional de Inteligê ncia Artificial

    work page 2011

  59. [59]

    Samir K Sadhukhan. 2013. Bidirectional heuristic search based on error estimate. CSI Journal of Computing 2, 1-2 (2013), S1

    work page 2013

  60. [60]

    Edward C Sewell and Sheldon H Jacobson. 2021. Dynamically improved bounds bidirectional search. Artificial Intelligence 291 (2021), 103405

    work page 2021

  61. [61]

    Hanmao Shi and Thomas H. Spencer. 1999. Time-Work Tradeoffs of the Single- Source Shortest Paths Problem. Journal of Algorithms 30, 1 (1999), 19–32

    work page 1999

  62. [62]

    Blelloch

    Julian Shun and Guy E. Blelloch. 2013. Ligra: A Lightweight Graph Processing Framework for Shared Memory. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP). 135–146

    work page 2013

  63. [63]

    Blelloch, Jeremy T

    Julian Shun, Guy E. Blelloch, Jeremy T. Fineman, and Phillip B. Gibbons. 2013. Re- ducing Contention Through Priority Updates. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 152–163

    work page 2013

  64. [64]

    Nathan Sturtevant and Ariel Felner. 2018. A brief history and recent achievements in bidirectional search. In AAAI Conference on Artificial Intelligence, Vol. 32

    work page 2018

  65. [65]

    Manuel Then, Moritz Kaufmann, Fernando Chirigati, Tuan-Anh Hoang-Vu, Kien Pham, Alfons Kemper, Thomas Neumann, and Huy T Vo. 2014. The more the mer- rier: Efficient multi-source graph traversal. Proceedings of the VLDB Endowment 8, 4 (2014), 449–460

    work page 2014

  66. [66]

    Konstantin Tretyakov, Abel Armas-Cervantes, Luciano García-Ba ñuelos, Jaak Vilo, and Marlon Dumas. 2011. Fast fully dynamic landmark-based estimation of shortest path distances in very large graphs. In ACM International Conference on Information and Knowledge Management . 1785–1794

    work page 2011

  67. [67]

    Gintaras Vaira and Olga Kurasova. 2011. Parallel bidirectional dijkstra’s shortest path algorithm. In Databases and Information Systems VI . IOS Press, 422–435

    work page 2011

  68. [68]

    Letong Wang, Xiaojun Dong, Yan Gu, and Yihan Sun. 2023. Parallel Strong Con- nectivity Based on Faster Reachability. ACM SIGMOD International Conference on Management of Data (SIGMOD) 1, 2 (2023), 1–29

    work page 2023

  69. [69]

    Yiqiu Wang, Shangdi Yu, Laxman Dhulipala, Yan Gu, and Julian Shun. 2021. GeoGraph: A Framework for Graph Processing on Geometric Data. ACM SIGOPS Operating Systems Review 55, 1 (2021), 38–46

    work page 2021

  70. [70]

    Chengshuo Xu, Abbas Mazloumi, Xiaolin Jiang, and Rajiv Gupta. 2020. SimGQ: Simultaneously evaluating iterative graph queries. In2020 IEEE 27th International Conference on High Performance Computing, Data, and Analytics (HiPC) . IEEE, 1–10

    work page 2020

  71. [71]

    Chengshuo Xu, Abbas Mazloumi, Xiaolin Jiang, and Rajiv Gupta. 2022. SimGQ+: Simultaneously evaluating iterative point-to-all and point-to-point graph queries. Journal of parallel and distributed computing 164 (2022), 12–27

    work page 2022

  72. [72]

    Chengshuo Xu, Keval Vora, and Rajiv Gupta. 2019. Pnp: Pruning and prediction for point-to-point iterative graph analytics. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems. 587–600

    work page 2019

  73. [73]

    Jaewon Yang and Jure Leskovec. 2015. Defining and evaluating network commu- nities based on ground-truth. Knowledge and Information Systems 42, 1 (2015), 181–213

    work page 2015

  74. [74]

    Wei Zeng and Richard L Church. 2009. Finding shortest paths on real road networks: the case for A. International journal of geographical information science 23, 4 (2009), 531–543

    work page 2009

  75. [75]

    Guozheng Zhang, Gilead Posluns, and Mark C Jeffrey. 2024. Multi Bucket Queues: Efficient Concurrent Priority Scheduling. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 113–124

    work page 2024

  76. [76]

    Yunming Zhang, Ajay Brahmakshatriya, Xinyi Chen, Laxman Dhulipala, Shoaib Kamil, Saman Amarasinghe, and Julian Shun. 2020. Optimizing ordered graph algorithms with GraphIt. In International Symposium on Code Generation and Optimization (CGO). 158–170

    work page 2020

  77. [77]

    Yu Zheng, Like Liu, Longhao Wang, and Xing Xie. 2008. Learning transportation mode from raw gps data for geographic applications on the web. In International World Wide Web Conference (WWW). 247–256. A Proof for Thm. 3.4 We present the proof for Thm. 3.4, which states that our BiD-A∗ algorithm can correctly compute the shortest distance between the source...

    work page arXiv 2008