面向空间兴趣区域的路线查询

Spatial Region of Interests Oriented Route Query

广泛的位置感知应用产生了大量的空间文本数据,其中既包含位置信息,也包含空间文本属性.为了利用这些丰富的信息来描述用户对路线的偏好,提出了面向空间兴趣区域的路线查询(region of interests oriented route query, ROIR).给定空间关键字集合及路线长度约束,ROIR检索满足长度约束和最高收益的由空间兴趣区域组成的路线.与传统的空间关键字路线查询相比,ROIR的对象由空间兴趣点扩展为兴趣区域,增加了用户的选择空间,使得查询结果的适用性更好.针对多种类型的海量空间兴趣点(point of interests, POI)及相关文本信息,设计了2层数据组织模型,模型中集成了POI对象的空间位置、关键字及POI对象间的转移关系.基于2层数据组织模型,提出了综合空间对象位置、转移图以及关键字3类信息的索引结构,同时预计算了关键字的收益统计值,并以签名方式存储在转移结点上.设计了ROIR路线查询精确算法.ROIR是一个NP难问题,为了有效地实现ROIR提出了近似率为1/ε的近似算法.利用真实数据集进行了详细的实验分析,评估了所提出算法的有效性.

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.