Improved space-time tradeoffs for approximate full-text indexing with one edit error

Details Improved space-time tradeoffs for approximate full-text indexing with one edit error Improved space-time tradeoffs for approximate full-text indexing with one edit error

2011-03-10

arxiv.org/abs/1103.2167v1

Computer Science

Data Structures and Algorithms

Preprint 22 pages

Scientific paper

In this paper we are interested in indexing texts for susbstring matching with one edit error. That is given a text T of n characters over an alphabet of size sigma, we are asked to build a data structure that answers to the following query: find all the occ substrings of the text which are at edit distance at most 1 from a string p of length m. In this paper we show two new results for this problem. The first result suitable for arbitrary alphabet size sigma uses O(n(log^epsilon n+ log sigma)) words of space and answers to queries in time O(m+occ). This improves simultaneously in space and time over the result of Cole et Al (STOC 2004). The second result suitable only for constant alphabet relies on compressed indexes and comes in two variants: the first variant uses O(n log^epsilon n) bits of space (where epsilon is any constant such that 0

Affiliated with

Also associated with

No associations

Rating

Improved space-time tradeoffs for approximate full-text indexing with one edit error does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Improved space-time tradeoffs for approximate full-text indexing with one edit error, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved space-time tradeoffs for approximate full-text indexing with one edit error will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-429736