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: 9616
Venue: VLDB
Year: 2007
Pagerank: 4.5282277e-05
Overall Rank: 8,374 | 41.81%
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,522	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.0001152219
7,771	Mining Tree-Structured Data on Multicore Systems	2009	VLDB	4.6512834e-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.00064281097
193	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00035591171
239	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00031581944
392	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00024546229
414	A Fast Index for Semistructured Data	2001	VLDB	0.00023801668
812	Covering Indexes for Branching Path Queries	2002	SIGMOD	0.00016343476
864	APEX: An Adaptive Path Index for XML Data	2002	SIGMOD	0.00015781693
1,028	Accelerating XPath Location Steps	2002	SIGMOD	0.00014578947
1,732	Efficient Structural Joins on Indexed XML Documents	2002	VLDB	0.00010716665
2,174	ViST: A Dynamic Index Method for Querying XML Data by Tree Structures	2003	SIGMOD	9.3762595e-05
3,125	Holistic Twig Joins on Indexed XML Documents	2003	VLDB	7.5228453e-05
9,182	Tree-Pattern Queries on a Lightweight XML Processor	2005	VLDB	4.3788525e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,277	Correlating XML Data Streams Using Tree-Edit Distance Embeddings	2003	PODS	5.5859557e-05
1,236	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00013107769
4,205	Mixed Mode XML Query Processing	2003	VLDB	6.354571e-05
2,862	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB	7.9982917e-05
3,421	Approximate XML Query Answers	2004	SIGMOD	7.1107127e-05
5,624	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD	5.4049016e-05
9,594	Fast Optimal Twig Joins	2010	VLDB	4.3155661e-05
5,580	Efficient Processing of XML Twig Queries with OR-Predicates	2004	SIGMOD	5.4216254e-05
2,174	ViST: A Dynamic Index Method for Querying XML Data by Tree Structures	2003	SIGMOD	9.3762595e-05
12,590	XSeq: An Indexing Infrastructure for Tree Pattern Queries	2004	SIGMOD	4.1905499e-05