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

0.00 Avg rating0 Votes
Article ID: iaor201526359
Volume: 72
Issue: 3
Start Page Number: 791
End Page Number: 817
Publication Date: Jul 2015
Journal: Algorithmica
Authors:
Keywords: datamining
Abstract:

In this paper we are interested in indexing texts for substring matching queries with one edit error. That is, given a text T of n characters over an alphabet of size σ, we are asked to build a data structure that answers the following query: find all the occ substrings of the text that are at edit distance at most 1 from a given string q of length m. In this paper we show two new results for this problem. The first result, suitable for an unbounded alphabet, uses O(nlog ϵ n) (where ϵ is any constant such that 0<ϵ <1) 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. The second result, suitable only for a constant alphabet, relies on compressed text indices and comes in two variants: the first variant uses O(nlog ϵ n) bits of space and answers to queries in time O(m+occ), while the second variant uses O(nloglogn) bits of space and answers to queries in time O((m+occ)loglogn). This second result improves on the previously best results for constant alphabets achieved in Lam et al. and Chan et al.

Reviews

Required fields are marked *. Your email address will not be published.