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: 3683
Venue: SIGMOD
Year: 2005
Pagerank: 7.3855924e-05
Overall Rank: 3,206 | 77.72%
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
949	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.0001510288
3,302	RTED: A Robust Algorithm for the Tree Edit Distance	2012	VLDB	7.2445358e-05
5,624	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD	5.4049016e-05
6,240	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB	5.1362097e-05
6,734	An Incrementally Maintainable Index for Approximate Lookups in Hierarchical Data	2006	VLDB	4.9434384e-05
7,215	SyncSignature: A Simple, Efficient, Parallelizable Framework for Tree Similarity Joins	2023	VLDB	4.7939964e-05
8,508	JEDI: These aren't the JSON documents you're looking for...	2022	SIGMOD	4.4907199e-05
9,444	On-the-Fly Token Similarity Joins in Relational Databases	2014	SIGMOD	4.3382418e-05
10,714	Extensible and Robust Evaluation of Similarity Queries	2025	VLDB	4.1905499e-05
11,016	X-TED: Massive Parallelization of Tree Edit Distance	2024	VLDB	4.1905499e-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.0032118946
78	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056385781
125	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00044946098
798	Optimal Multi-Step k-Nearest Neighbor Search	1998	SIGMOD	0.00016484637
1,923	The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation	2000	VLDB	0.00010079134
2,786	Approximate XML Joins	2002	SIGMOD	8.1223413e-05
5,277	Correlating XML Data Streams Using Tree-Edit Distance Embeddings	2003	PODS	5.5859557e-05
6,778	A New Method for Similarity Indexing of Market Basket Data	1999	SIGMOD	4.9237313e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,365	The Power of Two Min-Hashes for Similarity Search among Hierarchical Data Objects	2008	PODS	4.1905499e-05
999	Similarity-Based Queries for Time Series Data	1997	SIGMOD	0.00014726031
7,654	LiteHST: A Tree Embedding based Method for Similarity Search	2023	SIGMOD	4.6831082e-05
8,645	A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases	2006	SIGMOD	4.4725847e-05
2,387	Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance	2010	SIGMOD	8.9075095e-05
7,106	Efficient Similarity Join and Search on Multi-Attribute Data	2015	SIGMOD	4.8250163e-05
5,277	Correlating XML Data Streams Using Tree-Edit Distance Embeddings	2003	PODS	5.5859557e-05
5,624	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD	5.4049016e-05
6,240	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB	5.1362097e-05
6,805	Indexing for Subtree Similarity-Search using Edit Distance	2013	SIGMOD	4.9170518e-05