期刊名称：International Journal of Computer Trends and Technology
电子版ISSN：2231-2803
出版年度：2014
卷号：16
期号：4
页码：161-165
出版社：Seventh Sense Research Group
摘要：This work deals with the approximate string search in large spatial databases. We investigate range queries augmented with a string similarity search predicate in both Euclidean space and road networks. We make this query the spatial approximate Existing (Apr 19, 2013) string (SAS) query. In Euclidean space, we propose an approximate solution MHRtree, which will embed minwise signatures into Rtree. These minwise signature for an index node u keeps a concise representation of the union of qgrams from strings under the subtree of u. We here analyze the pruning functionality of such signatures based on the set resemblance between he query string and the qgrams from the subtrees with index nodes. Here we also discuss how to estimate the selectivity of a SAS query in Euclidean space, for which here we present a novel adaptive algorithm to find balanced partitions using both the spatial and string information stored in the tree as discussed. For queries on road networks, we propose a novel method, the RSASSOL, which significantly outperforms the baseline algorithm in practice. RSASSOL combines the qgram based inverted lists and the pruning based on reference nodes. Extensive experiments on large real data sets demonstrate the efficiency and effectiveness of the approach.
关键词：A Framework for Geographical based Approximate String Search
