微信服务号

微信订阅号

2025年3月30日 20:35 星期日
首页 > 过刊浏览>2018年第29卷第11期 >3500-3516. DOI:10.13328/j.cnki.jos.005297
PDF HTML阅读 XML下载 导出引用 引用提醒
基于偏好的个性化路网匹配算法
作者:
作者简介:

高需(1980-),男,河南南阳人,博士,讲师,CCF专业会员,主要研究领域为时空数据管理,时空数据挖掘,大数据存储、查询和分析;丁治明(1966-),男,博士,教授,博士生导师,CCF高级会员,主要研究领域为数据库与知识库系统,时空数据管理,物联网,云计算,大数据;武延军(1979-),男,博士,研究员,博士生导师,CCF高级会员,主要研究领域为操作系统,系统安全;陈军成(1980-),男,博士,讲师,CCF专业会员,主要研究领域为时空数据管理,时空数据挖掘,大数据存储、查询和分析;郭黎敏(1984-),女,博士,讲师,CCF专业会员,主要研究领域为时空数据管理,时空数据挖掘,大数据存储、查询和分析.

通讯作者:

高需,E-mail:gaoxu@nfs.iscas.ac.cn

基金项目:

国家自然科学基金（61402449，91546111）；中国科学院战略性科技先导专项课题（XDA06010600）；北京市教委重点项目（KZ201610005009）


Personalized Map-Matching Algorithm Based on Driving Preference
Author:
Fund Project:

National Natural Science Foundation of China (61402449, 91546111); Strategic Priority Research Program of the Chinese Academy of Sciences (XDA06010600); Key Project of Beijing Municipal Education Commission (KZ201610005009)

  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [40]
    • |
  • 相似文献 [20]
    • | | |
  • 文章评论
    摘要:

    定位技术的普遍应用，使得随时随地获取个人位置成为可能，进一步推动了基于位置的服务等新型应用的发展，产生了海量轨迹数据.精确的路网匹配对提高这些新型应用的服务质量具有重要的研究意义，然而受众多因素的影响，大部分轨迹的采样率较低，比如由签到类应用或低功耗设备生成的低采样轨迹，给路网匹配带来了巨大的挑战.研究基于偏好的个性化路网匹配（driving preference based personalized map-matching，简称DPMM），提出了在动态道路交通网络中的用户驾驶偏好模型.基于该模型，提出了两阶段路网匹配算法：局部匹配搜索用户最可能采用的几条局部Skyline路径；设计了全局匹配的动态规划算法，该算法返回在用户驾驶偏好下最可能的多条全局路径作为最终匹配结果.实验结果充分表明，该方法是有效的和高效的，具有一定的使用价值.

    Abstract:

    With the increasing proliferation of position technologies, there comes huge volumes of trajectory data, which are used in many modern applications such as path planning and location based services. Accurate road network matching can improve the service quality of these new applications. However, the low sampling trajectories bring a major challenge for map-matching. This paper studies the problem of matching individual law-sampling trajectory to a dynamic multi-criteria road network based on user's driving preferences. First, a driving preference model in the dynamic road traffic network is proposed. Based on this model, a two-stage map-matching algorithm is developed. While local matching searches multiple local likely Skyline paths, a global matching dynamic programming algorithm is designed and the most probable k global paths are selected as the matching result. Experiments show that the proposed method is effective and efficient.

    参考文献
    [1] Newson P, Krumm J. Hidden Markov map matching through noise and sparseness. In:Proc. of the GIS 2009. 2009. 336-343.
    [2] Prithu B, Sayan R, Sriram R. Inferring uncertain trajectories from partial observations. In:Proc. of the ICDM 2014. 2014. 30-39.
    [3] Wu H, Mao JY, Sun WW, Zheng BH, Zhang HY, Chen ZY, Wang W. Probabilistic robust route recovery with spatio-temporal dynamics. In:Proc. of the 22nd ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. 2016. 1915-1924.
    [4] Zheng K, Zheng Y, Xie X, Zhou XF. Reducing uncertainty of low-sampling-rate trajectories. In:Proc. of the 28th Int'l Conf. on Data Engineering. 2012. 1144-1155.
    [5] Ceikute V, Jensen CS. Routing service quality local driver behavior versus routing services. In:Proc. of the 14th Int'l Conf. on Mobile Data Management. 2013. 97-106.
    [6] White CE, Bernstein D, Alain LK. Some map-matching algorithms for personal navigation assistants. In:Proc. of the Transportation Research Part C8. 2000. 91-108.
    [7] Dai J, Ding ZM, Xu J. Context-Based moving object trajectory uncertainty reduction and ranking in road network. Journal of Computer Science and Technology, 2016,31(1):167-184.
    [8] Meng Y. Improved Positioning of land vehicle in ITS using digital map and other accessory information[Ph.D. Thesis]. Hong Kong:Department of Land Surveying & Geo-Informatics, Hong Kong Polytechnic University, 2006.
    [9] Yin HB, Wolfson O. A weight-based map matching method in moving objects databases. In:Proc. of the Int'l Conf. on Scientific and Statistical Database Management (SSDBM 2004), Vol.16. 2004. 437-410.
    [10] Yuan J, Zheng Y, Zhang C, Xie X, Sun GZ. An interactive-voting based map matching algorithm. In Proc. of the 11th Int'l Conf. on Mobile Data Management (MDM 2010). 2010. 43-52.
    [11] Lou Y, Zhang C, Zheng Y, Xie X, Wang W, Huang Y. Map-Matching for low-sampling-rate GPS trajectories. In:Proc. of the 17th ACM SIGSPATIAL Int'l Conf. on Advances in Geographic Informathin System. 2009. 352-361.
    [12] Raymond R, Morimura T, Osogami T, Hirosue N. Map matching with hidden Markov model on sampled road network. In:Proc. of the 21st Int'l Conf. on Pattern Recognition (ICPR 2012). 2012. 2242-2245.
    [13] Goh CY, Dauwels J, Mitrovic N, Asif MT, Oran A, Jaillet P. Online map-matching based on Hidden Markov model for real-time traffic sensing applications. In:Proc. of the 15th Int'l Conf. on Intelligent Transportation Systems. 2012. 776-781.
    [14] Ochieng WY, Quddus MA, Noland RB. Map-Matching in complex urban road networks. Journal of Cartography, 2004,55(2):1-18.
    [15] Brakatsoulas R, Pfoser D, Salas R, Wenk C. On map-matching vehicle tracking data. In:Proc. of the VLDB 2005. 2005. 852-864.
    [16] González MC, Hidalgo CA, et al. Understanding individual human mobility patterns. Nature, 2008,453(7196):779-782.
    [17] Li Y, Huang QX, Michael K, Zhang L, Leonidas G. Large-Scale joint map matching of GPS traces. In:Proc. of the 21st ACM SIGSPATIAL Int'l Conf. on Advances in Geographic Information Systems (GIS 2013). 2013. 214-223.
    [18] Javanmard A, Haridasan M, Zhang L. Multi-Track map matching. In:Proc. of the GIS 2012. 2012. 394-397.
    [19] Chang KP, Wei LY, Ling Y, Yeh MY, Peng WC. Discovering personalized routes from trajectories. In:Proc of the 3rd ACM SIGSPATIAL Int'l Workshop on Location-Based Social Networks. 2011. 33-40.
    [20] Silva ER, Souza C, Paiva AC. Personalized path finding in road networks. In:Proc. of the NCM. 2008. 586-591.
    [21] Balteanu A, Jossè G, Schubert M. Mining driving preferences in multi-cost networks. In:Proc. of the SSTD. 2013. 74-91.
    [22] Yang B, Guo CJ, Ma Y, Jensen CS. Toward personalized, context-aware routing. The VLDB Journal, 2015,25(2):279-318.
    [23] Dai J, Yang B, Guo CJ, Ding DZ. Personalized route recommendation using big trajectory data. In:Proc. of the Int'l Conf. on Data Engineering. 2015. 543-554.
    [24] Yang YJ, Gao H, Li JZ. Optimal path query based on cost function over multi-cost graphs. Chinese Journal of Computers, 2012, 35(10):2147-2158(in Chinese with English abstract).
    [25] Wei XJ, Yang J, Li CP, Chen H. Skyline query processing. Ruan Jian Xue Bao/Journal of Software, 2008,19(6):1386-1400(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/19/1386.htm[doi:10.3724/SP.J.1001.2008.01386]
    [26] Huang ZH, Xiang Y, Xue YS, Liu XL. An efficient method for processing skyline queries. Journal of Computer Research and Development, 2010,47(11):1947-1953(in Chinese with English abstract).
    [27] Kriegel HP, Renz M, Schubert M. Route skyline queries:A multi-preference path planning approach. In:Proc. of the Int'l Conf. Data Engineering. 2010. 261-272.
    [28] Shekelyan M, Josse G, Schubert M. Linear path skylines in multicriteria networks. In:Proc. of the ICDE 2015. 2015. 459-470.
    [29] Yang B, Guo CJ, Jensen CS. Travel cost inference from sparse, spatio-temporally correlated time series using Markov models. Proc. of the VLDB Endowment, 2013,6(9):769-780.
    [30] Orda A, Rom R. Shortest-Path and minimum-delay algorithms in networks with time-dependent edge-length. Journal of ACM, 1997,37(3):607-625.
    [31] Ester M, Kriegel HP, Sander J, Xu XW. A density-based algorithm for discovering clusters in large spatial databases with noise. In:Proc. of the 2nd Int'l Conf. on Knowledge Discovery and Data Mining. 1996. 226-231.
    [32] Rokach L, Oded M. Clustering Methods. Data Mining and Knowledge Discovery Handbook. Springer-Verlag, 2005. 321-352.
    [33] Bishop CM. Pattern Recognition and Machine Learning. New York:Springer-Verlag, 2006.
    [34] Bentley JL, Kung HT. On the average number of maxima in a set of vectors and applications. Journal of the Association for Computing Machinery, 1978,25(4):536-543.
    [35] Serafini P. Some considerations about computational complexity for multiobjective combinatorial problems. Recent Advances and Historical Development of Vector Optimization, 1986,294:222-231.
    [36] Rakha H, Ahn K, Trani A. Development of VT-micro model for estimating hot stabilized light duty vehicle and truck emission. Transportation Research Part D:Transportation Environment, 2004,9(1):49-74.
    附中文参考文献:
    [24] 杨雅君,高宏,李建中.多维代价图模型上最优路径查询问题的研究.计算机学报,2012,35(10):2147-2158.
    [25] 魏小娟,杨婧,李翠平,陈红.Skyline查询处理.软件学报,2008,19(6):1386-1400. http://www.jos.org.cn/1000-9825/19/1386.htm[doi:10.3724/SP.J.1001.2008.01386]
    [26] 黄振华,向阳,薛永生,刘啸岭.一种处理Skyline查询的有效方法.计算机研究与发展,2010,47(11):1947-1953.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

高需,武延军,郭黎敏,丁治明,陈军成.基于偏好的个性化路网匹配算法.软件学报,2018,29(11):3500-3516

复制
分享
文章指标
  • 点击次数:3105
  • 下载次数: 4219
  • HTML阅读次数: 1860
  • 引用次数: 0
历史
  • 收稿日期:2017-01-25
  • 最后修改日期:2017-03-12
  • 在线发布日期: 2018-04-16
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19754391位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号