Efficient Indexing and Querying over Syntactically Annotated Trees

Summary: Indexing over unique subtrees of syntactically parsed trees; root-split coding stores partial subtree structure to shrink index size. Experiments show 50-80% index-size reduction versus interval coding and an order-of-magnitude speedup for tree-pattern queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10556
Venue: VLDB
Year: 2012
Pagerank: 5.6029996e-05
Overall Rank: 7,524 | 48.38%
DOI: 10.14778/2350229.2350256

Incoming Non-self Citations Over Time

Authors

1. Pirooz Chubak (University of Alberta)
2. Davood Rafiei (University of Alberta)

BibTeX Citation

@article{chubak_vldb12,
        title = {{Efficient Indexing and Querying over Syntactically Annotated Trees}},
        author = {Chubak, Pirooz and Rafiei, Davood},
        journal = {PVLDB},
        series = {{VLDB} '12},
        volume = {5},
        number = {11},
        pages = {1316--1327},
        doi = {10.14778/2350229.2350256},
        url = {https://doi.org/10.14778/2350229.2350256},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,130	Natural Language Data Management and Interfaces: Recent Development and Open Challenges	2017	SIGMOD	6.354484e-05
11,961	Scalable Semantic Querying of Text	2018	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
163	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00027839792
175	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00027226333
177	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00027100548
187	Algorithmics and Applications of Tree and Graph Searching	2002	PODS	0.00026138589

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,107	Processing Queries on Tree-Structured Data Efficiently	2006	PODS
2	7,896	Optimizing Index for Taxonomy Keyword Search	2012	SIGMOD
3	8,422	LCS-TRIM: Dynamic Programming Meets XML Indexing and Querying	2007	VLDB
4	8,329	Understanding Queries in a Search Database System	2010	PODS
5	6,150	Flexible and Efficient XML Search with Complex Full-Text Predicates	2006	SIGMOD
6	6,014	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB
7	6,947	Indexing for Subtree Similarity-Search using Edit Distance	2013	SIGMOD
8	3,047	Similarity Evaluation on Tree-structured Data	2005	SIGMOD
9	3,742	RE-Tree: An Efficient Index Structure for Regular Expressions	2002	VLDB
10	6,832	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD