• Uber의 그리드 시스템인 H3에 대한 글입니다

---

그리드 시스템

• Grid 시스템은 대용량 데이터를 분석하고, 지구의 영역을 구분 가능한 그리드셀로 분할할 때 중요
  • 한국 같은 경우 행정 구역 단위가 있지만(시군구동…) 이 단위는 행정을 위한 단위기 때문에 분석시 유용하지 않음
  • 강남구는 생각보다 길고, 큼. 강남역 왼쪽은 서초구
• 우버에선 ride price과 dispatch을 효율적으로 최적화하기 위해 그리드 시스템인 H3을 개발하고 오픈소스로 공개함

유튜브 영상

• H3 Youtube
• Surge Pricing 하며 겪은 이슈
  • 우버에서 처음엔 도시 단위로 오퍼레이션 했는데, Boundary Effect가 생김
    • Surge Cliffs에서 취소가 생김
  • Pantom Demand: 유령 수요(너무 넓은 지역)
  • 프랑스는 도시가 매우 복잡하고 잘게 쪼개져 있음
  • 도시보다 작은 단위가 필요함을 깨달음
• 왜 육각형(헥사곤)을 사용했는가?
  • Smooth gradients of demand를 구현할 수 있음
  • Clear center of demand
  • Dynamic neighborhoods
  • 각 육각형끼리 거리가 동일함(반면, geohash 같은 사각형은 좌우상하와 대각선의 거리가 다름)
  • 아래 관점으로 여러 실험
    • Neighbor Traversal(이웃 순회)
      • 
    • Subdivision(재조합)
      • 
      • 사각형이 완벽하게 재조합이 되나, 헥사곤은 그렇진 않음. 우버는 완전 똑같을 필요는 없다고 함(약간의 에러를 감수)
      • 
    • Distortion(왜곡)
      • 헥사곤을 선택한 중요한 이유 중 하나
      • 지구는 sphere(구체)고, 평평하지 않음. 그러나 grid는 평평함. Map Projection을 통해 평평해짐
      • 
• 
• H3를 사용하면 지리 데이터를 분석해 여러 결정을 내릴 수 있음

그리드를 사용한 분석 사례

• 매 순간 라이더가 라이딩을 요청하고, 운전자는 여행을 시작, 배고픈 사용자는 음식을 요청
  • 각 이벤트는 특정 위치에서 발생
• 이런 이벤트를 분석해 시장에 대해 더 잘 이해하고 최적화할 수 있음
• 도시의 특정 지역에서 공급보다 수요가 많아 가격을 조정하거나 특정 드라이버에게 가까운 거리에 승차 요청이 있다고 알릴 수 있음
• 도시 전체 데이터를 분석해야 하고, 미세한 단위로 수행되어야 함
• 헥사곤은 quantization error를 최소화함

H3

• Hexagonal global grid system의 장점 + hierarchical indexing 시스템을 결합하기 위해 H3을 만듬
• 지구상 3차원 위치에서 2차원 점으로 이동하려면 투영(Projection)이 필요
  • Mercator Projection이 유명한데, 크기 왜곡이 발생해 셀의 영역이 달라짐
    • 정사각형 그리드는 여러 계수가 필요로 함
  • 결국 지도 투영은 이십면체(Icosahedron)를 중심으로 하는 gnomonic projection을 사용함
    • 20면체는 다양한 방법으로 펼쳐져 2차원 지도를 생성할 수 있으나, H3는 전개하지 않고 20 면에 그리드를 배치해 geodesic discrete global grid 시스템을 만듬
• 육각형
  • 육각형은 중심점과 이웃 점 사이에 단 하나의 거리를 가지고 있음
  • 그라디언트에 대한 분석/스무딩을 단순화함
• H3 그리드
  • 122개의 기본 셀을 지구상에 배치하고 한 면에 10개의 셀을 배치해 구성함
  • 16개의 해상도(resolution)을 지원
• 
• 계층적 특성으로 인덱스의 해상도를 효율적으로 자르고 복구할 수 있음
• 육각형 색인은 64 비트 정수로 표현됨
• 육각형의 중심에서 주위 육각형 어디로 움직여도 동일한 거리를 이동함(지오해시는 방향에 따라 다름)

H3 사용하기

• Python
• h3-py

• cc, make, cmake가 깔려있는지 확인

    which cc
    /usr/bin/cc
    which make
    /usr/bin/make
    which cmake
    /usr/bin/cmake
  

• 설치

    pip3 install h3
  

• geo_to_h3 함수
  • 위도, 경도, 해상도를 통해 h3 인덱스를 반환하는 함수
  • arg : lat 위도, lng 경도, hex resolution

    from h3 import h3
    h3_address = h3.geo_to_h3(37.3615593, -122.0553238, 5)
  

• h3_to_geo 함수
  • h3 인덱스를 통해 헥사곤의 중심점(lat, lng)을 반환하는 함수

    hex_center_coordinates = h3.h3_to_geo(h3_address)
  

• h3_to_geo_boundary 함수
  • h3 인덱스를 통해 헥사곤의 boundary를 반환하는 함수

    hex_boundary = h3.h3_to_geo_boundary(h3_address)
  

• k_ring_distance 함수
  • h3 인덱스를 통해 거리가 k 안에 있는 h3 인덱스를 반환하는 함수

    h3.k_ring_distances(h3_address, 4)
  

• Folium과 결합해 Jupyter Notebook에서 사용하는 예시
• SQL에서 사용하고 싶으면, UDF를 만들어서 사용할 수 있음
• H3를 토대로 나온 데이터를 kepler.gl에서 시각화할 수 있음
• 관련 블로그 글 : Uber Kepler.gl : 지리 데이터 시각화 도구

Reference

• H3: Uber’s Hexagonal Hierarchical Spatial Index
• H3 Github
• h3-py Github
• H3 Youtube

카일스쿨 유튜브 채널을 만들었습니다. 데이터 사이언스, 성장, 리더십, BigQuery 등을 이야기할 예정이니, 관심 있으시면 구독 부탁드립니다 :)

PM을 위한 데이터 리터러시 강의를 만들었습니다. 문제 정의, 지표, 실험 설계, 문화 만들기, 로그 설계, 회고 등을 담은 강의입니다

이 글이 도움이 되셨거나 다양한 의견이 있다면 댓글 부탁드립니다 :)