En sträng likhet gå hittar liknande par mellan två samlingar av strängar. Det är en viktig verksamhet i många tillämpningar, såsom dataintegration och rengöring, och har fått stor uppmärksamhet på senare tid. I den här artikeln studerar vi stränglikhet som förenas med redigerings-distansbegränsningar. Befintliga metoder använder vanligtvis ett filter-och-raffinaderiramverk och har följande nackdelar: (1) De är ineffektiva för datamängderna med korta strängar (den genomsnittliga stränglängden är inte större än 30); (2) De omfattar stora index; (3) De är dyra att stödja dynamisk uppdatering av datamängder. För att ta itu med dessa problem föreslår vi en ny ram som kallas trie-join, som kan generera resultat effektivt med små index. Vi använder en trie struktur för att indexera strängarna och använda trie struktur för att effektivt hitta liknande strängpar baserat på subtrie beskärning. Vi utformar effektiva trie-join algoritmer och beskärning tekniker för att uppnå hög prestanda. Vår metod kan enkelt utökas för att stödja dynamisk uppdatering av datamängder effektivt. Experimentella resultat visar att våra algoritmer överträffar toppmoderna metoder med en storleksordning på tre verkliga datauppsättningar med korta strängar.
BiTreeJoin REF är en trie-baserad metod för att stödja effektiv redigering likhet förenar med sub-trie beskärning.
Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}