Indexing for Subtree Similarity-Search using Edit Distance

Summary: First index structure for subtree similarity search under tree edit distance with a unit-cost model. Enables pruning-based, fast queries over large T, avoiding full-tree traversal; experiments show large speedups over prior traversal-based approaches. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4711
Venue: SIGMOD
Year: 2013
Pagerank: 5.7309645e-05
Overall Rank: 6,947 | 52.34%
DOI: 10.1145/2463676.2463716

Incoming Non-self Citations Over Time

Authors

1. Sara Cohen (Hebrew University)

BibTeX Citation

@inproceedings{cohen_sigmod13,
        title = {{Indexing for Subtree Similarity-Search using Edit Distance}},
        author = {Cohen, Sara},
        series = {{SIGMOD} '13},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2463676.2463716},
        url = {https://dl.acm.org/doi/10.1145/2463676.2463716},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
77	XRANK: Ranked Keyword Search over XML Documents	2003	SIGMOD	0.00037048607
79	XMark: A Benchmark for XML Data Management	2002	VLDB	0.00036555628
3,165	RTED: A Robust Algorithm for the Tree Edit Distance	2012	VLDB	7.6759052e-05
5,332	Correlating XML Data Streams Using Tree-Edit Distance Embeddings	2003	PODS	6.2626822e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,906	Efficient Similarity Join and Search on Multi-Attribute Data	2015	SIGMOD
2	1,084	A Data-adaptive and Dynamic Segmentation Index for Whole Matching on Time Series	2013	VLDB
3	7,524	Efficient Indexing and Querying over Syntactically Annotated Trees	2012	VLDB
4	727	Graph Indexing: Tree + Delta >= Graph	2007	VLDB
5	56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB
6	7,376	LiteHST: A Tree Embedding based Method for Similarity Search	2023	SIGMOD
7	2,036	Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance	2010	SIGMOD
8	6,014	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB
9	6,832	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD
10	3,047	Similarity Evaluation on Tree-structured Data	2005	SIGMOD