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: h29073f3b074f5577
Venue: SIGMOD
Year: 2005
Pagerank: 7.6367063e-05
Overall Rank: 3,110 | 79.10%
DOI: 10.1145/1066157.1066243

Incoming Non-self Citations Over Time

Authors

1. Rui Yang (National University of Singapore)
2. Panos Kalnis (National University of Singapore)
3. Anthony K. H. Tung (National University of Singapore)

BibTeX Citation

@inproceedings{yang_sigmod05,
        title = {{Similarity Evaluation on Tree-structured Data}},
        author = {Yang, Rui and Kalnis, Panos and Tung, Anthony K. H.},
        series = {{SIGMOD} '05},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1066157.1066243},
        url = {https://dl.acm.org/doi/10.1145/1066157.1066243},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,133	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.00011892544
3,234	RTED: A Robust Algorithm for the Tree Edit Distance	2012	VLDB	7.500292e-05
6,140	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB	5.8708494e-05
6,974	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD	5.6277375e-05
7,625	SyncSignature: A Simple, Efficient, Parallelizable Framework for Tree Similarity Joins	2023	VLDB	5.4806154e-05
7,705	An Incrementally Maintainable Index for Approximate Lookups in Hierarchical Data	2006	VLDB	5.472514e-05
8,684	JEDI: These aren't the JSON documents you're looking for...	2022	SIGMOD	5.2885567e-05
9,794	On-the-Fly Token Similarity Joins in Relational Databases	2014	SIGMOD	5.1248055e-05
11,347	Extensible and Robust Evaluation of Similarity Queries	2025	VLDB	4.9769913e-05
11,566	X-TED: Massive Parallelization of Tree Edit Distance	2024	VLDB	4.9769913e-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.0019923528
45	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00045027197
108	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00033040246
826	Optimal Multi-Step k-Nearest Neighbor Search	1998	SIGMOD	0.000136317
1,793	The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation	2000	VLDB	9.6212318e-05
2,747	Approximate XML Joins	2002	SIGMOD	8.0576613e-05
5,465	Correlating XML Data Streams Using Tree-Edit Distance Embeddings	2003	PODS	6.1192791e-05
7,024	A New Method for Similarity Indexing of Market Basket Data	1999	SIGMOD	5.6160027e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	829	Similarity-Based Queries for Time Series Data	1997	SIGMOD
2	12,846	The Power of Two Min-Hashes for Similarity Search among Hierarchical Data Objects	2008	PODS
3	7,397	LiteHST: A Tree Embedding based Method for Similarity Search	2023	SIGMOD
4	8,827	A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases	2006	SIGMOD
5	2,074	Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance	2010	SIGMOD
6	7,032	Efficient Similarity Join and Search on Multi-Attribute Data	2015	SIGMOD
7	5,465	Correlating XML Data Streams Using Tree-Edit Distance Embeddings	2003	PODS
8	6,974	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD
9	6,140	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB
10	7,088	Indexing for Subtree Similarity-Search using Edit Distance	2013	SIGMOD