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 / POLICRITI, Alberto; PREZZA, Nicola. - (2014), pp. 157-168. ((Intervento presentato al convegno 25th International Symposium, ISAAC 2014 tenutosi a Jeonju, Corea nel December 15-17, 2014 [10.1007/978-3-319-13075-0_13].

Hashing and Indexing: Succinct DataStructures and Smoothed Analysis

PREZZA, Nicola
2014

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.
9783319130743
Hash Function, Hash Table, Query Time ,Alphabet Size, Reduce Search Space
Hashing and Indexing: Succinct DataStructures and Smoothed Analysis / POLICRITI, Alberto; PREZZA, Nicola. - (2014), pp. 157-168. ((Intervento presentato al convegno 25th International Symposium, ISAAC 2014 tenutosi a Jeonju, Corea nel December 15-17, 2014 [10.1007/978-3-319-13075-0_13].
File in questo prodotto:
File Dimensione Formato  
chp:10.1007/978-3-319-13075-0_13.pdf

Solo gestori archivio

Tipologia: Versione dell'editore
Licenza: DRM non definito
Dimensione 226.59 kB
Formato Adobe PDF
226.59 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS 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: http://hdl.handle.net/11385/194111
Citazioni
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 4
social impact