Efficient algorithms for substring near neighbor problem

ABSTRACT

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¹ and with Õ(n^1/c + mn^o(1)) 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 l₁ 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).

References

References are not available

Index Terms

• Computing methodologies

  • Machine learning

• Theory of computation

  • Design and analysis of algorithms

    • Data structures design and analysis

      • Pattern matching

      • Sorting and searching

  • Randomness, geometry and discrete structures