Uber H3을 적용해 좌표 데이터 용량 20배 줄이기

개선된 결과를 먼저 말하자면
42GB의 높이 데이터 -> 2GB
서울시 시군구 단위 도로 데이터 계산 시간 20초 -> 1.2초

수행 시간의 경우 i5, 8GB인 16년도 그램으로 진행했기 때문에
고사양 컴퓨터라면 더 높은 성능을 볼 수 있다.

프로젝트 상황

도로 주변의 높이 정보를 가지고 해당 도로에 생기는 음영도를 계산해야 했다.
사용된 데이터는 다음과 같다.

1. 전국 도로 데이터 (130만 개, 1.3GB)
2. 전국 DSM 데이터(높이 데이터) (3억 개, 42GB)

여기서 높이 데이터의 경우 중복되거나 비슷한 높이를 가지는 것들이 많았다.

반만 해결된 속도 문제

이전 글에서 Polygon 재구성을 통해 I/O 연산을 줄였다.
추가로 클러스터 인덱싱을 적용하고, 시도 단위로 테이블을 분리한 결과
30초 -> 20초로 속도를 개선했지만, 데이터 재구성만으론 20초 이상으로 줄일 수 없었다.

 

물론, 데이터베이스의 자원을 늘리면 해결할 수 있지만
개발자다운 문제 해결은 아니라고 생각했다.

좌표 체계 변경

쿼리 플랜 조회 결과 I/O 작업은 눈에 띄게 줄었지만
공간 쿼리를 이용한 좌표 교차 여부 계산에서 병목이 발생한 것을 확인했다.
공간 쿼리의 복잡한 기하학 연산 + 실수 데이터로 인해 cpu intensive 가 커진다는 것을 확인했다.
따라서, 공간 쿼리를 사용하지 않고 교차 여부를 계산하거나, 실수 데이터를 정수로 바꿀 수 있는 방법을 찾아야 했다.

좌표계 정규화

검색해 본 결과 geoHash를 통해 일정 범위 내의 좌표를 16진수 값으로 바꿀 수 있단 것을 발견했다.

마침 우리 DSM 데이터도 비슷한 높이 값들이 몰려있는 형태였기 때문에, 정규화를 해 평균을 내면 되겠단 생각이 들었다.

 

하지만, geoHash는 정확도가 떨어진단 문제가 있어 선택할 수 없었다.

다른 기업들은 어떤 방식으로 좌표계를 정규화 했는지 찾아봤고, 그 결과 Google S2와 Uber H3을 알게 됐다.

우리는 Uber H3을 선택했다.

왜?

1. 탐색 횟수가 적었다.

기존 HillShade 알고리즘은 3*3 격자 기준 8방향을 봐야 한다.
Google S2 역시 사각형 형태였기 때문에, 기존 알고리즘 식을 적용해도 됐다.

하지만, Uber H3의 경우 6방향만 보면 됐기 때문에, 조금이라도 탐색 비용을 줄이고 싶었다.

 

2. Uber H3 관련 논문에 전용 HillShade 계산식이 있었다.

우리 프로젝트는 단순히 탐색만 하는 게 아니라, 계산도 해야 했다.

따라서, 6각형 기준 HillShade 계산이 필요했는데, 마침 여기에 관한 논문을 발견했다.

기존 체계와 동일한 결과를 보였기 때문에 Uber H3을 채택했다.

 

3. 왜곡이 적었다.

Uber를 적용하기 전에는 사각형으로 그리드를 나누는 것에 대한 기준을 임의로 정했기 때문에

겹치거나 누락되는 부분에 대한 검증과 처리가 매우 어려웠다.

그리고 Google S2에선 균일한 크기를 보장하지 않는 문제가 있다는 것을 알았다.

우리는 특정 영역을 덮는 것이 아니라. 균일한 그리드를 가지고 계산을 해야 해서 그리드간 균일한 크기를 보장하는 Uber H3이 우리 프로젝트에 적합하다 생각했다..

Uber H3 적용

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

개발 docs: https://h3geo.org/

영어 읽는게 어렵다면 https://zzsza.github.io/data/2019/03/31/uber-h3/
정리가 무척 잘 돼있다.

 

여기서 Uber H3에 대해 서술하는건 무척 길고 지루하기 때문에 3줄로 정리하면

1. DSM 데이터들을 그리드 셀에 정규화
2. 각 그리드 셀은 long 타입의 고윳값을 갖고 있음
3. 좌표 간 비교가 아닌, 셀의 고윳값만 보고 교차 유무 확인 가능

여기서 좌표 데이터 정규화가 어떤식으로 되는지 공식 사이트를 기준으로 설명하면 아래와 같다.

각 위경도 좌표들은 반드시 특정 셀 안에 있을 것이고
uber에서 제공하는 라이브러리를 통해 해당 좌표가 어느 셀에 있는지를 찾을 수 있다.

이로서 초기 데이터 세팅을 제외하고는 API 단에서 공간 쿼리를 더이상 사용하지 않게 됐다.

프로젝트에 적용한 형태

왼쪽은 서울 강동구의 도로 데이터
오른쪽은 서울 강동구의 지형 데이터를 Uber H3으로 정규화해 도색화한 형태다.

두 데이터를 합쳐서 도로의 음영도를 계산한 결과는 다음과 같다.

종합하면..

1. DSM 데이터 저장 용량을 42GB -> 2GB 로 단축
2. 공간 쿼리를 사용하지 않아, 20초 걸리던 서울시 시군구 도로 계산을 1200ms대로 단축
3. 검증된 알고리즘으로 정규화를 했기 때문에, 프로젝트 확장성 증가

Reference

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

H3: Uber’s Hexagonal Hierarchical Spatial Index

https://h3geo.org/

H3 | H3

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

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

https://www.sciencedirect.com/science/article/pii/S1569843222001765

Multi-resolution topographic analysis in hexagonal Discrete Global Grid Systems