KIISE Transactions on Computing Practices (정보과학회 컴퓨팅의 실제 논문지)

Korean Institute of Information Scientists and Engineers (한국정보과학회)
권호 표지
DOI QR코드

DOI QR Code

Recommendation of Best Empirical Route Based on Classification of Large Trajectory Data

대용량 경로데이터 분류에 기반한 경험적 최선 경로 추천

  • 이계형 (상명대학교 컴퓨터소프트웨어공학과) ;
  • 조영훈 (상명대학교 컴퓨터소프트웨어공학과) ;
  • 이태호 (상명대학교 컴퓨터소프트웨어공학과) ;
  • 박희민 (상명대학교 컴퓨터소프트웨어공학과)
  • Received : 2014.11.21
  • Accepted : 2015.01.16
  • Published : 2015.02.15
⟨ Previous Next ⟩

Abstract

This paper presents the implementation of a system that recommends empirical best routes based on classification of large trajectory data. As many location-based services are used, we expect the amount of location and trajectory data to become big data. Then, we believe we can extract the best empirical routes from the large trajectory repositories. Large trajectory data is clustered into similar route groups using Hadoop MapReduce framework. Clustered route groups are stored and managed by a DBMS, and thus it supports rapid response to the end-users' request. We aim to find the best routes based on collected real data, not the ideal shortest path on maps. We have implemented 1) an Android application that collects trajectories from users, 2) Apache Hadoop MapReduce program that can cluster large trajectory data, 3) a service application to query start-destination from a web server and to display the recommended routes on mobile phones. We validated our approach using real data we collected for five days and have compared the results with commercial navigation systems. Experimental results show that the empirical best route is better than routes recommended by commercial navigation systems.

위치를 수집할 수 있는 모바일 기기의 확산에 따라 다양한 위치기반서비스들이 개발되어 사용되고 있다. 본 논문에서는 위치기반서비스가 일반화됨에 따라 수집되고 저장되는 경로 데이터의 양이 기하급수적으로 커지고 결국 빅데이터가 될 것이기 때문에 수집된 대용량 경로데이터에서 최선 경로를 찾아 추천해주는 시스템을 제안한다. 대용량 경로 데이터에서 실제 운행 시간 등의 정보를 바탕으로 기존 내비게이션보다 좋은 경로를 추천할 수 있게 된다. 대용량 경로 데이터 처리를 위해 하둡 맵리듀스를 이용해서 분류하고 분류된 경로를 데이터베이스에 저장하여 사용자의 요청에 빠르게 반응할 수 있도록 하였다. 사용자의 요청에 지도상의 최단 경로가 아닌 수집된 경로 기록을 바탕으로 최선 경로를 찾게 되는 것이다. 구현된 전체 시스템은 1) 실제 경로를 수집하기 위한 안드로이드 응용프로그램, 2) 하둡 맵리듀스를 이용해 수집된 경로를 미리 분류해 놓기 위한 분류 엔진, 3) 사용자의 출발지-도착지 요청에 따라 분류된 경로에서 최선 경로를 찾아 사용자에게 돌려주는 웹서버와 안드로이드 클라이언트 서비스 시스템이다. 실제운행 실험을 제안한 방법과 시스템이 실효성이 있음을 보인다.

Keywords

Acknowledgement

Supported by : 상명대학교

References

  1. Apache Hadoop. [online]. Available: http://hadoop.apache.org (downloaded 2014, Aug. 5)
  2. K. Wagstaff, C. Cardie, S. Rogers, and S. Schroedl, "Constrained K-means Clustering with Background Knowledge," International Conference on Machine Learning, pp. 577-584, 2001.
  3. P. S. Bradley, K. P. Bennett, and A. Demiriz, "Constrained k-means clustering," Technical Report MSR-TR-2000-65, Microsoft Research, Redmond, WA, 2000.
  4. H.-W. Yun. "Path based K-means Clustering for RFID Data Sets," Journal of information and communication convergence engineering, Vol. 6, Issue 4, pp. 434-438, Dec. 2008.
  5. J. Lim, K. Kim, J. Kim, H. Oh, S. Yoon, S. Park, S. Yoon, J. Han, K. Bok, J. Yoo, "Design and Implementation of a Realtime Optimal Traffic Route Guidance System Through Big Data Analysis," 2014 Fall Conference of Korea Contents Association, pp. 297-298, 2014.
  6. S. Yang, C. Choi, H. Choi, "Design and Implementation of Vehicle Route Tracking System using Hadoop-Based Bigdata Image Processing," Journal of Digital Contents Society, Vol. 14, No. 4, pp. 447-454, Dec. 2013. https://doi.org/10.9728/dcs.2013.14.4.447
  7. J. Yuan, Y. Zheng, C. Zhang, W. Xie, X. Xie, G. Sun, and Y. Huang, "T-Drive: Driving Directions Based on Taxi Trajectories," ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 99-108, 2010.
  8. Naver Map. [online], Available: http://map.naver.com. (accessed 2014, Nov. 3)
  9. SK Telecom T-Map Navigation. [online]. Available: http://www.tmap.co.kr/tmap2. (accessed 2014, Nov. 3)
  10. B. C. Dean. "Continuous-time dynamic shortest path algorithms. Master's thesis," Massachusetts Institute of Technology, 1999.

Cited by

  1. A Big-Data Trajectory Combination Method for Navigations using Collected Trajectory Data vol.19, pp.2, 2016, https://doi.org/10.9717/kmms.2016.19.2.386