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
ha17aa5bee460364c
Venue
SIGMOD
Year
2016
Pagerank
0.00015032442
Overall Rank
658 | 95.60%
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 50 of 75 citing papers.

Rank Citing Paper Year Venue Pagerank
706 Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins 2019 VLDB 0.00014622696
952 Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together 2019 SIGMOD 0.00012878316
1,090 CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching 2019 SIGMOD 0.00012062682
1,171 In-Memory Subgraph Matching: An In-depth Study 2020 SIGMOD 0.00011677799
1,907 Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching 2021 SIGMOD 9.379165e-05
1,988 RapidMatch: A Holistic Approach to Subgraph Query Processing 2021 VLDB 9.2301018e-05
2,128 Subgraph Matching: on Compression and Computation 2018 VLDB 8.9879343e-05
2,226 TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data 2018 SIGMOD 8.7971869e-05
2,478 GPU-Accelerated Subgraph Enumeration on Partitioned Graphs 2020 SIGMOD 8.3890338e-05
2,635 Neural Subgraph Counting with Wasserstein Estimator 2022 SIGMOD 8.1795762e-05
3,020 Efficient GPU-Accelerated Subgraph Matching 2023 SIGMOD 7.7267183e-05
3,105 A Learned Sketch for Subgraph Counting 2021 SIGMOD 7.6278115e-05
3,107 GuP: Fast Subgraph Matching by Guard-based Pruning 2023 SIGMOD 7.6265309e-05
3,771 Multi-Query Optimization for Subgraph Isomorphism Search 2017 VLDB 7.0132957e-05
3,885 Distributed Subgraph Matching on Timely Dataflow 2019 VLDB 6.9282318e-05
4,099 A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction 2024 SIGMOD 6.7940875e-05
4,133 HUGE: An Efficient and Scalable Subgraph Enumeration System 2021 SIGMOD 6.7738028e-05
4,370 Circinus: Fast Redundancy-Reduced Subgraph Matching 2023 SIGMOD 6.6213567e-05
4,485 Fast Continuous Subgraph Matching over Streaming Graphs via Backtracking Reduction 2023 SIGMOD 6.5644966e-05
4,801 Symmetric Continuous Subgraph Matching with Bidirectional Dynamic Programming 2021 VLDB 6.3940913e-05
5,224 Efficient Streaming Subgraph Isomorphism with Graph Neural Networks 2021 VLDB 6.2100595e-05
5,271 Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach 2024 VLDB 6.1891764e-05
5,404 RapidFlow: An Efficient Approach to Continuous Subgraph Matching 2022 VLDB 6.132986e-05
5,571 Making Graphs Compact by Lossless Contraction 2021 SIGMOD 6.0628752e-05
5,576 I/O-Efficient Butterfly Counting at Scale 2023 SIGMOD 6.062102e-05
5,676 Subgraph Matching over Graph Federation 2022 VLDB 6.0246247e-05
5,895 Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach 2025 SIGMOD 5.9387634e-05
5,995 An In-Depth Study of Continuous Subgraph Matching 2022 VLDB 5.903845e-05
6,245 Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding 2024 VLDB 5.8210521e-05
6,251 BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification 2023 VLDB 5.8179719e-05
6,272 SUFF: Accelerating Subgraph Matching with Historical Data 2023 VLDB 5.8112899e-05
6,711 BSX : Subgraph Matching with Batch Backtracking Search 2025 SIGMOD 5.6854796e-05
6,829 BOOMER: Blending Visual Formulation and Processing of P-Homomorphic Queries on Large Networks 2018 SIGMOD 5.6556888e-05
7,473 PICASSO: Exploratory Search of Connected Subgraph Substructures in Graph Databases 2017 VLDB 5.5029761e-05
7,502 Extending Graph Patterns with Conditions 2020 SIGMOD 5.4943054e-05
7,552 Fast Local Subgraph Counting 2024 VLDB 5.4802093e-05
7,649 Computing A Near-Maximum Independent Set in Linear Time by Reducing-Peeling 2017 SIGMOD 5.4598986e-05
8,187 Efficient Maximal Motif-Clique Enumeration over Large Heterogeneous Information Networks 2024 VLDB 5.3652509e-05
8,899 Subgraph Matching: A New Decomposition Based Approach 2025 VLDB 5.2401722e-05
8,920 Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds 2025 VLDB 5.2361195e-05
9,059 MatCo: Computing Match Cover of Subgraph Query over Graph Data 2025 SIGMOD 5.21427e-05
9,179 In-depth Analysis of Continuous Subgraph Matching in a Common Delta Query Compilation Framework 2024 SIGMOD 5.1992749e-05
9,601 S^3AND: Efficient Subgraph Similarity Search Under Aggregated Neighbor Difference Semantics 2025 VLDB 5.1376962e-05
9,684 gSWORD: GPU-accelerated Sampling for Subgraph Counting 2024 SIGMOD 5.1258854e-05
9,837 NeuSO: Neural Optimizer for Subgraph Queries 2026 SIGMOD 5.1064323e-05
9,881 BEE: Towards Redundancy Reduction via Block-Separator Decomposition for Subgraph Matching 2026 SIGMOD 5.1043481e-05
9,882 Accelerating Subgraph Matching through Fine-grained and Powerful Equivalences 2025 VLDB 5.1043481e-05
9,954 FusionQuery: On-demand Fusion Queries over Multi-source Heterogeneous Data 2024 VLDB 5.0910746e-05
10,101 TC-Match: Fast Time-constrained Continuous Subgraph Matching 2024 VLDB 5.068372e-05
10,168 A Modular Graph-Native Query Optimization Framework 2025 SIGMOD 5.0559291e-05
Previous Page 1 / 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