Fast entropy-bounded string dictionary look-up with mismatches

2018/06/25 by Gawrychowski, Paweł, Landau, Gad M., Starikovskaya, Tatiana · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1806.09646

Abstract

We revisit the fundamental problem of dictionary look-up with mismatches. Given a set (dictionary) of d strings of length m and an integer k, we must preprocess it into a data structure to answer the following queries: Given a query string Q of length m, find all strings in the dictionary that are at Hamming distance at most k from Q. Chan and Lewenstein (CPM 2015) showed a data structure for k = 1 with optimal query time O(m/w + occ), where w is the size of a machine word and occ is the size of the output. The data structure occupies O(w d log^1+ε d) extra bits of space (beyond the entropy-bounded space required to store the dictionary strings). In this work we give a solution with similar bounds for a much wider range of values k. Namely, we give a data structure that has O(m/w + log^k d + occ) query time and uses O(w d log^k d) extra bits of space.

Cited by

• Space-Efficient k-Mismatch Text Indexes

Related

• Streaming dictionary matching with mismatches
• A practical index for approximate dictionary matching with few\n mismatches
• Engineering Small Space Dictionary Matching
• Improved Fast Similarity Search in Dictionaries
• Nearly Optimal Static Las Vegas Succinct Dictionary