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.640323e-05
Overall Rank: 3,108 | 79.11%
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.00011898162
3,231	RTED: A Robust Algorithm for the Tree Edit Distance	2012	VLDB	7.5038443e-05
6,137	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB	5.8736299e-05
6,973	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD	5.6304028e-05
7,619	SyncSignature: A Simple, Efficient, Parallelizable Framework for Tree Similarity Joins	2023	VLDB	5.4832111e-05
7,699	An Incrementally Maintainable Index for Approximate Lookups in Hierarchical Data	2006	VLDB	5.4751052e-05
8,676	JEDI: These aren't the JSON documents you're looking for...	2022	SIGMOD	5.2910615e-05
9,788	On-the-Fly Token Similarity Joins in Relational Databases	2014	SIGMOD	5.1272311e-05
11,339	Extensible and Robust Evaluation of Similarity Queries	2025	VLDB	4.9793485e-05
11,560	X-TED: Massive Parallelization of Tree Edit Distance	2024	VLDB	4.9793485e-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.001992968
45	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.0004503446
108	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.0003305531
826	Optimal Multi-Step k-Nearest Neighbor Search	1998	SIGMOD	0.0001363793
1,793	The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation	2000	VLDB	9.6235776e-05
2,747	Approximate XML Joins	2002	SIGMOD	8.0614566e-05
5,461	Correlating XML Data Streams Using Tree-Edit Distance Embeddings	2003	PODS	6.1221773e-05
7,023	A New Method for Similarity Indexing of Market Basket Data	1999	SIGMOD	5.6186604e-05

Semantically Similar Papers

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