Abstract
Let W be a set of n binary strings of length m each. We are interested in designing data structures for W that can answer d-queries quickly, that is, given a binary string α, decide whether there is any member of W within Hamming distance d of α. This problem, originally raised by Minsky and Papert [MP], remains a challenge in data structure design. In this paper, we make an initial effort towards a theoretical study of the small d case. Our main result is a data structure that achieves O(m log log n) query time with O(nm log m) space for the d = 1 case.
This author was supported in part by the National Science Foundation under grant CCR-9301430.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
D. Dolev, Y. Harari, N. Linial, N. Nisan, and M. Pamas, Neighborhood preserving hashing and approximate queries, Proceedings of Fifth ACM Symposium on Discrete Algorithms, 1994.
D. Dolev, Y. Harari and M. Parnas, Finding the neighborhood of a query in a dictionary, Proceedings of Second Israel Symposium on Theory of Computing and Systems, 1993.
P. Elias, Efficient storage and retrieval by content and address of static files, Journal ACM 21 (1974), 246–260.
M. Fredman, M. Komlós, and E. Szemerédi, Storing a sparse table with O(1) worst case access time, Journal ACM 31 (1984), 538–544.
Z. Galil and K. Park, An improved algorithm for approximate string matchng, SIAM J. on Computing 19 (1990), 989–999.
D. Greene, M. Parnas and F. Yao, Multi-index hashing for information retrieval, Proceedings of 1994 IEEE Symposium on Foundations of Computer Science, November 1994, 722–731.
G. Landau and U. Vishkin, Fast string matching with k differences, J. Comp. Sys. Sci. 37 (1988), 63–78.
U. Manber and S. Wu, An algorithm for approximate membership checking with application to password security, Information Processing Lettters 50 (1994), 191–197.
M. Minsky and S. Papert, Perceptrons, MIT Press, 1969.
J. Tarhio and E. Ukkonen, Approximate Boyer-Moore string matching, Report A-1990-3, Department of Computer Science, Univ. of Helsinki, March 1990.
E. Ukkonen, Finding approximate patterns in strings, J. Algorithms 6 (1985), 132–137.
E. Ukkonen and D. Wood, Approximate string matching with suffix automata, Algorithmica 10 (1993), 353–364.
A. Yao, Should tables be sorted?, Journal ACM 28 (1981), 615–628.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yao, A.C., Yao, F.F. (1995). Dictionary look-up with small errors. In: Galil, Z., Ukkonen, E. (eds) Combinatorial Pattern Matching. CPM 1995. Lecture Notes in Computer Science, vol 937. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60044-2_57
Download citation
DOI: https://doi.org/10.1007/3-540-60044-2_57
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60044-2
Online ISBN: 978-3-540-49412-6
eBook Packages: Springer Book Archive