Efficient algorithms for substring near neighbor problem
Alexandr Andoni, Piotr Indyk · 2006
In this paper we consider the problem of finding the ap-proximate 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 dif-ferent) substring of T within distance cR from P. The length of the pattern P, denoted by m, is not known in ad-vance. For the case where the distances are measured using the Hamming distance, we present a data structure which uses Õ(n1+1/c) space1 and with Õ n1/c +mno(1) query time. This essentially matches the earlier bounds of [Ind98], which assumed that the pattern length m is fixed in ad-vance. In addition, our data structure can be constructed in time Õ n1+1/c + n1+o(1)M1/3, whereM is an upper bound for m. This essentially matches the preprocessing bound of [Ind98] as long as the term Õ n1+1/c dominates the run-ning time, which is the case when, e.g., c < 3. We also extend our results to the case where the dis-tances are measured according to the l1 distance. The query time and the space bound are essentially the same, while the preprocessing time becomes Õ n1+1/c + n1+o(1)M2/3