문제 이해 및 설계 범위 확정

기능 요구사항

지원할 주 단말 : 스마트폰

• 사용자 위치 갱신
• 경로 안내 서비스 (ETA 도착 예정 시간 서비스 포함)
• 지도 표시

비기능 요구사항 및 제약사항

• 정확도 : 사용자에게 잘못된 경로는 안내하면 안됨

• 부드러운 경로 표시 : 클라이언트를 통해 제공되는 경로 안내 용도의 지도는 화면에 아주 부드럽게 표시되고 갱신되어야함

• 데이터 및 배터리 사용량 : 가능한 한 최소한의 데이터와 배터리를 사용해야함

• 일반적으로 널리 통용되는 가용성 및 규모 확장성을 고려해야함

• 지오해싱

  

  • 서울 시청 GeoHash 로 바꿔보기

• 지도표시

  • 지도를 화면에 표시하는데 가장 기본이 되는 개념은 타일
  • 지도 전부를 하나의 이미지로 표시하는 대신, 작은 타일로 쪼개어 표시
  • 사용자가 보는 영역에 관계된 타일만 다운 받아 표시
  • 지도 확대/축소 수준에 따라 다른 종류의 타일을 준비해야함

• 경로 안내 알고리즘을 위한 도로 데이터 처리

  • 다익스트라, A* 알고리즘의 변형이 대부분

  • 모든 경로 탐색 알고리즘에서 교차로를 node, 도로는 edge 로 표현하는 그래프 자료 구조

  • 그래프 크기에 따라 알고리즘의 성능이 좌우되므로 전 세계 도로망을 하나의 그래프로 표현x

    

    • 그래프를 관리 기능 단위로 분할할 필요가 있음

    • 지오해시와 같이 격자로 나누고, 각 격자(타일) 안의 도로망을 node,edge 로 구성된 그래프 자료 구조로 변환

      타일로 나누면 얼마나 좋을까?

    • 각 타일은 edge 가 연결된 타일들에 대해서 참조를 유지

    <aside> 💡

    지도 타일은 PNG 인 반면, 경로 안내 타일은 도로 데이터로 이뤄진 이진 파일임

    </aside>

• 계층적 경로 안내 타일

  

  • 경로 안내를 효율적으로 돌리려면 어느 정도 수준의 정밀도로 해야할지 고려해야함 ⇒ 지번 수준으로 할 경우 그래프가 너무 비대해짐
  • 구체성 정도를 상,중,하 ⇒ 지방도,관할구,도시 정도로 비교하려 안내 타일을 구성하자

개략적 규모 추정

스토리지 추정치

1. 세계 지도

   • 지원하는 확대 수준별로 지도 타일을 한벌씩 두고 모두 보관하는 용량 추정

   • 21번 확대 → 약 4.4조 개의 타일 필요 → 4.4조 * 100KB ⇒ 440PB

     • 한 장당 256*256 픽셀 압축 png → 약 100KB 정도

   • but 90% 는 불필요 지역이므로 높은 비율로 압축 ⇒ 결국 50PB 정도 필요

   • 각 수준 별로 필요 타일 수는 1/4로 줄어듬

     

     • 모두 다 저장되려면 대략 100PB 필요
2. 메타데이터 : 각 지도 타일의 메타데이터는 아주 작아서 추정에서 제외