DBScholar

Back to papers

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)

Paper ID
4079
Venue
SIGMOD
Year
2008
Pagerank
6.8233111e-05
Overall Rank
4,221 | 71.05%
DOI
10.1145/1376616.1376676

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{gou_sigmod08,
        title = {{Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs}},
        author = {Gou, Gang and Chirkova, Rada},
        series = {{SIGMOD} '08},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1376616.1376676},
        url = {https://dl.acm.org/doi/10.1145/1376616.1376676},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank Citing Paper Year Venue Pagerank
776 Distance-Join: Pattern Match Query In a Large Graph Database 2009 VLDB 0.00014110016
3,908 Diversified Top-k Graph Pattern Matching 2013 VLDB 7.0262215e-05
4,372 Schemaless and Structureless Graph Querying 2014 VLDB 6.7384384e-05
7,664 Optimal Enumeration: Efficient Top-k Tree Matching 2015 VLDB 5.5720259e-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
5 Optimal Aggregation Algorithms for Middleware [Extended Abstract] 2001 PODS 0.0010828372
11 Implementing Data Cubes Efficiently 1996 SIGMOD 0.00071822821
37 DISCOVER: Keyword Search in Relational Databases 2002 VLDB 0.00048017193
77 XRANK: Ranked Keyword Search over XML Documents 2003 SIGMOD 0.00037048607
175 Holistic Twig Joins: Optimal XML Pattern Matching 2002 SIGMOD 0.00027226333
272 BLINKS: Ranked Keyword Searches on Graphs 2007 SIGMOD 0.00022695855
282 Efficient Management of Transitive Relationships in Large Data and Knowledge Bases 1989 SIGMOD 0.0002242162
302 Bidirectional Expansion For Keyword Search on Graph Databases 2005 VLDB 0.00021963347
399 XSEarch: A Semantic Search Engine for XML 2003 VLDB 0.00019177959
7,202 Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs 2007 VLDB 5.6755422e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 9,730 Fast Optimal Twig Joins 2010 VLDB
2 175 Holistic Twig Joins: Optimal XML Pattern Matching 2002 SIGMOD
3 776 Distance-Join: Pattern Match Query In a Large Graph Database 2009 VLDB
4 11,762 Simulation-based Approximate Graph Pattern Matching 2020 SIGMOD
5 1,128 Graph Pattern Matching: From Intractable to Polynomial Time 2010 VLDB
6 3,908 Diversified Top-k Graph Pattern Matching 2013 VLDB
7 11,756 Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees 2020 SIGMOD
8 2,650 TreeSpan: Efficiently Computing Similarity All-Matching 2012 SIGMOD
9 12,352 Comments on "Stack-based Algorithms for Pattern Matching on DAGs" 2012 VLDB
10 7,664 Optimal Enumeration: Efficient Top-k Tree Matching 2015 VLDB