I/O-Efficient Dictionary Search with One Edit Error
Lists
Only you see this
Abstract
This paper studies the 1-error dictionary search problem in external memory. The input is a set D of strings whose characters are drawn from a constant-size alphabet. Given a string q, a query reports the ids of all strings in D that are within 1 edit distance from q. We give a structure occupying O(n/B) blocks that answers a query in \(O(1 + \frac{m}{wB} + \frac{k}{B})\) I/Os, where n is the total length of all strings in D, m is the length of q, k is the number of ids reported, w is the size of a machine word, and B is the number of words in a block.
BibTeX
@inproceedings{chung2014i,
author = {Chin-Wan Chung and Yufei Tao and Wei Wang},
title = {{I/O-Efficient Dictionary Search with One Edit Error}},
booktitle = {SPIRE},
year = {2014},
url = {https://openreview.net/forum?id=GAMLxPCTlr},
}Loading related content...