In this paper we consider the problem of finding the approximate nearest neighbor when the data set points are the substrings of a given text T . Specifically, for a string T of length n, we present a data structure which does the following: given a pattern P , if there is a substring of T within the distance R from P , it reports a (possibly different) substring of T within distance cR from P . The length of the pattern P , denoted by m, is not known in advance. For the case where the distances are measured using the Hamming distance, we present a data structure which usesÕ(n 1+1/c ) space 1 and withÕ n 1/c + mn query time. This essentially matches the earlier bounds of [Ind98], which assumed that the pattern length m is fixed in advance. In addition, our data structure can be constructed in timeÕ n 1+1/c + n 1+o(1) M 1/3 , where M is an upper bound for m. This essentially matches the preprocessing bound of [Ind98] as long as the termÕ n 1+1/c dominates the running time, which is the case when, e.g., c < 3. We also extend our results to the case where the distances are measured according to the l1 distance. The query time and the space bound are essentially the same, while the preprocessing time becomesÕ n 1+1/c + n 1+o(1) M 2/3 .
Andoni and Indyk REF use locality sensitive hashing (LSH) to construct a data structure of sizeÕ(n 1+1/c ), where n is the length of the text and c is a distortion factor andÕ(n 1/c + n 1+o(1) M 1/3 ) where M is the upper bound for the query length.
Efficient algorithms for substring near neighbor problem
SODA '06
Mathematics Computer Science