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)
Incoming Non-self Citations Over Time
Authors
- 1. Fei Bi (University of New South Wales)
- 2. Lijun Chang (University of New South Wales)
- 3. Xuemin Lin (University of New South Wales)
- 4. Lu Qin (University of Technology Sydney)
- 5. Wenjie Zhang (University of New South Wales)
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 25 of 75 citing papers.
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
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 1,502 | Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs | 2015 | VLDB |
| 2 | 5,486 | Diversified Top-k Subgraph Querying in a Large Graph | 2016 | SIGMOD |
| 3 | 10,289 | A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis] | 2026 | SIGMOD |
| 4 | 8,899 | Subgraph Matching: A New Decomposition Based Approach | 2025 | VLDB |
| 5 | 6,245 | Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding | 2024 | VLDB |
| 6 | 440 | Efficient Subgraph Matching on Billion Node Graphs | 2012 | VLDB |
| 7 | 3,771 | Multi-Query Optimization for Subgraph Isomorphism Search | 2017 | VLDB |
| 8 | 952 | Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together | 2019 | SIGMOD |
| 9 | 4,099 | A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction | 2024 | SIGMOD |
| 10 | 1,907 | Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching | 2021 | SIGMOD |