Quality Preference Spatial Approximate String Search

Joslin T.J

Abstract: This work deals with the approximate string search in large spatial databases. A spatial preference query ranks objects based on the qualities of features in their spatial neighborhood. Specifically; investigate range queries augmented with a string similarity search predicate in road networks. And dub this query the spatial approximate string (SAS) query. 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. Analyze 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. For queries on road networks; using a novel exact method; RSASSOL; which significantly outperforms the baseline algorithm in practice. The RSASSOL combines the q-gram based inverted lists and the reference nodes based pruning. Extensive experiments on large real data sets demonstrate the efficiency and effectiveness of our approaches.

Keywords: approximate string search, range query, road network, spatial databases, quality preference search