路网环境下访问序列受限的多标签路线查询算法  

Multi-Tag Route Query Based on Order Constraints in Road Networks

作　　者：张金增[1] 文洁[1] 孟小峰[1] 

机构地区：[1]中国人民大学信息学院,北京100872

出　　处：《计算机学报》2012年第11期2317-2326,共10页Chinese Journal of Computers

基　　金：国家自然科学基金(60833005;61070055;91024032);中国人民大学科学研究基金(10XNI018);核高基重大专项(2010ZX01042-002-003);高等学校博士学科点专项科研基金(200800020002)资助~~

摘　　要：随着移动互联网、地理定位技术和智能终端设备的迅速普及,产生了大量的位置信息和其对应的标签(tag)描述信息.路线搜索是人们出行时经常进行的活动,但面临多个任务需求时,寻找最佳路线是一项极为耗时的工作.此外空间对象本身的访问权限和用户指定的限制一定程度上制约了对象的访问次序.针对上述情况,文中提出了一种路网环境下访问序列受限的多标签路线(MTROC)查询,该查询的目标是找出一条从源点到目标点、经由与查询中给定的tag相匹配的空间对象且满足序列约束的最短线路.文中证明了MTROC查询问题是NP-hard,并基于增强的路线叠置-关联目录(EROAD)索引提出了3种近似算法.路线扩展RE-Greedy算法和路线渐增插入RII-Greedy算法通过局部更新获得满足需求的路线,而全局路线优化算法GROA为MTROC查询提供一个全局近似最优解.使用真实和合成数据集对文中提出的算法的有效性和可扩展性进行分析评估,实验结果表明3种算法都能有效地完成MTROC查询,其中GROA算法可扩展性最好,而RII-Greedy算法返回的路线质量最高.With the increasing popularity of mobile Web, geo-positioning technologies and smart devices, it enables users to generate amounts of location information and corresponding descriptive tags. Route search is a frequent laborious task when users have multiple demands on the trip. In addition, users prefer to specifying the order by which some spatial objects should be vis- ited before others. This paper proposes a new type of route search, multi-tag route query based on order constraints （MTROC） in road networks. We prove that the MTROC query is NP-hard and present three approximate algorithms based on enhanced route overlay and association directory index structure. The route extension greedy algorithm and the route incremental intersection algorithm build a route by greedily inserting a spatial object into some certain segments of the sequence. On contrast, the global route optimistic algorithm provides a globally approximate optimal solution for MTROC query. Extensive experiments on both synthetic and real-world datasets illustrate the efficiency and sealability of the three algorithms proposed in this paper.

关 键 词：路网 路线查询 序列约束 签名文件 标签 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]