DBScholar

Back to papers

Efficient Subgraph Matching by Postponing Cartesian Products

Summary: Postpones Cartesian products in Ullmann-style subgraph matching to curb unpromising results from dissimilar vertices. Adds a path-based DS of size O(|E(G)|·|V(q)|) to reduce the |V(G)|^(|V(q)|−1) blowup and yield up to 3 orders of magnitude speedups. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
5325
Venue
SIGMOD
Year
2016
Pagerank
0.00015214062
Overall Rank
659 | 95.49%
DOI
10.1145/2882903.2915236

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{bi_sigmod16,
        title = {{Efficient Subgraph Matching by Postponing Cartesian Products}},
        author = {Bi, Fei and Chang, Lijun and Lin, Xuemin and Qin, Lu and Zhang, Wenjie},
        series = {{SIGMOD} '16},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2882903.2915236},
        url = {https://dl.acm.org/doi/10.1145/2882903.2915236},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 23 of 73 citing papers.

Rank Citing Paper Year Venue Pagerank
10,354 Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings 2026 SIGMOD 5.093636e-05
10,375 GraphMatch: Subgraph Query Processing on Steroids 2026 SIGMOD 5.093636e-05
10,376 GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries 2026 SIGMOD 5.093636e-05
10,419 A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis] 2026 SIGMOD 5.093636e-05
10,428 An Extensive Experimental Study of Indexes in Continuous Subgraph Matching:[Experiments & Analysis] 2026 SIGMOD 5.093636e-05
10,452 Enumerating Graph Pattern Matches with ML Oracles 2026 SIGMOD 5.093636e-05
10,524 A Semantics-aware Approach for Graph Edit Distance Estimation over Knowledge Graphs 2026 VLDB 5.093636e-05
10,552 CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination 2026 VLDB 5.093636e-05
10,558 Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration 2026 VLDB 5.093636e-05
10,564 gMatch: Fine-Grained and Hardware-Efficient Subgraph Matching on GPUs 2026 VLDB 5.093636e-05
10,590 Aquila: A High-Concurrency System for Incremental Graph Query 2026 VLDB 5.093636e-05
10,606 Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching 2026 VLDB 5.093636e-05
10,787 cuMatch: A GPU-based Memory-Efficient Worst-case Optimal Join Processing Method for Subgraph Queries with Complex Patterns 2025 SIGMOD 5.093636e-05
10,885 Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach 2025 VLDB 5.093636e-05
10,952 Accelerating Subgraph Matching through Fine-grained and Powerful Equivalences 2025 VLDB 5.093636e-05
11,072 Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds 2025 VLDB 5.093636e-05
11,075 Mix & Match: Subgraph Matching for Absolute Coverage 2025 VLDB 5.093636e-05
11,165 gSWORD: GPU-accelerated Sampling for Subgraph Counting 2024 SIGMOD 5.093636e-05
11,192 Atom: An Efficient Query Serving System for Embedding-based Knowledge Graph Reasoning with Operator-level Batching 2024 SIGMOD 5.093636e-05
11,205 Towards a Converged Relational-Graph Optimization Framework 2024 SIGMOD 5.093636e-05
11,217 FusionQuery: On-demand Fusion Queries over Multi-source Heterogeneous Data 2024 VLDB 5.093636e-05
11,762 Simulation-based Approximate Graph Pattern Matching 2020 SIGMOD 5.093636e-05
11,793 IDAR: Fast Supergraph Search Using DAG Integration 2020 VLDB 5.093636e-05
Previous Page 2 / 2 Next

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.

Previous Page 1 / 1 Next

Semantically Similar Papers