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: 3744
Venue: SIGMOD
Year: 2005
Pagerank: 7.8155543e-05
Overall Rank: 3,047 | 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,115	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.00012117375
3,165	RTED: A Robust Algorithm for the Tree Edit Distance	2012	VLDB	7.6759052e-05
6,014	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB	6.0084322e-05
6,832	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD	5.7596335e-05
7,476	SyncSignature: A Simple, Efficient, Parallelizable Framework for Tree Similarity Joins	2023	VLDB	5.6090634e-05
7,559	An Incrementally Maintainable Index for Approximate Lookups in Hierarchical Data	2006	VLDB	5.5985266e-05
8,508	JEDI: These aren't the JSON documents you're looking for...	2022	SIGMOD	5.4123872e-05
9,613	On-the-Fly Token Similarity Joins in Relational Databases	2014	SIGMOD	5.2447096e-05
10,951	Extensible and Robust Evaluation of Similarity Queries	2025	VLDB	5.093636e-05
11,224	X-TED: Massive Parallelization of Tree Edit Distance	2024	VLDB	5.093636e-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.0020210012
46	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00044853085
107	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00033511706
796	Optimal Multi-Step k-Nearest Neighbor Search	1998	SIGMOD	0.00013932561
1,778	The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation	2000	VLDB	9.7769047e-05
2,699	Approximate XML Joins	2002	SIGMOD	8.2433011e-05
5,332	Correlating XML Data Streams Using Tree-Edit Distance Embeddings	2003	PODS	6.2626822e-05
6,887	A New Method for Similarity Indexing of Market Basket Data	1999	SIGMOD	5.7457967e-05

Semantically Similar Papers

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