Spatial Region of Interests Oriented Route Query

Extensive location aware applications produce a large number of spatial text data, which contains both location information and spatial text attributes. In order to use this rich information to describe users’ preference for routes, a region of interests oriented route query (ROIR) is proposed. Given a set of spatial keywords and the constraint in length, ROIR retrieves a route composed of spatial interest regions, which satisfies the distance constraints with the highest profit. Compared with the traditional spatial keyword route queries, the aim of ROIR is expanded from spatial interest points to interest regions, which increases the user’s choice and makes the query results more applicable. Aiming at various types of POI and related text information, a two-layer data organization model is designed, which integrates the spatial location of POI objects, keywords and the transfer relationship between POI objects. Based on the two-tier data organization model, an index structure is proposed, which integrates three kinds of information: spatial object location, transfer graph and keywords. At the same time, the profits of keywords are pre-calculated and stored on the transfer node as signatures. The exact algorithm of ROIR is designed. Aiming at various types of massive POI and related text information, this paper designs a two-tier data organization model, proposes the corresponding index structure, and designs an accurate algorithm for ROIR route query. ROIR is a NP hard problem. In order to implement ROIR effectively, an approximate algorithm with approximate rate 1/ε is proposed. A detailed experimental analysis is carried out on real data sets to evaluate the effectiveness of the proposed algorithm.