Similarity Evaluation on Tree-structured Data

Summary: Tree edit distance is costly; encode trees as approximate numeric vectors; L1 distance lower-bounds tree distance in O(|T1|+|T2|). A filter-and-refine framework uses the embedding to speed up similarity search on large tree-structured datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3682
Venue: SIGMOD
Year: 2005
Pagerank: 7.3927291e-05
Overall Rank: 3,199 | 77.75%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
951	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.00015106325
3,301	RTED: A Robust Algorithm for the Tree Edit Distance	2012	VLDB	7.2515266e-05
5,615	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD	5.4101086e-05
6,241	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB	5.1411469e-05
6,732	An Incrementally Maintainable Index for Approximate Lookups in Hierarchical Data	2006	VLDB	4.9477058e-05
7,215	SyncSignature: A Simple, Efficient, Parallelizable Framework for Tree Similarity Joins	2023	VLDB	4.7985991e-05
8,511	JEDI: These aren't the JSON documents you're looking for...	2022	SIGMOD	4.495029e-05
9,439	On-the-Fly Token Similarity Joins in Relational Databases	2014	SIGMOD	4.3423824e-05
10,706	Extensible and Robust Evaluation of Similarity Queries	2025	VLDB	4.1945683e-05
11,013	X-TED: Massive Parallelization of Tree Edit Distance	2024	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0032169493
79	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056242144
125	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00044847972
802	Optimal Multi-Step k-Nearest Neighbor Search	1998	SIGMOD	0.00016502317
1,925	The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation	2000	VLDB	0.00010073407
2,784	Approximate XML Joins	2002	SIGMOD	8.128931e-05
5,273	Correlating XML Data Streams Using Tree-Edit Distance Embeddings	2003	PODS	5.5913399e-05
6,778	A New Method for Similarity Indexing of Market Basket Data	1999	SIGMOD	4.9284526e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,357	The Power of Two Min-Hashes for Similarity Search among Hierarchical Data Objects	2008	PODS	4.1945683e-05
997	Similarity-Based Queries for Time Series Data	1997	SIGMOD	0.00014739219
7,654	LiteHST: A Tree Embedding based Method for Similarity Search	2023	SIGMOD	4.687476e-05
8,647	A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases	2006	SIGMOD	4.4768766e-05
2,376	Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance	2010	SIGMOD	8.9424361e-05
7,109	Efficient Similarity Join and Search on Multi-Attribute Data	2015	SIGMOD	4.8292998e-05
5,273	Correlating XML Data Streams Using Tree-Edit Distance Embeddings	2003	PODS	5.5913399e-05
5,615	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD	5.4101086e-05
6,241	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB	5.1411469e-05
6,807	Indexing for Subtree Similarity-Search using Edit Distance	2013	SIGMOD	4.9217776e-05