Pith. sign in

REVIEW 3 major objections 5 minor 39 references

Single-Source Regular Path Querying in Terms of Linear Algebra

T0 review · 3 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims that single-source two-way regular path queries can be evaluated by a frontier-based BFS over boolean matrices, proves the algorithm correct, and reports large average speedups over four graph systems on real-world…

desk verdict Solid, useful paper on linear-algebra BFS for 2-RPQs, with a fixable correctness gap (empty-word paths) and some benchmark caveats; worth refereeing after those are addressed. read the letter →

arxiv 2412.10287 v2 pith:JAIWMCTF submitted 2024-12-13 cs.DS

Georgiy Belyanin , Semyon Grigoriev , Rodion Suvorov This is my paper · ORCID
classification cs.DS
keywords two-wayregularpathqueriessparselinearalgebraGraphBLASbreadth-firstsearchknowledgegraphsLAGraphRPQevaluation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Two-way regular path queries (2-RPQs) ask for all vertices reachable from a given vertex by a path whose edge-label word belongs to a regular language, and they have become part of the GQL standard yet remain slow on real-world graphs. This paper claims that a BFS-style traversal expressed entirely in boolean sparse matrix operations evaluates single-source 2-RPQs accurately and quickly: at each step a frontier matrix of (automaton state, graph vertex) pairs is advanced by composing the query automaton's transposed Boolean decomposition with the graph's adjacency matrices, and the accumulated matrix masks out already-visited pairs. The authors prove by induction that the final matrix contains exactly the answer set, and they report average speedups of 6.8x over the RPQ-matrix algorithm, 11.3x over MillenniumDB, 18.9x over FalkorDB, and 16.8x over Blazegraph on the Wikidata query set. If true, this gives graph database engines a way to accelerate a standard query class by reusing mature parallel sparse linear algebra kernels rather than specialized indexing.

What carries the argument

The load-bearing object is Algorithm 1's update rule $M \leftarrow \bigoplus_{a\in\Sigma^{\leftrightarrow}\cap L^{\leftrightarrow}} ((N_a)^T \otimes M \otimes G_a)\langle \neg P\rangle$. Here $N_a$ and $G_a$ are the Boolean decompositions of the 2-NFA and the graph adjacency matrices by label, $\otimes$ is boolean matrix multiplication (relation composition), $\oplus$ is logical-or (union), and $\langle \neg P\rangle$ masks away pairs already accumulated, so each pair enters the frontier at most once. The frontier matrix $M$ holds the BFS layer of simultaneously reachable automaton states and graph vertices, $P$ accumulates all layers, and the final answer is the vector $F\otimes P$ for the final states $F$. A companion formulation (Algorithm 2) drops the separate traversal matrix $M$ and updates $P$ directly; the implementation switches between the two when the intermediate matrix reaches roughly 100 non-zero entries, a constant determined empirically for the studied datasets.

What would settle it

Run the identical Wikidata and RPQBench workloads while varying the switch threshold across orders of magnitude (for example 1, 10, 1,000, and 10,000 non-zero entries) and compare the average and median speedups; if the 6.8x–18.9x edge shrinks or reverses at thresholds far from 100, the empirical advantage is an artifact of the tuning constant rather than of the traversal structure itself.

Watch

Extended reading notes

Core claim

The central result is Theorem 4.1: the algorithm represented in Algorithm 1 computes a matrix $P$ such that $(q,v)\in P$ if and only if there is a 2-path $\pi_G$ in $G$ from $v_s$ to $v$ and a path $\pi_N$ in the 2-NFA $N$ from some start state to $q$ with $\omega^{\leftrightarrow}_G(\pi_G)\cap \omega_N(\pi_N)\neq \emptyset$; consequently $P_F=F\otimes P$ gives exactly the single-source 2-RPQ answer set. The proof is a straightforward induction on path length, with the invariant that after $n$ steps the frontier relation $M_n$ contains exactly those pairs reachable at depth $n$ whose label sets intersect and that have not appeared in earlier depths, and the loop is guaranteed to terminate in at most $|Q|\cdot|V|$ steps. The same construction solves single-destination queries by reversing the automaton and transposing the Boolean matrices. The authors further claim that this BFS-based formulation is not only correct but also competitive: on Wikidata it achieves the best mean query time for simple queries and remains within the one-minute limit on complex queries where competitors time out.

Load-bearing premise

The reported speedups depend on a single hand-tuned switch threshold of about 100 non-zero entries in the intermediate matrix, chosen for the studied datasets with no sensitivity analysis, so the benchmark results assume this one constant transfers to the workloads tested.

Editorial extensions

If this is right

  • Single-source 2-RPQs over graphs with hundreds of millions of edges can be answered in memory within one minute on workloads where three of the four compared graph databases time out.
  • Because the algorithm is expressed with boolean matrix operations, any fast parallel sparse linear algebra kernel can serve as the execution engine, avoiding per-database query-plan optimization.
  • The identical traversal solves single-destination 2-RPQs by reversing the 2-NFA and transposing the Boolean decompositions, effectively doubling the query class covered by one implementation.
  • The frontier-plus-accumulated-matrix structure separates the BFS layer from the visited set, which is exactly the shape needed for semiring-based variants that count paths or compute shortest distances without changing the traversal order.
  • The two-algorithm switch (frontier-based vs. accumulated-matrix-based) gives implementations a cheap adaptive knob that can be tuned per dataset or per query shape.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the threshold constant is truly dataset- and query-dependent, then the practical wins of LARPQ over RPQ-matrix are not solely structural; the same algorithm with a different threshold might lose on graphs with different density or label skew, and a self-tuning threshold would be a direct testable extension.
  • The paper's own results show RPQ-matrix wins on queries with rare labels and long concatenations, so a hybrid that routes label-rare query fragments to an evaluation-order optimizer and label-dense fragments to the BFS loop is a natural next step.
  • The masking step $\langle\neg P\rangle$ is where cycle handling lives; replacing it with a counting semiring would yield path counts per vertex, while keeping the same update rule, which is a concrete extension the authors only gesture at in the conclusion.
  • The threshold switch also indicates that on GPU or distributed targets (where launching many distinct kernels is costly) the accumulated-matrix variant may dominate for a wider range of queries, so porting the two-algorithm pair to such backends would test whether the 100-entry crossover is an artifact of CPU sparse-matrix kernels.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proposes LARPQ, a BFS-style algorithm for single-source 2-RPQs expressed with Boolean sparse matrix operations, and implements it in SuiteSparse:GraphBLAS/LAGraph. The algorithm simultaneously traverses the data graph and a 2-NFA for the regular language, maintaining the relation of reachable (automaton state, graph vertex) pairs and masking out already seen pairs to ensure termination. The authors prove correctness in Appendix A, describe an accumulated-matrix variant, and benchmark against RPQ-matrix, an RPQ-matrix reimplementation on GraphBLAS, MillenniumDB, FalkorDB, and Blazegraph on Wikidata, Yago-2S, and synthetic RPQBench workloads, reporting large average speedups on the Wikidata query set as well as cases where baselines are faster.

Significance. If the correctness gap identified below is repaired, the paper makes a useful contribution. It gives a clean linear-algebra formulation whose invariant proof is mostly elementary, and it ships an open implementation plus benchmark scripts, which is valuable for reproducibility. The comparison is unusually broad: two linear algebra solutions and three graph databases, on real and synthetic data. The main empirical claims are weakened, however, by a hand-tuned switch threshold with no sensitivity analysis and by the absence of a correctness statement for the second algorithm variant that is part of the measured implementation. The algorithmic idea is not conceptually radical, but the careful evaluation makes the paper of interest to the RPQ and graph-querying community.

major comments (3)
  1. [Section 4 (Algorithm 1); Appendix A] Theorem 4.1 (and its duplicate, Theorem A.1) is false as stated because Algorithm 1 never puts the initial relation M_0 into P. Line 3 initializes P to the zero matrix, line 4 initializes M to the start relation, and the loop body on lines 7-8 updates M before accumulating P, so after n iterations P contains only M_1,...,M_n. Appendix A uses exactly this convention: it defines P_n = union_{1<=m<=n} M_m and P = union_{m in N} M_m, so the proof establishes a statement that excludes length-0 paths. Since Definitions 2.2 and 2.6 explicitly admit zero-length paths, a query NFA with a final start state (e.g., an NFA for a* with no transitions) yields (q_F, v_s) in the answer set of Definition 2.6 while Algorithm 1 returns F tensor P = 0. The repair is local: initialize P to the same relation as M, or add M to P before the loop, and change the induction to P_n = union_{0<=m<=n} M_m; the termination argument should be adjusted accordingly. The paper must also state whether zero-length paths are intended to be answers and, if not, amend Definitions 2.2 and 2.6.
  2. [Section 5.1, Tables 1-3] The reported performance comparison depends on a single hand-tuned switch threshold of 100 nonzero entries. The paper states that 'for the studied datasets the most suitable value is 100', but it gives no sensitivity analysis for this constant and no argument that the value transfers from the Wikidata and Yago-2S workloads to the synthetic RPQBench graph. Because the advertised speedups (6.8x, 11.3x, 18.9x, 16.8x in the abstract, and the per-query times in Tables 1-3) are produced by the switched implementation, the empirical claims are not yet robust. I request a sensitivity study over a range of thresholds on at least the Wikidata and RPQBench workloads, or evidence that the threshold choice is not material.
  3. [Section 5.1 (Algorithm 2); Appendix A] Algorithm 2 is used by the implementation after the switch threshold is reached, but no correctness theorem is given for it. The proof in Appendix A covers only Algorithm 1, and the equivalence between the accumulated-matrix and traversal-matrix formulations is asserted informally. Since the reported timings come from an implementation that may execute Algorithm 2 for much of the traversal, the paper should supply a proof or precise invariant for Algorithm 2, or state explicitly that Algorithm 2 is a reformulation whose correctness follows by the same induction with P in place of M.
minor comments (5)
  1. [Section 5.2] The Yago-2S entry in Section 5.2 gives exactly the same statistics as Wikidata (610 million edges, 91 million vertices, 1400 distinct labels), which is contradicted by the 0.5 GB memory footprint reported for Yago-2S in Table 2 and by the known scale of the dataset. This looks like a copy-paste error and should be corrected.
  2. [Tables 1 and 2] The columns labeled 'Mean speedup' and 'Median speedup' contain values that are the reciprocals of the speedups advertised in the abstract (for example, LARPQ/RPQ-matrix = 0.15 corresponds to the claimed 6.8x speedup of LARPQ over RPQ-matrix). The caption should define the metric explicitly, and the table values should be made consistent with the text.
  3. [Appendix A] In the proof of the inductive step, the path pi'_N is described as going 'from q_F in Q_F to q''; this should presumably be from a starting state q_s in Q_S, and the text should be corrected for consistency with the invariant.
  4. [Appendix A] The termination argument states that P_{|Q||V|-1} has at least |Q||V| elements after |Q||V|-1 non-empty steps, but each non-empty step adds at least one new element, so the correct conclusion is that the loop may require |Q||V|+1 iterations before M vanishes. Finite termination is unaffected, but the bound should be corrected.
  5. [Section 4 (Algorithm 2 introduction)] The sentence introducing Algorithm 2 refers to 'appendix .' without a section number, and a displayed formula fragment precedes the algorithm. This is a formatting/completeness issue that should be cleaned up.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the correctness proof is self-contained and the empirical threshold is disclosed, not derived from the target result.

full rationale

The paper's central derivation chain is self-contained. The algorithm in Section 4 is expressed directly in terms of Boolean matrix operations, and the correctness argument in Appendix A proves an invariant on the matrices M_n and P_n by induction on path length, with P defined as the union of the M_m. No equation in the proof assumes the theorem it is trying to establish, and no fitted parameter is used in the derivation of correctness. The only fitted quantity in the paper is the switch threshold of 100 nonzero entries in Section 5.1, which is disclosed and described as empirically determined for the studied datasets; it affects performance comparisons but is not an input to the correctness result. The comparison also includes external systems (MillenniumDB, FalkorDB, Blazegraph, original RPQ-matrix) alongside an authors-implemented GraphBLAS port of RPQ-matrix, which is a benchmarking fairness concern rather than circular derivation. The zero-length path omission in Theorem 4.1 is a genuine correctness defect but is not circular: the proof does not redefine paths to force the conclusion; it simply omits M_0 from the accumulated P. That is a fixable bug, not an equivalence-by-construction between the premise and the claimed result.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The central correctness argument rests only on standard relation/matrix algebra and the synchronous product-automaton traversal. The performance story rests on one fitted threshold and on the behavior of SuiteSparse:GraphBLAS. No new entities are introduced.

free parameters (1)
  • switch threshold = 100 non-zero entries
    Determines when the implementation switches between the frontier-matrix formulation (Algorithm 1) and the accumulated-matrix formulation (Algorithm 2); chosen as 'the most suitable value' for the studied datasets (Section 5.1).
assumptions (4)
  • standard math Boolean matrix multiplication and addition over the OR/AND semiring faithfully represent composition and union of binary relations
    Section 3 establishes this correspondence and the algorithm is built on it.
  • domain assumption A word common to a graph path and an automaton path enforces equal path lengths, so a synchronous one-edge-per-transition traversal is complete
    Used in the invariant proof in Appendix A; valid because each symbol is consumed by exactly one graph edge and one automaton transition.
  • domain assumption Queries may accept the empty word and zero-length paths must be included in the answer, as stated in Definition 2.2
    The correctness theorem claims to cover this case, but Algorithm 1's pseudocode never adds the initial relation M_0 to P; the proof and algorithm disagree.
  • domain assumption SuiteSparse:GraphBLAS executes the Boolean matrix primitives correctly and the measured timings reflect the algorithm's performance
    The empirical evaluation in Section 5 depends on the library's behavior; this is standard tooling reliance.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Single-Source Regular Path Querying in Terms of Linear Algebra." pith.science (2026). https://pith.science/paper/JAIWMCTF

@misc{pith2026241210287,
  author       = {Pith},
  title        = {Pith review of: Single-Source Regular Path Querying in Terms of Linear Algebra},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JAIWMCTF}},
  note         = {Machine review of arXiv:2412.10287}
}
read the original abstract

Two-way regular path queries (2-RPQs) allow one to use regular languages over edges and inverted edges in edge-labelled graph to constrain paths of interest. 2-RPQs are (partially) adopted in different real-world graph analysis systems and have become a part of the GQL ISO standard. However the performance of 2-RPQs on real-world graphs remains a bottleneck for wider adoption. Utilisation of high-performance sparse linear algebra libraries for the algorithm implementation allows one to achieve significant speedup over competitors on real-world data and queries. We propose a new breadth-first-search-based algorithm that leverages linear algebra for evaluating single-source regular path queries. We integrate it into the LAGraph graph processing algorithm infrastructure and provide in-depth performance comparison on the large real-world knowledge bases. Additionally, we present extensive analysis of its performance across different query types using synthetic data, comparing it with various databases and other linear algebra-based approaches.

Figures

Figures reproduced from arXiv: 2412.10287 by the authors.

Figure 1
Figure 1. The algorithm step for graph and automaton for regular [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Wikidata dataset per-query evaluation time [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

39 extracted references · 26 canonical work pages

  1. [1]

    SPARQL 1.1 Query Language

    2013. SPARQL 1.1 Query Language. Technical Report. W3C. http://www.w3. org/TR/sparql11-query

    work page 2013

  2. [2]

    Chignell

    Zahid Abul-Basher, Nikolay Yakovets, Parke Godfrey, Shadi Ghajar-Khosravi, and Mark H. Chignell. 2017. TASWEET: Optimizing Disjunctive Path Queries in Graph Databases. InProceedings of the 20th International Conference on Extending Database Technology, EDBT 2017, Venice, Italy, March 21-24, 2017, Volker Markl, Salvatore Orlando, Bernhard Mitschang, Perikl...

    work page doi:10.5441/002/edbt.2017.47 2017

  3. [3]

    Renzo Angles, Marcelo Arenas, Pablo Barceló, Aidan Hogan, Juan Reutter, and Domagoj Vrgoč. 2017. Foundations of Modern Query Languages for Graph Databases. ACM Comput. Surv.50, 5, Article 68 (Sept. 2017), 40 pages. https: //doi.org/10.1145/3104031

    doi:10.1145/3104031 2017

  4. [4]

    InString Processing and Information Retrieval: 30th International Symposium, SPIRE 2023, Pisa, Italy, September 26–28, 2023, Proceedings(Pisa, Italy)

    DiegoArroyuelo,AdriánGómez-Brandón,andGonzaloNavarro.2023.Evaluating Regular Path Queries on Compressed Adjacency Matrices. InString Processing and Information Retrieval: 30th International Symposium, SPIRE 2023, Pisa, Italy, September 26–28, 2023, Proceedings(Pisa, Italy). Springer-Verlag, Berlin, Heidelberg, 35–48. https://doi.org/10.1007/978-3-031-43980-3_4

    work page doi:10.1007/978-3-031-43980-3_4 2023

  5. [5]

    Diego Arroyuelo, Adrián Gómez-Brandón, Aidan Hogan, Gonzalo Navarro, and Javiel Rojas-Ledesma. 2023. Optimizing RPQs over a compact graph representation. The VLDB Journal33, 2 (Sept. 2023), 349–374. https://doi.org/ 10.1007/s00778-023-00811-2

    doi:10.1007/s00778-023-00811-2 2023

  6. [6]

    Diego Arroyuelo, Aidan Hogan, Gonzalo Navarro, and Javiel Rojas-Ledesma

    work page

  7. [7]

    Chris Barrett, Riko Jacob, and Madhav Marathe. 2000. Formal-Language- Constrained Path Problems. SIAM J. Comput.30, 3 (May 2000), 809–837. https://doi.org/10.1137/S0097539798337716

    doi:10.1137/s0097539798337716 2000

  8. [8]

    Angela Bonifati, George Fletcher, Hannes Voigt, and Nikolay Yakovets. 2018. QueryingGraphs. SpringerInternationalPublishing. https://doi.org/10.1007/978- 3-031-01864-0

    doi:10.1007/978- 2018

Show all 39 references
  1. [9]

    Benjamin Brock, Aydın Buluç, Timothy Mattson, Scott McMillan, and José Moreira. 2021. The graphblas c api specification.GraphBLAS. org, Tech. Rep (2021)

    2021

  2. [10]

    Aydın Buluç and John R Gilbert. 2011. The Combinatorial BLAS: design, implementation, and applications. The International Journal of High Perfor- mance Computing Applications25, 4 (2011), 496–509. https://doi.org/10.1177/ 1094342011403516 arXiv:https://doi.org/10.1177/1094342011403516

    2011 doi

  3. [11]

    Pieter Cailliau, Tim Davis, Vijay Gadepally, Jeremy Kepner, Roi Lipman, Jeffrey Lovitz, and Keren Ouaknine. 2019. RedisGraph GraphBLAS Enabled Graph Database. In2019 IEEE International Parallel and Distributed Processing Sym- posium Workshops (IPDPSW). IEEE, 285–286. https://do...

    2019

  4. [12]

    Query processing using views for regular path queries with inverse

    Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, Moshe Y Vardi, et al.2000. Query processing using views for regular path queries with inverse. In ACM Principles of Database Systems. 58–66

    2000

  5. [13]

    Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. 2000. Containment of conjunctive regular path queries with inverse. In Proceedings of the Seventh International Conference on Principles of Knowledge Representation and Reasoning(Breckenridge, Colora...

    2000

  6. [15]

    Timothy A. Davis. 2019. Algorithm 1000: SuiteSparse:GraphBLAS: Graph Algorithms in the Language of Sparse Linear Algebra.ACM Trans. Math. Softw. 45, 4, Article 44 (dec 2019), 25 pages. https://doi.org/10.1145/3322125

    2019 doi

  7. [16]

    Timothy A. Davis. 2023. Algorithm 1037: SuiteSparse:GraphBLAS: Parallel Graph Algorithms in the Language of Sparse Linear Algebra.ACM Trans. Math. Softw.49, 3, Article 28 (Sept. 2023), 30 pages. https://doi.org/10.1145/3577195

    2023 doi

  8. [17]

    Davis, and Gábor Szárnyas

    Márton Elekes, Attila Nagy, Dávid Sándor, János Benjamin Antal, Timo- thy A. Davis, and Gábor Szárnyas. 2020. A GraphBLAS solution to the SIGMOD 2014 Programming Contest using multi-source BFS. In2020 IEEE High Performance Extreme Computing Conference (HPEC). 1–7. https: //doi...

    2020

  9. [18]

    Tomáš Faltín, Vasileios Trigonakis, Ayoub Berdai, Luigi Fusco, Călin Iorgulescu, Jinsoo Lee, Jakub Yaghob, Sungpack Hong, and Hassan Chafi. 2023. Distributed Asynchronous Regular Path Queries (RPQs) on Graphs. InProceedings of the 24th International Middleware Conference: Indu...

    2023

  10. [19]

    Benjamín Farias, Carlos Rojas, and Domagoj Vrgoc. 2023. MillenniumDB path query challenge (short paper). InProceedings of the 15th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW 2023), Santiago de Chile, Chile, May 22-26, 2023 (CEUR Workshop Pr...

    2023

  11. [20]

    Nadime Francis, Alastair Green, Paolo Guagliardo, Leonid Libkin, Tobias Lin- daaker, Victor Marsault, Stefan Plantikow, Mats Rydberg, Petra Selmer, and Andrés Taylor. 2018. Cypher: An Evolving Query Language for Property Graphs. In Proceedings of the 2018 International Confere...

    2018

  12. [22]

    Xintong Guo, Hong Gao, and Zhaonian Zou. 2021. Distributed processing of regularpathqueriesinRDFgraphs. Knowl.Inf.Syst. 63,4(April2021),993–1027. https://doi.org/10.1007/s10115-020-01536-2

    2021 doi

  13. [23]

    Information technology – Database languages – GQL

    ISO/IEC 39075:2024 2024. Information technology – Database languages – GQL. Standard. International Organization for Standardization, Geneva, CH. https://www.iso.org/standard/76120.html

    2024

  14. [24]

    Bader, Aydın Buluç, Franz Franchetti, John R

    Jeremy Kepner, Peter Aaltonen, David A. Bader, Aydın Buluç, Franz Franchetti, John R. Gilbert, Dylan Hutchison, Manoj Kumar, Andrew Lumsdaine, Henning Meyerhenke, Scott McMillan, Carl Yang, John Douglas Owens, Marcin Zalewski, Timothy G. Mattson, and José E. Moreira. 2016. Mat...

    2016

  15. [25]

    André Koschmieder and Ulf Leser. 2012. Regular Path Queries on Large Graphs. InScientificandStatisticalDatabaseManagement ,AnastasiaAilamakiandShawn Bowers (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 177–194

    2012

  16. [26]

    PAIRPQ: An Efficient Path Index for Regular Path Queries on Knowledge Graphs

    BaozhuLiu,XinWang,PengkaiLiu,SizhuoLi,andXiaofeiWang.2021. PAIRPQ: An Efficient Path Index for Regular Path Queries on Knowledge Graphs. InWeb and Big Data, Leong Hou U, Marc Spaniol, Yasushi Sakurai, and Junying Chen (Eds.). Springer International Publishing, Cham, 106–120

    2021

  17. [27]

    RuoyanMa,ShenganZheng,GuifengWang,JinPu,YifanHua,WentaoWang,and Linpeng Huang. 2024. Accelerating Regular Path Queries over Graph Database with Processing-in-Memory. arXiv:2403.10051 [cs.DB] https://arxiv.org/abs/ 2403.10051

    2024 arXiv

  18. [28]

    Mendelzon and Peter T

    Alberto O. Mendelzon and Peter T. Wood. 1989. Finding Regular Simple Paths in Graph Databases.SIAM J. Comput.24 (1989), 1235–1258. https: //api.semanticscholar.org/CorpusID:12684556

    1989

  19. [29]

    Maurizio Nolé and Carlo Sartiani. 2016. Regular Path Queries on Massive Graphs. InProceedings of the 28th International Conference on Scientific and StatisticalDatabaseManagement (Budapest,Hungary) (SSDBM’16).Association for Computing Machinery, New York, NY, USA, Article 13, ...

    2016

  20. [30]

    The GraphBLAS in Julia and Python: the PageRank and Triangle Centralities

    MichelPelletier,WillKimmerer,TimothyA.Davis,andTimothyG.Mattson.2021. The GraphBLAS in Julia and Python: the PageRank and Triangle Centralities. In2021 IEEE High Performance Extreme Computing Conference (HPEC). 1–7. https://doi.org/10.1109/HPEC49654.2021.9622789

    2021

  21. [31]

    Oracev Egor Stanislavovic. 2023. Generalized sparse linear algebra library with vendor-agnostic GPUs acceleration. (2023)

    2023

  22. [32]

    Bader, Timothy A

    Gábor Szárnyas, David A. Bader, Timothy A. Davis, James Kitchen, Timo- thy G. Mattson, Scott McMillan, and Erik Welch. 2021. LAGraph: Linear Algebra, Network Analysis Libraries, and the Study of Graph Algorithms. arXiv:2104.01661 [cs.MS] https://arxiv.org/abs/2104.01661

    2021 arXiv

  23. [33]

    Grigorev

    Arseniy Terekhov, Vlada Pogozhelskaya, Vadim Abzalov, Timur Zinnatulin, and Semyon V. Grigorev. 2021. Multiple-Source Context-Free Path Querying in Terms of Linear Algebra. InInternational Conference on Extending Database Technology. https://api.semanticscholar.org/CorpusID:232284054

    2021

  24. [34]

    Oskar van Rest, Sungpack Hong, Jinha Kim, Xuming Meng, and Hassan Chafi

  25. [35]

    Domagoj Vrgoc, Carlos Rojas, Renzo Angles, Marcelo Arenas, Diego Arroyuelo, Carlos Buil Aranda, Aidan Hogan, Gonzalo Navarro, Cristian Riveros, and Juan Romero. 2021. MillenniumDB: A Persistent, Open-Source, Graph Database. arXiv:2111.01540 [cs.DB] https://arxiv.org/abs/2111.01540

    2021 arXiv

  26. [36]

    Hui Wang, Xin Wang, Menglu Ma, and Yiheng You. 2025. RPQBench: A Benchmark for Regular Path Queries on Graph Data. InWeb Information Systems Engineering–WISE2024 ,MahmoudBarhamgi,HuaWang,andXinWang(Eds.). Springer Nature Singapore, Singapore, 351–367

    2025

  27. [37]

    Xin Wang, Simiao Wang, Yueqi Xin, Yajun Yang, Jianxin Li, and Xiaofei Wang

  28. [38]

    Carl Yang, Aydın Buluç, and John D. Owens. 2022. GraphBLAST: A High- Performance Linear Algebra-based Graph Framework on the GPU.ACM Trans. Math.Softw. 48,1,Article1(feb2022),51pages. https://doi.org/10.1145/3466795 Georgiy Belyanin, Rodion Suvorov, and Semyon Grigorev A PROOF...

    2022 doi

  29. [2016]

    Association for Computing Machinery, NewYork,NY,USA,Article7,6pages

    PGQL:apropertygraphquerylanguage.In ProceedingsoftheFourthInter- national Workshop on Graph Data Management Experiences and Systems(Red- wood Shores, California)(GRADES ’16). Association for Computing Machinery, NewYork,NY,USA,Article7,6pages. https://doi.org/10.1145/2960414.2960421

  30. [2019]

    2019), 1465–1496

    Distributed Pregel-based provenance-aware regular path query processing on RDF knowledge graphs.World Wide Web23, 3 (Nov. 2019), 1465–1496. https://doi.org/10.1007/s11280-019-00739-0

    2019 doi

  31. [2022]

    In2022 IEEE 38th International Conference on Data Engineering (ICDE)

    Time- and Space-Efficient Regular Path Queries. In2022 IEEE 38th International Conference on Data Engineering (ICDE). 3091–3105. https: //doi.org/10.1109/ICDE53745.2022.00277

    2022

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.