Geohash란

Gustavo Niemeyer가 개발한 geocoding system으로, geographic location을 문자와 숫자로 이루어진 짧은 string형태로 변환한다. Geohash는 공간을 사각형으로 분할하는 계층적인 공간 테이터 구조다. Geohash는 사용자가 원하는 만큼의 정확도를 구현할 수 있고, 맨 뒤에 글자를 지우는 것만으로 그 크기를 줄일 수 있다. (물론 정확도도 줄어든다.) 비슷한 위치를 가리키는 geohash는 대개 유사한 prefix를 갖고 공통 prefix가 길면 길수록 두 지점의 거리가 가깝다. 2008년에 이 시스템의 공개와 함께 개발자는 http://geohash.org/ 라는 사이트를 공개했다.

Algorithm and example

해쉬를 구하기 위해서 먼저 비트값을 계산해야 한다. 비트는 경도와 위도가 번갈아가면서 나타나고, 첫번째 비트는 항상 경도값에 대한 비트다.

먼저 서울시청의 위경도를 해싱해보자. 서울시청의 위경도는 (37.566300, 126.977946) 이다. 위도의 범위는 -90 ~ 90, 경도의 범위는 -180 ~ 180 이다. 이 때 서울 시청의 경도는 126.977946 으로 경도 구간 -180 ~ 180을 이등분 한 구간 중에 큰 구간 0~180에 위치한다. 그렇다면 첫번째 비트값은 1이 된다. 다음은 위도에 대해서 같은 로직을 적용해 보자. 위도는 -90 ~ 90 을 이등분 한 구간 중에 마찬가지로 큰 구간 0~90에 위치한다. 이제 두번째 비트값은 1이된다. 이제 다시 경도에 대한 비트가 위치할 차례다. 경도의 구간을 0~180이라 보고 다음 비트를 구해보면 90~180에 위치하기 때문에 해시의 세번째 자리 값은 1이다.

이런식으로 비트를 열번째자리까지 완성하면 ‘11100 11110’이라는 비트값을 얻을 수 있다. 이렇게 나온 비트값을 5자리씩 잘라 아래의 base32 map에 대응시키면 ‘wy’ 가 나온다. 해시 길이가 8자리가 될 때까지 이 연산을 반복하면 ‘wydm9qwx’ 이라는 해시값을 얻을 수 있다.

wy와 wydm9qwx가 가리키는 지역을 비교해보자. wy가 가리키는 지역은 위도 33.75 ~ 39.375, 경도 123.75 ~ 135 인 사각형을 가리킨다. 약 ±630km의 오차다. wydm9qwx가 가리키는 지역은 위도 37.565915 ~ 37.566085, 경도 126.97783 ~ 126.97817인 사각형을 가리키며, 약 ±19m의 오차를 갖는다.

hash의 길이에 따른 오차 범위는 아래와 같다.

이렇게 geohash는 한 점을 표기하는 방식이 아니라, 사각형의 구간을 표기하는 방식이다. 그렇기 때문에 해시의 길이가 길어지면 길어질수록 사각형이 더 작아지고 표기하고자 하는 점에 대한 오차를 줄일 수가 있다.

응용

geotagging을 위해 제안되기도 했었다.

geohash를 이용하면 geohash가 가리키는 사각형에 포함된 모든 점들을 index 할 수 있다. 따라서 위도, 경도로 이루어진 index 두개가 아닌 geohash index 하나만으로도 위치에 대한 정보를 indexing 할 수 있다. 또한 이러한 index 구조는 quick-and-dirty proximity search에 사용될 수 있다. 가장 가까운 두 점은 아주 유사한 geohash 값을 갖게 된다.

한계

geohash를 이용하면 prefix를 통해 인접한 두 점을 찾을 수 있다. 하지만 매우 인접한 두 점임에도 불구하고, -180도와 180도가 만나는 지점에서는 전혀 다른 prefix를 갖게 될 수도 있다. 비슷하게 북극과 남극에 위치하는 점들도 다른 prefix를 갖게 될 수 있다.

참고

https://en.wikipedia.org/wiki/Geohash