LCS-TRIM: Dynamic Programming Meets XML Indexing and Querying

Summary: Dynamic-programming-driven LCS variant for tree-structured data; sequential encoding of queries and data; early pruning with a lightweight index to shrink search space. Supports constrained and approximate matches; achieves 2-3 orders of magnitude faster query times on real XML workloads and scales on multi-core servers. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9806
Venue: VLDB
Year: 2007
Pagerank: 5.4278338e-05
Overall Rank: 8,422 | 42.22%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Shirish Tatikonda (Ohio State University)
2. Srinivasan Parthasarathy (Ohio State University)
3. Matthew Goyder (Ohio State University)

BibTeX Citation

@article{tatikonda_vldb07,
        title = {{LCS-TRIM: Dynamic Programming Meets XML Indexing and Querying}},
        author = {Tatikonda, Shirish and Parthasarathy, Srinivasan and Goyder, Matthew},
        journal = {PVLDB},
        series = {{VLDB} '07},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,006	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.00012699518
7,710	Mining Tree-Structured Data on Multicore Systems	2009	VLDB	5.5618769e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
48	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB	0.00044033592
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
341	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00020704572
430	A Fast Index for Semistructured Data	2001	VLDB	0.00018600166
718	Covering Indexes for Branching Path Queries	2002	SIGMOD	0.00014642961
893	Accelerating XPath Location Steps	2002	SIGMOD	0.00013374715
897	APEX: An Adaptive Path Index for XML Data	2002	SIGMOD	0.00013339862
1,523	Efficient Structural Joins on Indexed XML Documents	2002	VLDB	0.00010502089
1,849	ViST: A Dynamic Index Method for Querying XML Data by Tree Structures	2003	SIGMOD	9.6191884e-05
2,694	Holistic Twig Joins on Indexed XML Documents	2003	VLDB	8.2469414e-05
9,338	Tree-Pattern Queries on a Lightweight XML Processor	2005	VLDB	5.2874872e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,332	Correlating XML Data Streams Using Tree-Edit Distance Embeddings	2003	PODS
2	1,068	Minimization of Tree Pattern Queries	2001	SIGMOD
3	3,814	Mixed Mode XML Query Processing	2003	VLDB
4	2,625	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB
5	3,180	Approximate XML Query Answers	2004	SIGMOD
6	6,832	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD
7	9,730	Fast Optimal Twig Joins	2010	VLDB
8	5,298	Efficient Processing of XML Twig Queries with OR-Predicates	2004	SIGMOD
9	12,774	XSeq: An Indexing Infrastructure for Tree Pattern Queries	2004	SIGMOD
10	1,849	ViST: A Dynamic Index Method for Querying XML Data by Tree Structures	2003	SIGMOD