Approximate String Search in Large Spatial Database

Applications are featured with both text and location information, which leads to a search like: spatial approximate string search (SAS). Mainly four issues are identified in the general area of SAS. They are: (i) Spatial approximate string search in Euclidean space (Esas); (ii) Spatial approximate string search on road networks (RSAS); (iii) Selectivity Estimation for Esas Range Queries; (iv) Multi-Approximate-Keyword Routing query on road networks. For efficiently answering spatial approximate string queries in Euclidean space, SAS propose a novel index structure, IR2 -tree, which is based on the R-tree augmented with the min-wise signature and the linear hashing technique. Extensive experiments on large real data sets demonstrate the efficiency and effectiveness of the proposed approach.