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 |
|---|---|---|---|---|
| 916 | Distance-Join: Pattern Match Query In a Large Graph Database | 2009 | VLDB | 0.00015326675 |
| 3,330 | Schemaless and Structureless Graph Querying | 2014 | VLDB | 7.2116683e-05 |
| 4,748 | Diversified Top-k Graph Pattern Matching | 2013 | VLDB | 5.9432853e-05 |
| 7,761 | Optimal Enumeration: Efficient Top-k Tree Matching | 2015 | VLDB | 4.6543114e-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 |
|---|---|---|---|---|
| 8 | Optimal Aggregation Algorithms for Middleware [Extended Abstract] | 2001 | PODS | 0.0015436578 |
| 11 | Implementing Data Cubes Efficiently | 1996 | SIGMOD | 0.0011695087 |
| 53 | DISCOVER: Keyword Search in Relational Databases | 2002 | VLDB | 0.00065993143 |
| 73 | XRANK: Ranked Keyword Search over XML Documents | 2003 | SIGMOD | 0.0005840064 |
| 239 | Holistic Twig Joins: Optimal XML Pattern Matching | 2002 | SIGMOD | 0.00031581944 |
| 255 | Efficient Management of Transitive Relationships in Large Data and Knowledge Bases | 1989 | SIGMOD | 0.00030342925 |
| 302 | BLINKS: Ranked Keyword Searches on Graphs | 2007 | SIGMOD | 0.00028343691 |
| 337 | Bidirectional Expansion For Keyword Search on Graph Databases | 2005 | VLDB | 0.00027002505 |
| 436 | XSEarch: A Semantic Search Engine for XML | 2003 | VLDB | 0.00023264416 |
| 7,236 | Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs | 2007 | VLDB | 4.7877732e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 9,594 | Fast Optimal Twig Joins | 2010 | VLDB | 4.3155661e-05 |
| 239 | Holistic Twig Joins: Optimal XML Pattern Matching | 2002 | SIGMOD | 0.00031581944 |
| 916 | Distance-Join: Pattern Match Query In a Large Graph Database | 2009 | VLDB | 0.00015326675 |
| 11,569 | Simulation-based Approximate Graph Pattern Matching | 2020 | SIGMOD | 4.1905499e-05 |
| 1,419 | Graph Pattern Matching: From Intractable to Polynomial Time | 2010 | VLDB | 0.00012072488 |
| 4,748 | Diversified Top-k Graph Pattern Matching | 2013 | VLDB | 5.9432853e-05 |
| 11,563 | Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees | 2020 | SIGMOD | 4.1905499e-05 |
| 2,402 | TreeSpan: Efficiently Computing Similarity All-Matching | 2012 | SIGMOD | 8.87387e-05 |
| 12,164 | Comments on “Stack-based Algorithms for Pattern Matching on DAGs” | 2012 | VLDB | 4.1905499e-05 |
| 7,761 | Optimal Enumeration: Efficient Top-k Tree Matching | 2015 | VLDB | 4.6543114e-05 |