Database Paper Browser

Back to papers

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
13165
Venue
VLDB
Year
2023
Pagerank
4.7985991e-05
Overall Rank
7,215 | 49.81%
DOI
10.14778/3565816.3565833

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank Citing Paper Year Venue Pagerank
10,706 Extensible and Robust Evaluation of Similarity Queries 2025 VLDB 4.1945683e-05
11,013 X-TED: Massive Parallelization of Tree Edit Distance 2024 VLDB 4.1945683e-05
Previous Page 1 / 1 Next

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
34 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00076637636
125 Approximate String Joins in a Database (Almost) for Free 2001 VLDB 0.00044847972
266 Efficient Exact Set-Similarity Joins 2006 VLDB 0.00029718727
447 Efficient Parallel Set-Similarity Joins Using MapReduce 2010 SIGMOD 0.00022900171
960 A Comparison of Join Algorithms for Log Processing in MapReduce 2010 SIGMOD 0.00015012242
1,234 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB 0.00013122499
1,396 Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search 2012 SIGMOD 0.00012204748
2,592 Pass-Join: A Partition-based Method for Similarity Joins 2012 VLDB 8.4795761e-05
2,784 Approximate XML Joins 2002 SIGMOD 8.128931e-05
3,199 Similarity Evaluation on Tree-structured Data 2005 SIGMOD 7.3927291e-05
3,301 RTED: A Robust Algorithm for the Tree Edit Distance 2012 VLDB 7.2515266e-05
3,774 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 6.7757301e-05
4,216 Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints 2010 VLDB 6.3521675e-05
4,406 Approximate Matching of Hierarchical Data Using pq-Grams 2005 VLDB 6.2141638e-05
6,241 Scaling Similarity Joins over Tree-Structured Data 2015 VLDB 5.1411469e-05
7,590 Exact Single-Source SimRank Computation on Large Graphs 2020 SIGMOD 4.7029681e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
6,807 Indexing for Subtree Similarity-Search using Edit Distance 2013 SIGMOD 4.9217776e-05
6,351 SigMatch: Fast and Scalable Multi-Pattern Matching 2010 VLDB 5.1005697e-05
9,563 Towards a Unified Framework for String Similarity Joins 2019 VLDB 4.3254416e-05
1,234 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB 0.00013122499
4,216 Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints 2010 VLDB 6.3521675e-05
5,151 String Similarity Measures and Joins with Synonyms 2013 SIGMOD 5.6609851e-05
11,247 A Two-Level Signature Scheme for Stable Set Similarity Joins 2023 VLDB 4.1945683e-05
3,774 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 6.7757301e-05
3,199 Similarity Evaluation on Tree-structured Data 2005 SIGMOD 7.3927291e-05
6,241 Scaling Similarity Joins over Tree-Structured Data 2015 VLDB 5.1411469e-05