Representing Paths in Graph Database Pattern Matching

Summary: Introduce path-multiset representations (PMRs) that encode path multisets exponentially to avoid intermediate blowup in graph pattern matching. Theory and experiments show PMRs suit RPQs (counting, sampling, unions) and yield massive speedups. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13037
Venue: VLDB
Year: 2023
Pagerank: 5.4573655e-05
Overall Rank: 5,527 | 61.59%
DOI: 10.14778/3587136.3587151

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,743	Output-Sensitive Evaluation of Regular Path Queries	2025	PODS	4.2856385e-05
10,070	DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs	2026	SIGMOD	4.1905499e-05
10,495	Finding Logic Bugs in Graph-processing Systems via Graph-cutting	2025	SIGMOD	4.1905499e-05
10,666	LLMLog: Advanced Log Template Generation via LLM-driven Multi-Round Annotation	2025	VLDB	4.1905499e-05
10,916	Distinct Shortest Walk Enumeration for RPQs	2024	PODS	4.1905499e-05
11,082	Complex-Path: Effective and Efficient Node Ranking with Paths in Billion-Scale Heterogeneous Graphs	2024	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 20 of 20 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
256	GraphLog: a Visual Formalism for Real Life Recursion	1990	PODS	0.00030241337
364	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.00025657601
657	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.00018581389
787	Cypher: An Evolving Query Language for Property Graphs	2018	SIGMOD	0.00016624372
808	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.000164132
964	G-CORE: A Core for Future Graph Query Languages	2018	SIGMOD	0.00014967208
993	D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data	2003	SIGMOD	0.00014759406
1,040	Querying Graph Databases	2013	PODS	0.00014483577
1,054	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00014397587
1,255	Aggregation and Ordering in Factorised Databases	2013	VLDB	0.00013011216
1,572	Query Preserving Graph Compression	2012	SIGMOD	0.00011296109
1,812	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS	0.00010458164
2,345	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	8.9933611e-05
2,504	Graph Pattern Matching in GQL and SQL/PGQ	2022	SIGMOD	8.629969e-05
3,088	FDB: A Query Engine for Factorised Relational Databases	2012	VLDB	7.5940302e-05
3,310	PG-Keys: Keys for Property Graphs	2021	SIGMOD	7.2370328e-05
3,702	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8251643e-05
4,787	The Relational Data Borg is Learning	2020	VLDB	5.9168117e-05
5,435	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS	5.5074113e-05
9,801	Threshold Queries in Theory and in the Wild	2022	VLDB	4.2777144e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,556	Materialized View Selection & View-Based Query Planning for Regular Path Queries	2024	SIGMOD	4.3212967e-05
5,663	GPC: A Pattern Calculus for Property Graphs	2023	PODS	5.3853781e-05
3,659	The Complexity of Evaluating Path Expressions in SPARQL	2012	PODS	6.8684407e-05
1,812	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS	0.00010458164
4,949	Querying Graph Patterns	2011	PODS	5.8090034e-05
1,040	Querying Graph Databases	2013	PODS	0.00014483577
2,832	Regular Path Query Evaluation on Streaming Graphs	2020	SIGMOD	8.048358e-05
1,445	Finding Regular Simple Paths in Graph Databases	1989	VLDB	0.00011937596
460	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022679846
11,017	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	4.1905499e-05