Efficient and accurate approach for approximate string search in spatial dataset

This paper proposes a new index and method to find strings approximately in spatial databases. Specifically, the task of candidate generation is as follows. Given a location name with wrong spelling, the system finds location in OSM dataset which are most similar to that location name which are misspelled. An approximate solution is proposed using log linear model which is defined as a conditional probability distribution of a corrected word and a rule set for the correction conditioned on wrong location name. An Aho-corasic tree which is used for storing and applying correction rules referred to as rule index and an Aho-Corasic algorithm which is efficient and gives guarantee to find top k candidates. Experiment on large real OSM dataset demonstrates the accuracy of proposed method upon existing methods.