Vi studerar problemet med redigering likhet går, där med tanke på en uppsättning strängar och ett tröskelvärde värde K, vi vill mata ut alla par av strängar vars redigeringsavstånd är som mest K. Redigera likhet gå är ett grundläggande problem i datarengöring / integration, bioinformatik, samarbete ltering och naturligt språk bearbetning, och har identifierats som en primitiv operatör för databassystem. är problem har studerats i stor utsträckning i litteraturen. Vi har dock observerat att alla befintliga algoritmer inte räcker till på långa strängar och stora avståndströsklar. I detta papper föreslår vi en algoritm som heter EmbedJoin som skalar mycket bra med stränglängd och avstånd tröskel. Vår algoritm är byggd på den senaste utvecklingen av metriska inbäddningar för redigeringsavstånd, och är mycket olika från alla tidigare tillvägagångssätt. Vi demonstrerar genom en omfattande uppsättning experiment att EmbedJoin helt och hållet överträffar de tidigare bästa algoritmerna på långa strängar och stora avståndströsklar. 2 I en "svag" inbäddning, förvrängningen innehar för varje par av strängar med konstant sannolikhet, låt oss säga 0,99. I kontrast, i en "stark" inbäddning, med sannolikhet 0.99 förvrängningen innehar för alla par av strängar samtidigt.
Nyligen har CGK tillämpats på problemet med redigering likhet går REF.
EmbedJoin: Efficient Edit Similarity Joins via Embeddings
{'venue': "KDD '17", 'journal': None, 'mag_field_of_study': ['Computer Science']}