지오해시(geohash)는 Gustavo Niemeyer가 개발하여 퍼블릭 도메인으로 공개한 지오코딩(geocoding) 시스템이다. 지오해시는 공간을 그리드 형태로 분할하는 계층적 공간 데이터 구조로서, Z-order curve, space-filling curve 등과 같은 많은 공간분할 방법중 하나이다.
지오해시는 정밀도를 마음대로 정할 수 있고, 코드의 끝부분 문자를 순차적으로 제거하면 크기를 줄일 수 있는 (정확도도 떨어지는) 등의 특성이 있다.
점진적 정밀도 저감 특성의 결과, 인근한 지역(항상 그런 것은 아님)은 대부분 접두어(코드의 시작부분)이 비슷하다. 즉, 접두어가 비슷한 부분이 많을 수록 두 지점은 서로 근접한다.
서비스(Service)
지오해시 서비스는 http://geohash.org/에서 제공된다. 2008년 2월에 시작된 서비스의 목적은 지구상의 위치를 고유하게 구분할 수 있는 짧은 URL을 제공함으로써, 이메일이나 포럼, 웹사이트 등에서 편리하게 사용할 수 있도록 하는 것이다.
지오해시(Geohash)를 얻으려면 사용자는 지오코딩할 주소나 경위도 좌표를 작은 입력박스(대부분 널리 사용되는 정위도 포맷을 인식함)에 넣고, 요청을 시행하면 된다.
주어진 지오해시에 해당되는 경위도 좌표를 보이는 외에도 geohash.org에서 지오해시를 둘러보는 사용자는 내장된 지도도 볼 수 있고, GPX 파일로도 다운로드 받을 수 있으며, 직접 해당 지점을 특정한 GPS 수신기로 전송할 수 도 있다. 아울러 링크를 외부사이트에 제공하여, 특정 지점 주변의 보다 상세한 내역을 제공할 수 있다.
예를 들어 경위도 57.64911,10.40744 (덴마크 Jutland 반도 끝부분)는 약간 짧은 해시인 u4pruydqqvj로 나온다.
사용(Uses)
지오해시의 중요한 사용처는
- 유일 식별자
- point 자료의 표현 (예를 들어 데이터베이스에서)
지오해시는 아울러 지오태깅의 목적으로도 제안되었다.
지오해시 데이터 구조를 데이터베이스에서 사용하면 두가지 장점이 있다. 첫번째, 지오해시로 인덱싱된 데이터는 주어진 직사각형 면적에 포함되는 모든 점들이 인접해 있는 조각에 들어가게 된다.(이때 조각의 수는 필요한 정밀도 및 지오해시 "fault line"의 존재 여부에 따라 달라진다.) 이는 데이터베이스 시스템에서 매우 유용하다. 하나의 인덱스에 대한 쿼리가 여러개의 인덱스로 구성된 쿼리에 비해 훨씬 쉽고 빠르기 때문이다. 두번째, 이 인덱스 체계는 간이 접근성 검색에 사용할 수 있다는 것이다. 즉, 가까운 점들은 지오해시가 비슷하다.
설계(Design)
해시 값 ezs42를 예로 들어, 지오해시를 십진 경위도로 해석하는 방법을 보이면 아래와 같다.
첫번째 단계는 아래와 같은 문자맵을 사용하여 32진법으로 해시값을 해석하는 것이다.
| Decimal | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Base 32 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | b | c | d | e | f | g | |||
| Decimal | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | |||
| Base 32 | h | j | k | m | n | p | q | r | s | t | u | v | w | x | y | z | |||
이 연산을 적용하면 ezs42는 01101 11111 11000 00100 00010 이된다. 여기에서 맨 왼쪽을 0번째 값이라고 가정하여, 짝수 비트는 경도 코드(0111110000000), 홀수 비트는 위도 코드(101111001001)로 둔다.
이제 각각의 2진 코드는 분할에 사용된다. 좌측부터 우측으로 한 비트씩 사용하여 분할 한다. 위도의 경우 -90부터 +90을 두개로 분할 하면, -90 에서 0, 0 에서 +90까지 2개의 구간이 만들어진다. 위도 첫비트는 1이므로, 높은 구간을 사용하게 된다. 이러한 방식으로 모든 비트를 반복한다. 마지막으로 위도 값은 마지막으로 남은 구간의 중앙값이 된다. 경도도 이와 같은 방식으로 처리하되, 시작구간이 -180 에서 180이라는 것만 다르다.
이러한 절차를 마치면 대략 위도 42.6, 경도 -5.6이 된다.
위도 2진값 101111001001이 42.6이 되는 과정은 다음과 같다. 맨 처음에 위도는 -90에서 90 사이라는 것을 알고 있다. 아무런 비트도 없으니, 위도는 0이라고 할 수 있고 에러는 ±90이다. 첫번째 비트를 사용하면, -90 에서 0 구간인지, 0에서 +90 구간인지 결정할 수 있다. 첫번째 비트가 높은(1) 값이므로, 우리의 위도는 0에서 90사이 어디쯤이라는 것을 알 수 있다. 만약 다른 비트가 없다면 위도는 45라고 가정할 수 있고, 에러는 ±45가 된다.
비트가 하나씩 추가될 수록 이 에러가 반으로 줄어든다. 아래의 표는 각각의 비트의 효과이다. 각 단계에서 관계되는 범위는 초록색으로 강조하였다. 즉 낮은 비트(0)은 아래 구간, 높은 비트(1)은 높은 구간을 선택한다.
끝에서 두번째 열은 위도값(범위의 산술평균)이다. 비트가 추가될 수록 이 값은 점점 더 정확해진다.
| bit | min | mid | max | val | err |
|---|---|---|---|---|---|
| 1 | -90.000 | 0.000 | 90.000 | 45.000 | 45.000 |
| 0 | 0.000 | 45.000 | 90.000 | 22.500 | 22.500 |
| 1 | 0.000 | 22.500 | 45.000 | 33.750 | 11.250 |
| 1 | 22.500 | 33.750 | 45.000 | 39.375 | 5.625 |
| 1 | 33.750 | 39.375 | 45.000 | 42.188 | 2.813 |
| 1 | 39.375 | 42.188 | 45.000 | 43.594 | 1.406 |
| 0 | 42.188 | 43.594 | 45.000 | 42.891 | 0.703 |
| 0 | 42.188 | 42.891 | 43.594 | 42.539 | 0.352 |
| 1 | 42.188 | 42.539 | 42.891 | 42.715 | 0.176 |
| 0 | 42.539 | 42.715 | 42.891 | 42.627 | 0.088 |
| 0 | 42.539 | 42.627 | 42.715 | 42.583 | 0.044 |
| 1 | 42.539 | 42.583 | 42.627 | 42.605 | 0.022 |
(위 표에 있는 숫자들은 보기 편하도록 소수점 세자리에서 반올림하였다.)
최종 값은 아래와 같이 사용하여야 한다.
따라서 42.61에서 42.61 혹은 42.6은 올바르지만, 43은 아니다.
| geohash length | lat bits | lng bits | lat error | lng error | km error |
|---|---|---|---|---|---|
| 1 | 2 | 3 | ± 23 | ± 23 | ± 2500 |
| 2 | 5 | 5 | ± 2.8 | ± 5.6 | ±630 |
| 3 | 7 | 8 | ± 0.70 | ± 0.7 | ±78 |
| 4 | 10 | 10 | ± 0.087 | ± 0.18 | ±20 |
| 5 | 12 | 13 | ± 0.022 | ± 0.022 | ±2.4 |
| 6 | 15 | 15 | ± 0.0027 | ± 0.0055 | ±0.61 |
| 7 | 17 | 18 | ±0.00068 | ±0.00068 | ±0.076 |
| 8 | 20 | 20 | ±0.000085 | ±0.00017 | ±0.019 |
지오해시 알고리듬의 한가지 제한은 공통 접두어를 근거로 점들간의 근접성을 찾고자하는 경우에 발생한다. 서로 근접해 있지만, 자오선을 기준으로 180도 떨어져 있는 경계 위치에서는 전혀 접두어가 다르다. (물리적으로는 근접해 있지만, 경도가 다를 경우) 아울러 북극 및 남극에 가까운 점들의 경우, 지오해시가 매우 다르게 된다.(물리적으로는 근접해있지만, 경도가 다를 경우)
적도(혹은 본초자오선)를 기준으로 양쪽으로 근접한 지역에서도 서로 다른 '반구'에 속하기 때문에 접두어가 공통되지 않는다. 간단히 말해 한 지역의 경도(또는 위도)는 011111.... 이 되고 반대쪽은 100000... 이 되어, 공통 접두어는 없고 대부분의 비트가 반대로 된다. 이러한 현상은 점들을 순서대로 나열할 때 Z-order 커브(보다 적당하게는 N-order visit)에 의존하는 경우에도 볼 수 있다. 인접해 있는 두점이 아주 멀리 떨어져 있을 수 있기 때문이다. 그러나, 공통접두어가 긴 점들은 서로 근접하다는 것은 항상 진실이다.
In order to do a proximity search, one could compute the southwest corner (low geohash with low latitude and longitude) and northeast corner (high geohash with high latitude and longitude) of a bounding box and search for geohashes between those two. This will retrieve all points in the z-order curve between the two corners, which can be far too many points, this also breaks down at the 180 meridians and the poles. Solr uses a filter list of prefixes, by computing the prefixes of the nearest squares close to the geohash
인접 검색을 하기 위해서는 먼저 경계 사각형(Bounding box)의 남서쪽 구석(작은 경위도 값을 가진 작은 지오해시)와 북동쪽 구석(높은 경위도 값을 가진 높은 지오해시)를 계산한 뒤, 이 두 점사이의 지오해시를 검색해야 한다. 이렇게 하면 두 꼭지점 사이에 있는 z-order curve에 있는 모든 점을 추출하여, 너무 많은 점이 될 수도 있지만, 180도 자오선 및 극지방에서 분할된다. Solr 는 지오해시에 인접한 사각형의 접두어를 계산함으로써, 접두어 필터 리스트를 사용한다.????
세번째로 지오해시는 경위도좌표에 기반하므로, 두 지오해시간의 거리는 두 지점간의 경위도 좌표에서의 거리가 되는데, 이는 실제 거리가 아니다. 자세한 사항은 Haversine 식을 볼 것.
다음은 경위도 체계의 비 선형성을 보여주는 예이다.
- 적도에서 경도 1도의 길이는 111.320 km 이지만, 위도 1도의 길이는 110.574km로 약 0.67%의 오차가 있다.
- 위도 30도(중위도)에서 이 오류는 110.852/96.486 = 14.89% 로 커진다.
- 위도 60도(고위도)에서는 111.412/55.800 = 99.67% 가 되며, 극에서는 무한대에 근접한다.
참고로 이러한 제한은 지오해시 때문이 아니라, 경위도 좌표체계 때문으로, 구면(비선형, 나머지 연산과 비슷하게 값의 겹침 등)상의 좌표를 2차원 좌표로 사상시키는 데 따르는 어려움과 이차원 공간을 균등하게 탐사하는 데 따른 어려움 때문이다. 첫번째는 지리좌표계와 지도투영에 관련된 사항이며, 두번째는 힐버트(Hilbert) 곡선과 z-order curve에 의한 문제이다. 점간의 거리가 선형으로 표현되는 좌표계를 사용하고, 경계에서 중복되지 않는다면 균등하게 탐사하는 것이 가능해져 지오해시를 그러한 좌표계에 적용할 경우 위에서 언급한 제한은 발생하지 않는다.
지오해시를 직각 좌표계를 사용하는 지역에도 적용할 수 있지만, 그 경우 해당 좌표계가 적용하는 지역에서만 사용할 수 있다.
이러한 문제에도 불구하고, 여러가지 회피책이 있으며, 근접성 검색을 구현할 수 있도록 Elasticsearch, MongoDB, HBase, Accumulo 등에서 이 알고리듬을 성공적으로 적용해 왔다.
지오해시를 데이터베이스에서 문자열로 저장하는 대신 다른 대안으로서 위치코드(Locational codes)가 있으며, 이는 공간키(Spatial Key)와 쿼드타일(QuadTiles)과 비슷하게 부른다.
원문 : https://en.wikipedia.org/wiki/Geohash
댓글을 달아 주세요