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: 9615
Venue: VLDB
Year: 2007
Pagerank: 4.527474e-05
Overall Rank: 8,397 | 41.59%
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
1,561	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.00011358946
7,790	Mining Tree-Structured Data on Multicore Systems	2009	VLDB	4.650649e-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
61	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB	0.00064329285
193	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00035610321
240	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00031603463
391	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00024564567
415	A Fast Index for Semistructured Data	2001	VLDB	0.00023814619
817	Covering Indexes for Branching Path Queries	2002	SIGMOD	0.00016352717
869	APEX: An Adaptive Path Index for XML Data	2002	SIGMOD	0.00015788339
1,027	Accelerating XPath Location Steps	2002	SIGMOD	0.0001458865
1,733	Efficient Structural Joins on Indexed XML Documents	2002	VLDB	0.00010724888
2,168	ViST: A Dynamic Index Method for Querying XML Data by Tree Structures	2003	SIGMOD	9.3848723e-05
3,120	Holistic Twig Joins on Indexed XML Documents	2003	VLDB	7.5295938e-05
9,178	Tree-Pattern Queries on a Lightweight XML Processor	2005	VLDB	4.3828426e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,273	Correlating XML Data Streams Using Tree-Edit Distance Embeddings	2003	PODS	5.5913399e-05
1,235	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00013120483
4,207	Mixed Mode XML Query Processing	2003	VLDB	6.359465e-05
2,855	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB	8.0059865e-05
3,419	Approximate XML Query Answers	2004	SIGMOD	7.1173416e-05
5,615	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD	5.4101086e-05
9,594	Fast Optimal Twig Joins	2010	VLDB	4.3197044e-05
5,574	Efficient Processing of XML Twig Queries with OR-Predicates	2004	SIGMOD	5.4268403e-05
12,581	XSeq: An Indexing Infrastructure for Tree Pattern Queries	2004	SIGMOD	4.1945683e-05
2,168	ViST: A Dynamic Index Method for Querying XML Data by Tree Structures	2003	SIGMOD	9.3848723e-05