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
ha22c96d2b68515ae
Venue
SIGMOD
Year
2008
Pagerank
6.6827339e-05
Overall Rank
4,291 | 71.16%
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
783 Distance-Join: Pattern Match Query In a Large Graph Database 2009 VLDB 0.00014021799
3,979 Diversified Top-k Graph Pattern Matching 2013 VLDB 6.8802947e-05
4,466 Schemaless and Structureless Graph Querying 2014 VLDB 6.5872459e-05
7,752 Optimal Enumeration: Efficient Top-k Tree Matching 2015 VLDB 5.4595236e-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.0010679641
11 Implementing Data Cubes Efficiently 1996 SIGMOD 0.00071084324
38 DISCOVER: Keyword Search in Relational Databases 2002 VLDB 0.00047394041
81 XRANK: Ranked Keyword Search over XML Documents 2003 SIGMOD 0.00036346781
178 Holistic Twig Joins: Optimal XML Pattern Matching 2002 SIGMOD 0.00026628894
270 BLINKS: Ranked Keyword Searches on Graphs 2007 SIGMOD 0.00022599109
293 Bidirectional Expansion For Keyword Search on Graph Databases 2005 VLDB 0.00021943678
294 Efficient Management of Transitive Relationships in Large Data and Knowledge Bases 1989 SIGMOD 0.00021927874
410 XSEarch: A Semantic Search Engine for XML 2003 VLDB 0.00018778082
7,339 Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs 2007 VLDB 5.5490881e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 9,901 Fast Optimal Twig Joins 2010 VLDB
2 178 Holistic Twig Joins: Optimal XML Pattern Matching 2002 SIGMOD
3 12,065 Simulation-based Approximate Graph Pattern Matching 2020 SIGMOD
4 783 Distance-Join: Pattern Match Query In a Large Graph Database 2009 VLDB
5 1,148 Graph Pattern Matching: From Intractable to Polynomial Time 2010 VLDB
6 3,979 Diversified Top-k Graph Pattern Matching 2013 VLDB
7 12,059 Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees 2020 SIGMOD
8 2,702 TreeSpan: Efficiently Computing Similarity All-Matching 2012 SIGMOD
9 12,643 Comments on "Stack-based Algorithms for Pattern Matching on DAGs" 2012 VLDB
10 7,752 Optimal Enumeration: Efficient Top-k Tree Matching 2015 VLDB