I detta papper anser vi problemet med att hitta den ungefärliga närmaste granne när dataset punkter är delsträngar av en viss text T. Särskilt, för en sträng T längd n, presenterar vi en datastruktur som gör följande: med tanke på ett mönster P, Om det finns en delsträng av T inom avståndet R från P, Det rapporterar en (eventuellt annorlunda) delsträng av T inom avstånd cR från P. Längden på mönstret P, betecknad av m, är inte känd i förväg. För de fall där avstånden mäts med hjälp av hammingavståndet, presenterar vi en datastruktur som använder Õ(n 1+1/c ) utrymme 1 och med Õ n 1/c + mn frågetid. Detta motsvarar i huvudsak de tidigare gränserna i [Ind98], som antog att mönstrets längd m är fast i förväg. Dessutom kan vår datastruktur konstrueras i tid Õ n 1+1/c + n 1+o(1) M 1/3, där M är en övre gräns för m. Detta motsvarar i huvudsak förbehandlingen av [Ind98] så länge termen Õ n 1+1/c dominerar körtiden, vilket är fallet när t.ex. c < 3. Vi utökar också våra resultat till det fall där avstånden mäts enligt l1-avståndet. Frågetiden och det utrymme som är bundet är i huvudsak samma, medan förbehandlingstiden blir Õ n 1+1/c + n 1+o(1) M 2/3.
Andoni och Indyk REF använder locality sensitive hashing (LSH) för att konstruera en datastruktur av storlek Õ(n 1+1/c ), där n är textens längd och c är en förvrängningsfaktor och Õ(n 1/c + n 1+o(1) M 1/3 ) där M är den övre gränsen för frågelängden.
Efficient algorithms for substring near neighbor problem
{'venue': "SODA '06", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}