路网环境下访问序列受限的多标签路线查询算法
外文标题：Multi-Tag Route Query Based on Order Constraints in Road Networks
文献类型：期刊
作者：张金增[1]
机构：[1]中国人民大学信息学院
[2]中国人民大学信息学院
[3]中国人民大学信息学院
通讯作者：Zhang, J.-Z.(zajize@163.com)
年：2012
期刊名称：计算机学报
卷：35
期：11
页码范围：2317-2326
增刊：增刊
收录情况：EI(20124715691635)
所属部门：信息学院
语言：中文
ISSN：0254-4164
链接地址：http://d.g.wanfangdata.com.cn/Periodical_jsjxb201211010.aspx
DOI：10.3724/SP.J.1016.2012.02317
人气指数：3
浏览次数：3
基金：国家自然科学基金; 中国人民大学科学研究基金; 核高基重大专项; 高等学校博士学科点专项科研基金
关键词：路网;路线查询;序列约束;签名文件;标签
摘要：随着移动互联网、地理定位技术和智能终端设备的迅速普及,产生了大量的位置信息和其对应的标签(tag)描述信息.路线搜索是人们出行时经常进行的活动,但面临多个任务需求时,寻找最佳路线是一项极为耗时的工作.此外空间对象本身的访问权限和用户指定的限制一定程度上制约了对象的访问次序.针对上述情况,文中提出了一种路网环境下访问序列受限的多标签路线(MTROC)查询,该查询的目标是找出一条从源点到目标点、经由与查询中给定的tag相匹配的空间对象且满足序列约束的最短线路.文中证明了MTROC查询问题是NP-hard,并基于增强的路线叠置-关联目录(EROAD)索引提出了3种近似算法.路线扩展RE-Greedy算法和路线渐增插入RⅡ-Greedy算法通过局部更新获得满足需求的路线,而全局路线优化算法GROA为MTROC查询提供一个全局近似最优解.使用真实和合成数据集对文中提出的算法的有效性和可扩展性进行分析评估,实验结果表明3种算法都能有效地完成MTROC查询,其中GROA算法可扩展性最好,而RⅡ-Greedy算法返回的路线质量最高.
作者其他论文
差分隐私保护下一种精确挖掘top-k频繁模式方法.张啸剑;王淼;孟小峰.计算机研究与发展.2014,51(1),104-114.
大规模图数据可达性索引技术:现状与展望.富丽贞;孟小峰.计算机研究与发展.2015,52(1),116-129.
海量高维向量的并行Top-k连接查询.马友忠;慈祥;孟小峰.计算机学报.2015,38(1),86-98.
基于小数据的在线用户兴趣长程演化研究.李勇;孟小峰;刘继,等.计算机研究与发展.2015,779-788.
云数据管理索引技术研究.马友忠;孟小峰.软件学报.2015,26(1),145-166.
