Geohash를 이용한 좌표기반 시스템 개선

<개요>

- 일반적으로 많이 사용하는 지리좌표계는 위도, 경도로 이루어져있다.

  이는 실제 정확한 위치를 측정하는 것이 목표이기 때문에 소수점 표현에 제한이 없이 무한하게 표현한다. (보통 6자리)

- 특정 영역(Area) 에 대한 처리를 하기에는 적합하지 않기 때문에, 영역기반의 검색/표현에 적합한 구조가 필요하다.

- 즉, (무한->유한) 한정된 공간내에서 필요한 만큼만의 데이터(의미있는 데이터) 를 관리할 수 있도록 개선이 필요하다.

 

<내용>

- 지도뷰를 기반으로 하는 시스템에서 좌표를 기반으로 검색하는 것은 속도/공간에서 많은 손해를 본다. (대부분 특정영역 내 검색)

- 지도내에서 살짝만 움직여도 소수점 값이 변경되는데 실제 서비스내에서 의미를 갖는 값으로 보기 어려울때가 있다.

- 또한 Round처리를 통해서 어느정도 고정적으로 표현할 수는 있으나 연산에 역시 불편함이 있다.

- 지역내 검색이나 가까운 위치 등을 계산할때도 복잡한 수식을 사용해야 하며 Index 나 Key를 사용하기에 쉬운 구조는 아니다.

 

<GeoHash Concept>

전 세계를 잘라내기

- 이를 보완하기 위해서 전 세계 지역을 특정영역 단위로 잘라낸 것이 GeoHash의 기본사상이다.

- 좌표값을 특정 해시값으로 변경하여 지역기반 검색 이나 캐시 활용에서 편리하게 활용 할 수 있다. ( f(x) -> y )

- GeoHash의 결과는 특정 영역(Area) 이다.  지점(Point)이 아니다.

 

<GeoHash Algorithm>

- 알고리즘은 간단히 설명하면 Index Tree, Binary Search등과 비슷하다.

1. Latitude (-90 ~ 90), Longitude (-180 ~ 180) 범위 내에서 Binary Search를 수행한다.

2. 왼쪽에 속하면 0, 오른쪽에 속하면 1 이다. (bits)

3. 다음 구간으로 이동하여 1,2를 반복한다.

Longtitude / Latitude 변환

4. 이렇게 해서 얻은 각 bit를 하나씩 꺼내어 결합한다.

- Geohash level이 높아질 수록 더 자세한 위치를 표현해야 하기 때문에, 더 많은 bit를 필요로 하게 된다.

- latitude 1개, longitude 1개 순으로 번갈아가면서 결합한다.

 (Longitude의 값의 범위가 더 넓기 때문에 Level에 따라서 Bit가 1개 더 필요한 경우가 있고, 이 때 마지막 두 개를 연속해서 붙인다. )

 

5. 마지막으로 얻은 bits를 5개씩 나눠서 BASE32 encoding으로 변환하여 알파벳 문자를 얻을 수 있다. (2^5=32)

BASE32

6. Binary Search를 많이 반복할 수록 더욱 정확한 숫자를 얻게 되고, GeoHash 의 길이는 길어진다고 볼 수 있다.

 - GeoHash Stirng의 길이가 GeoHash Level로 생각하면 된다.

 

7. 위의 연산을 통해서 얻은 결과값은 다음과 같다.

위/경도 좌표 (37.385595, 127.122759) -> Level 2 (wy), Level 8 (wydkstzf)

위/경도 좌표 (37.384887, 127.123689) -> Level 2 (wy), Level 8 (wydksv8w)

 

*장점

- 매우 길고 큰 값을 상대적으로 짧고 저장공간을 적게 차지하는 String으로 바꿀 수 있게 된다. (Hash의 기본사상)

- GeoHash알고리즘의 특성상 prefix비교를 통해서 이웃인지 판별할 수 있다.

 예를 들어서 GeoHash를 통해서 gbsuv (Level 5)값을 얻은경우 아래의 지역들은  Neighbours 로 판별할 수 있다.

gbsvh	gbsvj	gbsvn
gbsuu	gbsuv	gbsuy
gbsus	gbsut	gbsuw

 

<코드>

전체코드는 다음 위치에서 확인 가능합니다.

https://github.com/ggthename/geohash

GitHub - ggthename/geohash: get a geohash value from a coordinate (latitude,longitude)

위도/경도 기반의 좌표

GeoHash Level에 따른 Binary Search 응용

 

<정리>

- 이를 통해서 특정 지역 내의 데이터값을 관리할때 Key값으로 사용할 수 있다.

 e.g) 특정지역내 위치한 상점 검색, 50 x 50내 인구 등

 

- 해당 지역간의 인접성도 복잡한 계산없이 판별할 수 있다.

 e.g) 현재 위치에서 10km내 이동가능한 곳에 있는 주유소 위치 등

 

- 최대 Level 12로 32.2mm x 18.6mm의 지역까지 표현할 수 있다. 일반적으로 Level 9 까지 사용한다.

 

<참고>

- https://en.wikipedia.org/wiki/Geohash#Technical_description

Geohash - Wikipedia

- https://en.wikipedia.org/wiki/Base32

Base32 - Wikipedia

https://www.movable-type.co.uk/scripts/geohash.html

Geohash encoding/decoding