We consider the problem of indexing a text T (of length n) with a light data structure that supports efficient search of patterns P (of length m) allowing errors under the Hamming distance. We propose a hash-based strategy that employs two classes of hash functions—dubbed Hamming-aware and de Bruijn—to drastically reduce search space and memory footprint of the index, respectively. We use our succinct hash data structure to solve the k-mismatch search problem in 2n log σ + o(n log σ) bits of space with a random- ized algorithm having smoothed complexity O((2σ)k(log n)k(log m+ξ)+ (occ + 1) · m), where σ is the alphabet size, occ is the number of occur- rences, and ξ is a term depending on m, n, and on the amplitude ε of the noise perturbing text and pattern. Significantly, we obtain that for any ε > 0, for m large enough, ξ ∈ O(log m): our results improve upon previous linear-space solutions of the k-mismatch problem.

Hashing and Indexing: Succinct DataStructures and Smoothed Analysis

PREZZA, Nicola
2014-01-01

Abstract

We consider the problem of indexing a text T (of length n) with a light data structure that supports efficient search of patterns P (of length m) allowing errors under the Hamming distance. We propose a hash-based strategy that employs two classes of hash functions—dubbed Hamming-aware and de Bruijn—to drastically reduce search space and memory footprint of the index, respectively. We use our succinct hash data structure to solve the k-mismatch search problem in 2n log σ + o(n log σ) bits of space with a random- ized algorithm having smoothed complexity O((2σ)k(log n)k(log m+ξ)+ (occ + 1) · m), where σ is the alphabet size, occ is the number of occur- rences, and ξ is a term depending on m, n, and on the amplitude ε of the noise perturbing text and pattern. Significantly, we obtain that for any ε > 0, for m large enough, ξ ∈ O(log m): our results improve upon previous linear-space solutions of the k-mismatch problem.
2014
Algorithms and Computation: 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings
File in questo prodotto:
File Dimensione Formato  
chp:10.1007/978-3-319-13075-0_13.pdf

non disponibili

Dimensione 226.59 kB
Formato Adobe PDF
226.59 kB Adobe PDF   Visualizza/Apri

I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10278/3729830
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 4
social impact