Uber H3 - 육각형 계층의 공간 인덱스

프로젝트에 Uber H3을 적용하면서 이게 무엇인지에 대해 정리한 글입니다.

Uber H3이 유용한 상황

1. 특정 공간에 대푯값 하나만 있으면 되는 경우(좌표계 정규화)
2. 특정 구역을 채우고 싶은 경우
3. 어떤 구역에 진입했을 때, 그 주변의 데이터를 얻고 싶은데 주변의 기준이 애매한 경우
4. ST_Intersects 같은 공간 쿼리의 비용이 무거운 경우
5. 겹침, 누락에 대한 손실을 최소화 하고 싶을 때

2번의 경우 google S2가 유용할 수 있다.
배달의민족에서 이걸 사용해 문제를 해결한 글이 있다.
(https://techblog.woowahan.com/2717/)

Uber H3란?

https://www.uber.com/en-us/blog/h3/

• 지구를 식별 가능한 육각형 형태로 나눈 형태
• 각 육각형 셸마다 64-bit 정수 형태의 고유한 값이 있다.
• 육각형 크기는 15단계까지 있고, 단계 숫자가 클수록 육각형 크기가 작다.
  (1단계 크기 > 15단계 크기)

좌표계 정규화

https://www.uber.com/en-us/blog/h3/

어떤 값을 계산할 때, 좌표 데이터 하나하나 가지고 계산을 하는 것이 훨씬 정확하지만
인프라 대비 처리할 좌표 데이터가 많거나 중복되는 값이 많은 경우 육각형 셸로 정규화를 하는 것이 유용할 수 있다.

 

실제로 우리 프로젝트에선 지형 높이 좌표가 3억 개로, 42GB의 공간을 차지했는데
10단계 육각형 셀로 정규화를 한 결과 2천만 개로 2GB 공간만 사용하게 됐다.

탐색 단순화

https://www.uber.com/en-us/blog/h3/

4각형으로 지도를 나누면 주변을 탐색하기 위해 8방향을 탐색해야 하지만
6각형의 경우 6방향만 보면 되기 때문에 적은 비용으로 주변을 탐색할 수 있다.
(uber h3에서 주변 셀 인덱스를 찾아주는 함수가 있다.)

Uber H3 환경 구성

Postgre SQL

2022.11에 공식적으로 지원을 시작했다.

https://postgis.net/windows_downloads/

기존에는 깃헙에서 따로 받아서 설치를 해야 했는데, 리눅스만 지원을 해서 윈도우는 사용하는 것이 어려웠다.
코드 레벨에서 처리가 가능하기 때문에 SQL에 꼭 써야 하는 상황이 아니면
굳이 DB까지 적용할 필요는 없다고 생각한다.

기타 언어

https://h3geo.org/docs/installation
java, python, JS에 라이브러리를 제공한다.
이 외는 깃허브에서 각자 설치해야 한다.

참고 자료

https://h3geo.org/

H3 | H3

https://www.uber.com/en-us/blog/h3/

H3: Uber’s Hexagonal Hierarchical Spatial Index

https://zzsza.github.io/data/2019/03/31/uber-h3/

Uber H3 : 육각형 계층의 인덱스