On Efficient Map-Matching According to Intersections You Pass By

详细信息    查看全文

• 作者：Yaguang Li (21) (23)
  Chengfei Liu (22)
  Kuien Liu (21)
  Jiajie Xu (21)
  Fengcheng He (21) (23)
  Zhiming Ding (21)
  
• 关键词：Efficient Map ; matching ; Multi ; Hypothesis Technique
• 刊名：Lecture Notes in Computer Science
• 出版年：2013
• 出版时间：2013
• 年：2013
• 卷：8056
• 期：1
• 页码：57-64
• 全文大小：490KB
• 参考文献：1. Liu, K., Deng, K., Ding, Z., Li, M., Zhou, X.: Moir/mt: Monitoring large-scale road network traffic in real-time. PVLDB聽2(2), 1538鈥?541 (2009)
  2. Gonzalez, H., Han, J., Li, X., Myslinska, M., Sondag, J.P.: Adaptive fastest path computation on a road network: a traffic mining approach. In: VLDB, pp. 794鈥?05 (2007)
  3. Li, X., Han, J., Lee, J.-G., Gonzalez, H.: Traffic density-based discovery of hot routes in road networks. In: Papadias, D., Zhang, D., Kollios, G. (eds.) SSTD 2007. LNCS, vol.聽4605, pp. 441鈥?59. Springer, Heidelberg (2007) CrossRef
  4. White, C.E., Bernstein, D., Kornhauser, A.L.: Some map matching algorithms for personal navigation assistants. Transportation Research Part C: Emerging Technologies聽8(1-6), 91鈥?08 (2000) CrossRef
  5. Greenfeld, J.S.: Matching gps observations to locations on a digital map. In: Transportation Research Board. Meeting, Washington, D.C (2002)
  6. Lou, Y., Zhang, C., Zheng, Y., Xie, X., Wang, W., Huang, Y.: Map-matching for low-sampling-rate gps trajectories. In: GIS, Seattle, Washington, pp. 352鈥?61 (2009)
  7. Newson, P., Krumm, J.: Hidden markov map matching through noise and sparseness. In: GIS, Seattle, WA, USA, pp. 336鈥?43 (2009)
  8. Zheng, K., Zheng, Y., Xie, X., Zhou, X.: Reducing uncertainty of low-sampling-rate trajectories. In: ICDE, Washington, DC, USA, pp. 1144鈥?155 (2012)
  9. Pink, O., Hummel, B.: A statistical approach to map matching using road network geometry, topology and vehicular motion constraints. In: ITSC, pp. 862鈥?67. IEEE (2008)
  10. Wenk, C., Salas, R., Pfoser, D.: Addressing the need for map-matching speed: Localizing globalb curve-matching algorithms. In: SSDBM, Washington, DC, USA, pp. 379鈥?88 (2006)
  11. Brakatsoulas, S., Pfoser, D., Salas, R., Wenk, C.: On map-matching vehicle tracking data. In: VLDB, Trondheim, Norway, pp. 853鈥?64 (2005)
  12. Quddus, M.A., Ochieng, W.Y., Noland, R.B.: Current map-matching algorithms for transport applications: State-of-the art and future research directions. Transportation Research Part C: Emerging Technologies聽15(5), 312鈥?28 (2007) CrossRef
  13. Syed, S., Cannon, M.: Fuzzy logic based-map matching algorithm for vehicle navigation system in urban canyons. In: National Technical Meeting of The Institute of Navigation, San Diego, CA, pp. 982鈥?93 (2004)
  14. Reid, D.: An algorithm for tracking multiple targets. IEEE Transactions on Automatic Control聽24(6), 843鈥?54 (1979) CrossRef
  15. Pyo, J.S., Shin, D.H., Sung, T.K.: Development of a map matching method using the multiple hypothesis technique. In: Proceedings of 2001 Intelligent Transportation Systems, pp. 23鈥?7. IEEE, Oakland (2001)
  16. Abdallah, F., Nassreddine, G., Denoeux, T.: A multiple-hypothesis map-matching method suitable for weighted and box-shaped state estimation for localization. IEEE Transactions on Intelligent Transportation Systems聽12(4), 1495鈥?510 (2011) CrossRef
  17. Liu, K., Li, Y., He, F., Xu, J., Ding, Z.: Effective map-matching on the most simplified road network. In: GIS, Redondo Beach, CA, USA, pp. 609鈥?12 (2012)
  18. Zhou, J., Golledge, R.: A three-step general map matching method in the gis environment: travel/transportation study perspective. International Journal of Geographical Information System聽8(3), 243鈥?60 (2006)
  19. Alt, H., Guibas, L.: Discrete geometric shapes: Matching, interpolation, and approximation. In: Handbook of Computational Geometry, Amsterdam, pp. 121鈥?53 (1999)
  20. ACM SIGSPATIAL Cup 2012: Training data sets (2012), http://depts.washington.edu/giscup/home
  
• 作者单位：Yaguang Li (21) (23)
  Chengfei Liu (22)
  Kuien Liu (21)
  Jiajie Xu (21)
  Fengcheng He (21) (23)
  Zhiming Ding (21)
  
  21. Institute of Software, Chinese Academy of Sciences, Beijing, 100190, China
  23. University of Chinese Academy of Sciences, Beijing, 100049, China
  22. FICT, Swinburne University of Technology, Australia
  

文摘

Map-matching is a hot research topic as it is essential for Moving Object Database and Intelligent Transport Systems. However, existing map-matching techniques cannot satisfy the increasing requirement of applications with massive trajectory data, e.g., traffic flow analysis and route planning. To handle this problem, we propose an efficient map-matching algorithm called Passby. Instead of matching every single GPS point, we concentrate on those close to intersections and avoid the computation of map-matching on intermediate GPS points. Meanwhile, this efficient method also increases the uncertainty for determining the real route of the moving object due to less availability of trajectory information. To provide accurate matching results in ambiguous situations, e.g., road intersections and parallel paths, we further propose Passby*. It is based on the multi-hypothesis technique and manages to maintain a small but complete set of possible solutions and eventually choose the one with the highest probability. The results of experiments performed on real datasets demonstrate that Passby* is efficient while maintaining the high accuracy.