{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T03:06:09Z","timestamp":1787022369388,"version":"build-2736575974"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,10]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.14778\/3565816.3565833","type":"journal-article","created":{"date-parts":[[2022,11,23]],"date-time":"2022-11-23T19:35:16Z","timestamp":1669232116000},"page":"330-342","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["SyncSignature"],"prefix":"10.14778","volume":"16","author":[{"given":"Nikolai","family":"Karpov","sequence":"first","affiliation":[{"name":"Indiana University Bloomington"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Qin","family":"Zhang","sequence":"additional","affiliation":[{"name":"Indiana University Bloomington"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,11,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.06.002"},{"key":"e_1_2_1_2_1","volume-title":"ISAAC (Lecture Notes in Computer Science)","author":"Akutsu Tatsuya","unstructured":"Tatsuya Akutsu , Daiji Fukagawa , and Atsuhiro Takasu . 2006. Approximating Tree Edit Distance Through String Edit Distance . In ISAAC (Lecture Notes in Computer Science) , Vol. 4288 . Springer , 90--99. Tatsuya Akutsu, Daiji Fukagawa, and Atsuhiro Takasu. 2006. Approximating Tree Edit Distance Through String Edit Distance. In ISAAC (Lecture Notes in Computer Science), Vol. 4288. Springer, 90--99."},{"key":"e_1_2_1_3_1","unstructured":"Arvind Arasu Venkatesh Ganti and Raghav Kaushik. 2006. Efficient Exact Set-Similarity Joins. In PVLDB. 918--929.  Arvind Arasu Venkatesh Ganti and Raghav Kaushik. 2006. Efficient Exact Set-Similarity Joins. In PVLDB. 918--929."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083630"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1670243.1670247"},{"key":"e_1_2_1_6_1","volume-title":"Gianmarco De Francisci Morales, and Claudio Lucchese","author":"Baraglia Ranieri","year":"2010","unstructured":"Ranieri Baraglia , Gianmarco De Francisci Morales, and Claudio Lucchese . 2010 . Document Similarity Self-Join with MapReduce. In ICDM. IEEE Computer Society , 731--736. Ranieri Baraglia, Gianmarco De Francisci Morales, and Claudio Lucchese. 2010. Document Similarity Self-Join with MapReduce. In ICDM. IEEE Computer Society, 731--736."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Roberto J. Bayardo Yiming Ma and Ramakrishnan Srikant. 2007. Scaling up all pairs similarity search. In WWW. 131--140.  Roberto J. Bayardo Yiming Ma and Ramakrishnan Srikant. 2007. Scaling up all pairs similarity search. In WWW. 131--140.","DOI":"10.1145\/1242572.1242591"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Spyros Blanas Jignesh M. Patel Vuk Ercegovac Jun Rao Eugene J. Shekita and Yuanyuan Tian. 2010. A comparison of join algorithms for log processing in MaPreduce. In SIGMOD. ACM 975--986.  Spyros Blanas Jignesh M. Patel Vuk Ercegovac Jun Rao Eugene J. Shekita and Yuanyuan Tian. 2010. A comparison of join algorithms for log processing in MaPreduce. In SIGMOD. ACM 975--986.","DOI":"10.1145\/1807167.1807273"},{"key":"e_1_2_1_9_1","volume-title":"Fast similarity search in large dictionaries","author":"Bocek Thomas","unstructured":"Thomas Bocek , Ela Hunt , Burkhard Stiller , and Fabio Hecht . 2007. Fast similarity search in large dictionaries . University . Thomas Bocek, Ela Hunt, Burkhard Stiller, and Fabio Hecht. 2007. Fast similarity search in large dictionaries. University."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644015.1644017"},{"key":"e_1_2_1_11_1","unstructured":"Aristides Gionis Piotr Indyk and Rajeev Motwani. [n.d.]. Similarity Search in High Dimensions via Hashing. In VLDB. 518--529.  Aristides Gionis Piotr Indyk and Rajeev Motwani. [n.d.]. Similarity Search in High Dimensions via Hashing. In VLDB. 518--529."},{"key":"e_1_2_1_12_1","unstructured":"Luis Gravano Panagiotis G. Ipeirotis H. V. Jagadish Nick Koudas S. Muthukrishnan and Divesh Srivastava. 2001. Approximate String Joins in a Database (Almost) for Free. In PVLDB. 491--500.  Luis Gravano Panagiotis G. Ipeirotis H. V. Jagadish Nick Koudas S. Muthukrishnan and Divesh Srivastava. 2001. Approximate String Joins in a Database (Almost) for Free. In PVLDB. 491--500."},{"key":"e_1_2_1_13_1","unstructured":"Sudipto Guha H. V. Jagadish Nick Koudas Divesh Srivastava and Ting Yu. [n.d.]. Approximate XML joins. In SIGMOD. 287--298.  Sudipto Guha H. V. Jagadish Nick Koudas Divesh Srivastava and Ting Yu. [n.d.]. Approximate XML joins. In SIGMOD. 287--298."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Thomas H\u00fctter Mateusz Pawlik Robert Loschinger and Nikolaus Augsten. 2019. Effective Filters and Linear Time Verification for Tree Similarity Joins. In ICDE. 854--865.  Thomas H\u00fctter Mateusz Pawlik Robert Loschinger and Nikolaus Augsten. 2019. Effective Filters and Linear Time Verification for Tree Similarity Joins. In ICDE. 854--865.","DOI":"10.1109\/ICDE.2019.00081"},{"key":"e_1_2_1_15_1","volume-title":"Can we beat the prefix filtering?: an adaptive framework for similarity join and search. SIGMOD","author":"Jiannan Wang","year":"2012","unstructured":"Wang Jiannan , Li Guoliang , and Feng Jianhua . 2012. Can we beat the prefix filtering?: an adaptive framework for similarity join and search. SIGMOD ( 2012 ), 85--96. Wang Jiannan, Li Guoliang, and Feng Jianhua. 2012. Can we beat the prefix filtering?: an adaptive framework for similarity join and search. SIGMOD (2012), 85--96."},{"key":"e_1_2_1_16_1","volume-title":"EDBT (Lecture Notes in Computer Science)","author":"Kailing Karin","unstructured":"Karin Kailing , Hans-Peter Kriegel , Stefan Sch\u00f6nauer , and Thomas Seidl . 2004. Efficient Similarity Search for Hierarchical Data in Large Databases . In EDBT (Lecture Notes in Computer Science) , Vol. 2992 . Springer , 676--693. Karin Kailing, Hans-Peter Kriegel, Stefan Sch\u00f6nauer, and Thomas Seidl. 2004. Efficient Similarity Search for Hierarchical Data in Large Databases. In EDBT (Lecture Notes in Computer Science), Vol. 2992. Springer, 676--693."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Nikolai Karpov and Qin Zhang. 2022. SyncSignature: A Simple Efficient Parallelizable Framework for Tree Similarity Joins. https:\/\/github.com\/nkkarpov\/syncsignature\/blob\/main\/paper\/SyncSignature-full-version.pdf.  Nikolai Karpov and Qin Zhang. 2022. SyncSignature: A Simple Efficient Parallelizable Framework for Tree Similarity Joins. https:\/\/github.com\/nkkarpov\/syncsignature\/blob\/main\/paper\/SyncSignature-full-version.pdf.","DOI":"10.14778\/3565816.3565833"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-68530-8_8"},{"key":"e_1_2_1_19_1","unstructured":"Chen Li Jiaheng Lu and Yiming Lu. 2008. Efficient Merging and Filtering Algorithms for Approximate String Searches. In ICDE. 257--266.  Chen Li Jiaheng Lu and Yiming Lu. 2008. Efficient Merging and Filtering Algorithms for Approximate String Searches. In ICDE. 257--266."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590989.2590994"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/2078331.2078340"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781933019604"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2095686.2095692"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2015.08.004"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Mateusz Pawlik and Nikolaus Augsten. 2020. Minimal Edit-Based Diffs for Large Trees. In CIKM. ACM 1225--1234.  Mateusz Pawlik and Nikolaus Augsten. 2020. Minimal Edit-Based Diffs for Large Trees. In CIKM. ACM 1225--1234.","DOI":"10.1145\/3340531.3412026"},{"key":"e_1_2_1_26_1","unstructured":"Jianbin Qin Wei Wang Yifei Lu Chuan Xiao and Xuemin Lin. 2011. Efficient exact edit similarity query processing with the asymmetric signature scheme. In SIGMOD. 1033--1044.  Jianbin Qin Wei Wang Yifei Lu Chuan Xiao and Xuemin Lin. 2011. Efficient exact edit similarity query processing with the asymmetric signature scheme. In SIGMOD. 1033--1044."},{"key":"e_1_2_1_27_1","volume-title":"Fast and Scalable Distributed Set Similarity Joins for Big Data Analytics","author":"Rong Chuitian","unstructured":"Chuitian Rong , Chunbin Lin , Yasin N. Silva , Jianguo Wang , Wei Lu , and Xiaoyong Du. 2017. Fast and Scalable Distributed Set Similarity Joins for Big Data Analytics . In ICDE. IEEE Computer Society , 1059--1070. Chuitian Rong, Chunbin Lin, Yasin N. Silva, Jianguo Wang, Wei Lu, and Xiaoyong Du. 2017. Fast and Scalable Distributed Set Similarity Joins for Big Data Analytics. In ICDE. IEEE Computer Society, 1059--1070."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2012.195"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/322139.322143"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809976"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2006.07.002"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Rares Vernica Michael J. Carey and Chen Li. 2010. Efficient parallel set-similarity joins using MapReduce. In SIGMOD. ACM 495--506.  Rares Vernica Michael J. Carey and Chen Li. 2010. Efficient parallel set-similarity joins using MapReduce. In SIGMOD. ACM 495--506.","DOI":"10.1145\/1807167.1807222"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Hanzhi Wang Zhewei Wei Ye Yuan Xiaoyong Du and Ji-Rong Wen. 2020. Exact Single-Source SimRank Computation on Large Graphs. In SIGMOD. ACM 653--663.  Hanzhi Wang Zhewei Wei Ye Yuan Xiaoyong Du and Ji-Rong Wen. 2020. Exact Single-Source SimRank Computation on Large Graphs. In SIGMOD. ACM 653--663.","DOI":"10.1145\/3318464.3389781"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920992"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2012.79"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453957"},{"key":"e_1_2_1_37_1","volume-title":"Tung","author":"Yang Rui","year":"2005","unstructured":"Rui Yang , Panos Kalnis , and Anthony K. H . Tung . 2005 . Similarity Evaluation on Tree-structured Data. In SIGMOD. ACM , 754--765. Rui Yang, Panos Kalnis, and Anthony K. H. Tung. 2005. Similarity Evaluation on Tree-structured Data. In SIGMOD. ACM, 754--765."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098003"},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Haoyu Zhang and Qin Zhang. 2019. MinJoin: Efficient Edit Similarity Joins via Local Hash Minima. In SIGKDD. 1093--1103.  Haoyu Zhang and Qin Zhang. 2019. MinJoin: Efficient Edit Similarity Joins via Local Hash Minima. In SIGKDD. 1093--1103.","DOI":"10.1145\/3292500.3330853"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218082"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3565816.3565833","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T04:36:50Z","timestamp":1672202210000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3565816.3565833"}},"subtitle":["a simple, efficient, parallelizable framework for tree similarity joins"],"short-title":[],"issued":{"date-parts":[[2022,10]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["10.14778\/3565816.3565833"],"URL":"https:\/\/doi.org\/10.14778\/3565816.3565833","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,10]]},"assertion":[{"value":"2022-11-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}