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: 13036
Venue: VLDB
Year: 2023
Pagerank: 5.4626107e-05
Overall Rank: 5,517 | 61.63%
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,744	Output-Sensitive Evaluation of Regular Path Queries	2025	PODS	4.2897489e-05
10,070	DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs	2026	SIGMOD	4.1945683e-05
10,485	Finding Logic Bugs in Graph-processing Systems via Graph-cutting	2025	SIGMOD	4.1945683e-05
10,658	LLMLog: Advanced Log Template Generation via LLM-driven Multi-Round Annotation	2025	VLDB	4.1945683e-05
10,912	Distinct Shortest Walk Enumeration for RPQs	2024	PODS	4.1945683e-05
11,079	Complex-Path: Effective and Efficient Node Ranking with Paths in Billion-Scale Heterogeneous Graphs	2024	VLDB	4.1945683e-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.00030259041
363	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.00025715157
690	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.00018099792
789	Cypher: An Evolving Query Language for Property Graphs	2018	SIGMOD	0.00016634256
810	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00016428374
964	G-CORE: A Core for Future Graph Query Languages	2018	SIGMOD	0.0001497475
993	D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data	2003	SIGMOD	0.00014765816
1,037	Querying Graph Databases	2013	PODS	0.00014502493
1,056	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.0001441128
1,259	Aggregation and Ordering in Factorised Databases	2013	VLDB	0.00012995821
1,579	Query Preserving Graph Compression	2012	SIGMOD	0.00011283792
1,812	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS	0.00010467069
2,342	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.0015589e-05
2,505	Graph Pattern Matching in GQL and SQL/PGQ	2022	SIGMOD	8.634551e-05
3,082	FDB: A Query Engine for Factorised Relational Databases	2012	VLDB	7.6014248e-05
3,306	PG-Keys: Keys for Property Graphs	2021	SIGMOD	7.2437997e-05
3,715	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8220943e-05
4,787	The Relational Data Borg is Learning	2020	VLDB	5.9224501e-05
5,424	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS	5.5126983e-05
9,798	Threshold Queries in Theory and in the Wild	2022	VLDB	4.2818172e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
919	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00015343179
5,651	GPC: A Pattern Calculus for Property Graphs	2023	PODS	5.3905536e-05
3,652	The Complexity of Evaluating Path Expressions in SPARQL	2012	PODS	6.875313e-05
1,812	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS	0.00010467069
4,946	Querying Graph Patterns	2011	PODS	5.8149362e-05
1,037	Querying Graph Databases	2013	PODS	0.00014502493
2,826	Regular Path Query Evaluation on Streaming Graphs	2020	SIGMOD	8.056119e-05
1,444	Finding Regular Simple Paths in Graph Databases	1989	VLDB	0.00011946075
461	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022499343
11,014	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	4.1945683e-05