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.6114853e-05
Overall Rank: 3,118 | 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,136	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.00011857445
3,250	RTED: A Robust Algorithm for the Tree Edit Distance	2012	VLDB	7.4754914e-05
6,160	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB	5.8514368e-05
6,997	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD	5.6091287e-05
7,640	SyncSignature: A Simple, Efficient, Parallelizable Framework for Tree Similarity Joins	2023	VLDB	5.4624931e-05
7,717	An Incrementally Maintainable Index for Approximate Lookups in Hierarchical Data	2006	VLDB	5.4545945e-05
8,704	JEDI: These aren't the JSON documents you're looking for...	2022	SIGMOD	5.2710695e-05
9,825	On-the-Fly Token Similarity Joins in Relational Databases	2014	SIGMOD	5.1084057e-05
11,400	Extensible and Robust Evaluation of Similarity Queries	2025	VLDB	4.9605343e-05
11,615	X-TED: Massive Parallelization of Tree Edit Distance	2024	VLDB	4.9605343e-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.0019892478
45	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00044967652
108	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00032945275
828	Optimal Multi-Step k-Nearest Neighbor Search	1998	SIGMOD	0.00013588099
1,805	The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation	2000	VLDB	9.5936926e-05
2,757	Approximate XML Joins	2002	SIGMOD	8.0313227e-05
5,481	Correlating XML Data Streams Using Tree-Edit Distance Embeddings	2003	PODS	6.0990465e-05
7,045	A New Method for Similarity Indexing of Market Basket Data	1999	SIGMOD	5.5975731e-05

Semantically Similar Papers

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