Anyone who has ever searched for a word (pattern) in a file or checked documents for spelling errors appreciates efficient algorithms that can quickly find relevant occurrences of the pattern, even if it is inexact or incomplete. This paper surveys a class of such algorithms: indexing methods for approximate searching.

The paper is divided into sections that discuss fundamental concepts and definitions, describe the methods and algorithms, and provide a comparative analysis of the experimental results. The bibliography lists more than 180 references, with publication times spanning decades, from the 1960s to 2010. In spite of the voluminous material, thanks to the taxonomy introduced by the author, the presentation is clear and well organized. A rich appendix includes additional material, such as proofs of selected theorems. Numerous tables and figures augment the presentation. Furthermore, the main observations and key points are concisely itemized as lists, such as the “bird view” (Boytsov’s term) of key conclusions from the experimental analysis of the search methods.

The paper thoroughly describes intensive experiments that include detailed investigations of results that, on the surface, may appear to be counterintuitive. For example, with FB-tries, retrieval times for longer patterns are better than for short ones; Boytsov conducted additional experiments to understand this phenomenon.

This paper would be of interest not only to computer scientists (for whom numerous open questions are listed in the conclusion section), but also to researchers and practitioners from a variety of areas, who want to select the best search methods for such tasks as searching in dictionaries of DNA sequences.