Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data

Summary: Generalized tree pattern queries (GTPQs) for graph-structured data, enabling full propositional logic of structural constraints. Efficient evaluation with a compact graph representation, join pruning, and a 3-hop reachability index; experiments show speedups. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10515
Venue: VLDB
Year: 2012
Pagerank: 4.7041255e-05
Overall Rank: 7,584 | 47.25%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,762	Optimal Enumeration: Efficient Top-k Tree Matching	2015	VLDB	4.6583829e-05
9,890	The (Almost) Complete Guide to Tree Pattern Containment	2015	PODS	4.2617199e-05

Outgoing Citations (Sorted by Pagerank)

Showing 18 of 18 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
98	XMark: A Benchmark for XML Data Management	2002	VLDB	0.00050023808
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
279	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00029113513
425	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00023598882
461	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022499343
919	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00015343179
1,235	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00013120483
1,414	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00012118275
2,168	ViST: A Dynamic Index Method for Querying XML Data by Tree Structures	2003	SIGMOD	9.3848723e-05
2,956	Efficient Algorithms for Minimizing Tree Pattern Queries	2002	SIGMOD	7.821865e-05
3,610	From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery	2003	VLDB	6.9196208e-05
4,354	From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching	2005	VLDB	6.262393e-05
4,364	Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents	2006	VLDB	6.2546168e-05
5,574	Efficient Processing of XML Twig Queries with OR-Predicates	2004	SIGMOD	5.4268403e-05
5,948	Minimization of Tree Pattern Queries with Constraints	2008	SIGMOD	5.2602218e-05
7,367	Hash-based Subgraph Query Processing Method for Graph-structured XML Documents	2008	VLDB	4.7514687e-05
12,156	Comments on “Stack-based Algorithms for Pattern Matching on DAGs”	2012	VLDB	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,014	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	4.1945683e-05
5,948	Minimization of Tree Pattern Queries with Constraints	2008	SIGMOD	5.2602218e-05
3,117	Processing Queries on Tree-Structured Data Efficiently	2006	PODS	7.5407318e-05
1,663	Conjunctive Queries over Trees	2004	PODS	0.00010977096
4,058	Efficient Evaluation and Approximation of Well-designed Pattern Trees	2015	PODS	6.4866036e-05
4,251	Static Analysis and Optimization of Semantic Web Queries	2012	PODS	6.3235328e-05
4,625	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.0406081e-05
2,584	Expressive and efficient pattern languages for tree-structured data (extended abstract)	2000	PODS	8.4948053e-05
3,610	From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery	2003	VLDB	6.9196208e-05
9,890	The (Almost) Complete Guide to Tree Pattern Containment	2015	PODS	4.2617199e-05