Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs
Summary: DP-B and DP-P: two algorithms for exact top-ranked twig-pattern matching on large graphs. DP-B runs in time and space linear in data size even with exponential matches; DP-P is often sublinear in practice, making these the first guarantees of this kind, with experimental validation. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Gang Gou
- 2. Rada Chirkova
Incoming Citations (Sorted by Pagerank)
Showing 4 of 4 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 919 | Distance-Join: Pattern Match Query In a Large Graph Database | 2009 | VLDB | 0.00015343179 |
| 3,320 | Schemaless and Structureless Graph Querying | 2014 | VLDB | 7.2249102e-05 |
| 4,807 | Diversified Top-k Graph Pattern Matching | 2013 | VLDB | 5.9092289e-05 |
| 7,762 | Optimal Enumeration: Efficient Top-k Tree Matching | 2015 | VLDB | 4.6583829e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 10 of 10 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 7 | Optimal Aggregation Algorithms for Middleware [Extended Abstract] | 2001 | PODS | 0.0015496097 |
| 11 | Implementing Data Cubes Efficiently | 1996 | SIGMOD | 0.0011708144 |
| 54 | DISCOVER: Keyword Search in Relational Databases | 2002 | VLDB | 0.00066047203 |
| 73 | XRANK: Ranked Keyword Search over XML Documents | 2003 | SIGMOD | 0.00058443993 |
| 240 | Holistic Twig Joins: Optimal XML Pattern Matching | 2002 | SIGMOD | 0.00031603463 |
| 246 | Efficient Management of Transitive Relationships in Large Data and Knowledge Bases | 1989 | SIGMOD | 0.00030949575 |
| 301 | BLINKS: Ranked Keyword Searches on Graphs | 2007 | SIGMOD | 0.00028370644 |
| 336 | Bidirectional Expansion For Keyword Search on Graph Databases | 2005 | VLDB | 0.00027020919 |
| 434 | XSEarch: A Semantic Search Engine for XML | 2003 | VLDB | 0.0002328559 |
| 7,240 | Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs | 2007 | VLDB | 4.792172e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 9,594 | Fast Optimal Twig Joins | 2010 | VLDB | 4.3197044e-05 |
| 240 | Holistic Twig Joins: Optimal XML Pattern Matching | 2002 | SIGMOD | 0.00031603463 |
| 919 | Distance-Join: Pattern Match Query In a Large Graph Database | 2009 | VLDB | 0.00015343179 |
| 11,565 | Simulation-based Approximate Graph Pattern Matching | 2020 | SIGMOD | 4.1945683e-05 |
| 1,414 | Graph Pattern Matching: From Intractable to Polynomial Time | 2010 | VLDB | 0.00012118275 |
| 4,807 | Diversified Top-k Graph Pattern Matching | 2013 | VLDB | 5.9092289e-05 |
| 11,559 | Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees | 2020 | SIGMOD | 4.1945683e-05 |
| 2,409 | TreeSpan: Efficiently Computing Similarity All-Matching | 2012 | SIGMOD | 8.8776858e-05 |
| 12,156 | Comments on “Stack-based Algorithms for Pattern Matching on DAGs” | 2012 | VLDB | 4.1945683e-05 |
| 7,762 | Optimal Enumeration: Efficient Top-k Tree Matching | 2015 | VLDB | 4.6583829e-05 |