SyncSignature: A Simple, Efficient, Parallelizable Framework for Tree Similarity Joins

Summary: SyncSignature: first fully parallelizable framework for tree similarity joins under edit distance using implicitly-synchronized signature generation to enable hash-join candidate generation. Beats prior work in parallel settings and on large trees (single-thread too); includes theoretical analysis of signature schemes. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13353
Venue: VLDB
Year: 2023
Pagerank: 5.6090634e-05
Overall Rank: 7,476 | 48.71%
DOI: 10.14778/3565816.3565833

Incoming Non-self Citations Over Time

Authors

1. Nikolai Karpov (Indiana University)
2. Qin Zhang (Indiana University)

BibTeX Citation

@article{karpov_vldb23,
        title = {{SyncSignature: A Simple, Efficient, Parallelizable Framework for Tree Similarity Joins}},
        author = {Karpov, Nikolai and Zhang, Qin},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {2},
        pages = {330--342},
        doi = {10.14778/3565816.3565833},
        url = {https://doi.org/10.14778/3565816.3565833},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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 16 of 16 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
21	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00056760516
107	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00033511706
169	Efficient Exact Set-Similarity Joins	2006	VLDB	0.0002743469
356	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD	0.00020303289
769	A Comparison of Join Algorithms for Log Processing in MapReduce	2010	SIGMOD	0.00014166872
911	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013283031
975	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012870645
1,886	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	9.5358137e-05
2,699	Approximate XML Joins	2002	SIGMOD	8.2433011e-05
3,047	Similarity Evaluation on Tree-structured Data	2005	SIGMOD	7.8155543e-05
3,165	RTED: A Robust Algorithm for the Tree Edit Distance	2012	VLDB	7.6759052e-05
3,193	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	7.649474e-05
3,731	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB	7.1663952e-05
4,566	Approximate Matching of Hierarchical Data Using pq-Grams	2005	VLDB	6.6275286e-05
6,014	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB	6.0084322e-05
6,446	Exact Single-Source SimRank Computation on Large Graphs	2020	SIGMOD	5.8763523e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,832	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD
2	6,716	SigMatch: Fast and Scalable Multi-Pattern Matching	2010	VLDB
3	9,702	Towards a Unified Framework for String Similarity Joins	2019	VLDB
4	911	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB
5	3,731	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB
6	5,088	String Similarity Measures and Joins with Synonyms	2013	SIGMOD
7	11,447	A Two-Level Signature Scheme for Stable Set Similarity Joins	2023	VLDB
8	3,193	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD
9	3,047	Similarity Evaluation on Tree-structured Data	2005	SIGMOD
10	6,014	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB