A dictionary for approximate string search and longest prefix search

Sreenivas Gollapudi, Rina PanigrahyCIKM 2006 · OpenReview

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.
BibTeX
@inproceedings{gollapudi2006dictionary,
  author = {Sreenivas Gollapudi and Rina Panigrahy},
  title = {{A dictionary for approximate string search and longest prefix search}},
  booktitle = {ACM International Conference on Information and Knowledge Management},
  year = {2006},
  url = {https://openreview.net/forum?id=6Ej9sefFheeh},
}

Loading related content...

Figure