Fråga automatisk komplettering är en viktig funktion som sparar användare många tangenttryckningar från att skriva hela frågan. I det här dokumentet studerar vi problemet med automatisk frågekomplettering som tolererar fel i användarnas inmatning med hjälp av redigeringsavståndsbegränsningar. Tidigare tillvägagångssätt index datasträngar i en trie, och kontinuerligt upprätthålla alla prefix för datasträngar vars redigera avstånd från frågan ligger inom tröskeln. Det stora inneboende problemet är att antalet sådana prefix är enormt för de första få tecknen i frågan och är exponentiellt i alfabetets storlek. Detta resulterar i långsam frågesvar även om hela frågan ungefär matchar endast några prefix. I detta dokument föreslår vi en ny stadsdel generationsbaserad algoritm, IncNGTree, som kan uppnå upp till två storleksordningar speedup över befintliga metoder för fel-tolerant fråga autocompletion problem. Vår föreslagna algoritm bara upprätthåller en liten uppsättning aktiva noder, vilket sparar både utrymme och tid för att behandla frågan. Vi studerar också effektiv dubblett borttagning som är ett kärnproblem i att hämta svar på frågor. Dessutom föreslår vi optimeringstekniker för att minska vår indexstorlek, samt diskussioner om flera tillägg till vår metod. Effektiviteten hos vår metod demonstreras mot befintliga metoder genom omfattande experiment på verkliga dataset.
Xiao m.fl. REF utvidgade ytterligare tillvägagångssättet, genom att föreslå en ny stadsdel generation-baserad algoritm, som kan uppnå upp till två storleksordningar hastigheter över befintliga metoder för feltolerant fråga automatisk komplettering problem.
Efficient Error-tolerant Query Autocompletion
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}