Connectivity-Oriented Property Graph Partitioning for Distributed Graph Pattern Query Processing

Summary: RCP partitions graphs by weakly connected components per relationship label to reduce crossing matches in variable-length path and labeled-pattern queries. It enables independent execution of basic and extended queries, with Neo4j/JanusGraph prototypes achieving nearly 100× speedups on billion-scale data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 7040
Venue: SIGMOD
Year: 2024
Pagerank: 5.093636e-05
Overall Rank: 11,197 | 23.18%
DOI: 10.1145/3698804

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Min Shi (Hunan University)
2. Peng Peng (Hunan University)
3. Xu Zhou (Hunan University)
4. Jiayu Liu (Hunan University)
5. Guoqing Xiao (Hunan University)
6. Kenli Li (Hunan University)

BibTeX Citation

@inproceedings{shi_sigmod24,
        title = {{Connectivity-Oriented Property Graph Partitioning for Distributed Graph Pattern Query Processing}},
        author = {Shi, Min and Peng, Peng and Zhou, Xu and Liu, Jiayu and Xiao, Guoqing and Li, Kenli},
        series = {{SIGMOD} '24},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3698804},
        url = {https://dl.acm.org/doi/10.1145/3698804},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,606	Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching	2026	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
3	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0012250108
366	Scalable Semantic Web Data Management Using Vertical Partitioning	2007	VLDB	0.00020039981
426	The LDBC Social Network Benchmark: Interactive Workload	2015	SIGMOD	0.00018692185
436	Trinity: A Distributed Graph Engine on a Memory Cloud	2013	SIGMOD	0.00018504439
547	Cypher: An Evolving Query Language for Property Graphs	2018	SIGMOD	0.00016731552
776	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00014110016
1,591	SQLGraph: An Efficient Relational-Based Property Graph Store	2015	SIGMOD	0.00010255536
1,836	Graph Pattern Matching in GQL and SQL/PGQ	2022	SIGMOD	9.6489549e-05
2,915	GraphScope: A Unified Engine For Big Graph Processing	2021	VLDB	7.9666977e-05
3,225	A Scalable Distributed Graph Partitioner	2015	VLDB	7.6245396e-05
3,752	Distributed Edge Partitioning for Trillion-edge Graphs	2019	VLDB	7.15217e-05
4,365	Application Driven Graph Partitioning	2020	SIGMOD	6.740899e-05
7,777	S2RDF: RDF Querying with SPARQL on Spark	2016	VLDB	5.5461212e-05
9,118	Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs	2024	SIGMOD	5.3201316e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	500	Scalable SPARQL Querying of Large RDF Graphs	2011	VLDB
2	2,221	Streaming Graph Partitioning: An Experimental Study	2018	VLDB
3	5,029	Performance Guarantees for Distributed Reachability Queries	2012	VLDB
4	1,803	Towards Effective Partition Management for Large Graphs	2012	SIGMOD
5	6,111	Scaling Queries over Big RDF Graphs with Semantic Hash Partitioning	2013	VLDB
6	10,488	R2O: A Dual-Layer Framework for Joint Rewriting and Ordering in Distributed Property Graph Query Optimization	2026	SIGMOD
7	7,362	A Study of Partitioning Policies for Graph Analytics on Large-scale Distributed Platforms	2019	VLDB
8	8,651	Distributed Set Reachability	2016	SIGMOD
9	3,109	Managing Large Dynamic Graphs Efficiently	2012	SIGMOD
10	10,361	DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs	2026	SIGMOD