A dictionary for approximate string search and longest prefix search

ABSTRACT

In this paper we propose a dictionary data structure for string search with errors where the query string may didiffer from the expected matching string by a few edits. This data structure can also be used to find the database string with the longest common prefix with few errors. Specifically, with a database of n random strings, each of length of O(m), we show how to perform string search on a query string that differs from its closest match by k edits using a data structure of linear size and query time equal to Õ(log n ^{2 log n klog _a 2m} over 2m). This means that if k < m over log _a 2m log n, then the query time is Õ(1). This is of significant in practice as there are several applications where k is small relative to m. Our approach converts strings into bit vectors so that similar strings can map to similar bit vectors with small hamming distance. A simple reduction can be used to obtain similar results for approximate longest prefix search.

REFERENCES

• 1: Alexandr Andoni , Piotr Indyk, Efficient algorithms for substring near neighbor problem, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1203-1212, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109690]
• 2: Ziv Bar-Yossef , T. S. Jayram , Robert Krauthgamer , Ravi Kumar, Approximating Edit Distance Efficiently, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.550-559, October 17-19, 2004 [doi>10.1109/FOCS.2004.14]
• 3: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 4: A. Broder and M. Mitzenmacher. Network applications of bloom filters: A survey, 2002.
• 5: A. Broder, On the Resemblance and Containment of Documents, Proceedings of the Compression and Complexity of Sequences 1997, p.21, June 11-13, 1997
• 6: Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations, Journal of Computer and System Sciences, v.60 n.3, p.630-659, June 2000 [doi>10.1006/jcss.1999.1690]
• 7: Richard Cole , Lee-Ad Gottlieb , Moshe Lewenstein, Dictionary matching and indexing with errors and don't cares, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007374]
• 8: Cristian Estan , George Varghese, New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice, ACM Transactions on Computer Systems (TOCS), v.21 n.3, p.270-313, August 2003 [doi>10.1145/859716.859719]
• 9: Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
• 10: Adam Kirsch and Michael Mitzenmacher. Distance-sensitive bloom filters. In Proceedings of ALENEX 06, 2006.
• 11: Eyal Kushilevitz , Rafail Ostrovsky , Yuval Rabani, Efficient search for approximate nearest neighbor in high dimensional spaces, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.614-623, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276877]
• 12: G M Landau , U Vishkin, Efficient string matching with k mismatches, Theoretical Computer Science, v.43 n.2-3, p.239-249, July 1986
• 13: M. D. McIllroy. Development of a spelling list. IEEE Transactions on Communications, 30(1):91--99, 1982.
• 14: J. K. Mullin , D. J. Margoliash, A tale of three spelling checkers, Software—Practice & Experience, v.20 n.6, p.625-630, June 1990 [doi>10.1002/spe.4380200607]
• 15: Gonzalo Navarro, A guided tour to approximate string matching, ACM Computing Surveys (CSUR), v.33 n.1, p.31-88, March 2001 [doi>10.1145/375360.375365]
• 16: Rafail Ostrovsky , Yuval Rabani, Low distortion embeddings for edit distance, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060623]
• 17: H. Shang , T. h. Merrettal, Tries for Approximate String Matching, IEEE Transactions on Knowledge and Data Engineering, v.8 n.4, p.540-547, August 1996 [doi>10.1109/69.536247]
• 18: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 19: E. Ukkonnen. Finding approximate pattern in strings. Journal of Algorithms, 6:132--137, 1985.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Experimentation

Keywords:
embeddings, hamming space