Approximate String Search in Spatial Databases

This paper presents a novel index structure, MHRtree, for efficiently answering approximate string match queries in large spatial databases. The MHR-tree is based on the R-tree augmented with the min-wise signature and the linear hashing technique. The min-wise signature for an index node u keeps a concise representation of the union of q-grams from strings under the sub-tree of u. The authors analyze the pruning functionality of such signatures based on set resemblance between the query string and the q-grams from the sub-trees of index nodes.