SyncSignature: A Simple, Efficient, Parallelizable Framework for Tree Similarity Joins
SyncSignature: A Simple, Efficient, Parallelizable Framework for Tree Similarity Joins
复制标题
DOI：
10.14778/3565816.3565833
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
Nikolai Karpov;Qin Zhang
中科院分区：
文献类型：
--
作者：
Nikolai Karpov;Qin Zhang
本文介绍了SyncSignature，第一个完全并行化的算法框架下的编辑距离树相似连接。SyncSignature使用隐式同步签名生成方案，通过散列连接实现高效且可并行的候选生成过程。我们的实验上的大型现实世界的数据集表明，在同步签名框架下提出的算法显着优于国家的最先进的算法在并行计算环境。对于具有大树的数据集，它们在集中式/单线程计算环境中也超过了最先进的算法。为了补充和指导实验研究，我们还提供了一个全面的理论分析，所有提出的签名生成方案。
This paper introduces SyncSignature, the first fully parallelizable algorithmic framework for tree similarity joins under edit distance. SyncSignature makes use of implicit-synchronized signature generation schemes, which allow for an efficient and parallelizable candidate-generation procedure via hash join. Our experiments on large real-world datasets show that the proposed algorithms under the SyncSignature framework significantly outperform the state-of-the-art algorithm in the parallel computation environment. For datasets with big trees, they also exceed the state-of-the-art algorithms by a notable margin in the centralized/single-thread computation environment. To complement and guide the experimental study, we also provide a thorough theoretical analysis for all proposed signature generation schemes.