路网环境下访问序列受限的多标签路线查询算法
文献类型：会议
作者：ZHANG Jin-Zeng[1]
机构：School of Information,Renmin University of China,Beijing 100872;中国人民大学信息学院 北京 100872
年：2012
会议名称：第29届中国数据库学术会议论文集中国计算机学会
页码范围：2317-2326
会议地点：合肥
所属部门：信息学院
语言：中文
关键词：数据集 路线搜索 查询算法 访问权限
摘要：随着移动互联网、地理定位技术和智能终端设备的迅速普及,产生了大量的位置信息和其对应的标签(tag)描述信息。路线搜索是人们出行时经常进行的活动,但面临多个任务需求时,寻找最佳路线是一项极为耗时的工作。此外空间对象本身的访问权限和用户指定的限制一定程度上制约了对象的访问次序。针对上述情况,文中提出了一种路网环境下访问序列受限的多标签路线(MTROC)查询,该查询的目标是找出一条从源点到目标点、经由与查询中给定的tag相匹配的空间对象且满足序列约束的最短线路。文中证明了MTROC查询问题是NP-hard,并基于增强的路线叠置-关联目录(EROAD)索引提出了3种近似算法,路线扩展RE-Greedy算法和路线渐增插入R(II)-Greedy算法通过局部更新获得满足需求的路线,而全局路线优化算法GROA为MTROC查询提供一个全局近似最优解,使用真实和合成数据集对文中提出的算法的有效性和可扩展性进行分析评估,实验结果表明3种算法都能有效地完成MTROC查询,其中GROA算法可扩展性最好,而R(II)Greedy算法返回的路线质量最高。
作者其他论文
An efficient approach for continuous density queries.Wen, Jie;Meng, Xiaofeng;Hao, Xing,等.FRONTIERS OF COMPUTER SCIENCE.2012,6(5),581-595.
差分隐私保护下一种精确挖掘top-k频繁模式方法.张啸剑;王淼;孟小峰.计算机研究与发展.2014,51(1),104-114.
大规模图数据可达性索引技术:现状与展望.富丽贞;孟小峰.计算机研究与发展.2015,52(1),116-129.
海量高维向量的并行Top-k连接查询.马友忠;慈祥;孟小峰.计算机学报.2015,38(1),86-98.
基于小数据的在线用户兴趣长程演化研究.李勇;孟小峰;刘继,等.计算机研究与发展.2015,779-788.
