Description

This work deals with the approximate string search in large spatial databases. Specially, I investigate range queries augmented with a string similarity search predicate in both Euclidean space and road networks. I dub this query the Spatial Approximate String (SAS) query. In Euclidean space, it propose an approximate solution, the MHR-tree, which embeds min-wise signatures into an R-tree. 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. It analyzes the pruning functionality of such signatures based on the set resemblance between the query string and the q-grams from the sub-trees of index nodes. We 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. MHR-tree supports a wide range of query predicates efficiently, including range and nearest neighbor queries. We also discuss how to estimate range query selectivity accurately. We present a novel adaptive algorithm for finding balanced partitions using both the spatial and string information stored in the tree. Extensive experiments on large real data sets demonstrate the efficiency and effectiveness of our approach.