Geohash

Recommanded Free YOUTUBE Lecture: <% selectedImage[1] %>

yundream
2018-08-16
2017-10-07
151733

아이디어

어떻게 하면, 위치정보를 빠르게 찾을 수 있을까 ?
지구의 지역을 해시하면 어떨까 ? 해시 이거 한번에 찾을 수 있잖아.
하지만 위치의 경우, 주변위치도 찾을 수 있어야 하는데. 우리가 알고 있는 해시로는 이런 일을 할 수 없잖아 ?
그거야 해시 함수를 잘 만들면 되지

어떻게 ?

01101 11111 11000 00100 00010라는 2진수가 있다고 가정해보자. 왼쪽에 비트로 지도에서의 시작점과 해상도를 결정 할 수 있다. 이제 홀수열의 비트 0111110000000는 longitude가 되고, 짝수열의 비트 101111001001는 latitude가 된다. 위도와 경도 데이터를 2진 데이터로 만든 각 비트를 번갈아가면서 썩고, 이 값을 Base32 인코딩하면, 그 값이 해당 위치의 해시가 된다. 위 값은 대략 위도 42.6, 경도 -5.6 이 된다.

Geohash 인코딩은 역순으로 이루어진다. 0111110000000과 101111001001를 번갈아서 하나의 비트로 만들고 base32 encoding 한다.

Geohash

전통적인 지리정보 시스템은 R-Tree나 Quadtree모델을 사용한다. 이런 데이터 구조는 in-place 업데이트를 해야하는데, 데이터가 많을 경우 조작에 많은 비용이 들어간다. Geohash는 Z-like 검색을 이용해서 차원을 축소한다. Geohash를 이용하면 위치정보를 정렬된 key&value 형태로 저장 할 수 있다.

Geohash는 Gustavo Niemeyer이 개발한 지오코딩(geocoding)시스템이다. 2008년 2월에 시작된 서비스로, 지구상의 위치를 고유하게 식별할 수 있는 URL을 제공하는게 목적이다. URL 형식이므로 이메일, 게시판, 웹 애플리케이션에서 사용하기 좋다.

예를들어 127.02627271413803101, 37.49984981340243451(강남 대로변)의 geohash 값은 wydm6d9sqw0이다. geohash.org 사이트를 이용하면 geohash의 위치를 지도로 표시할 수 있다. 링크 http://geohash.org/wydm6d9sqw0

표현방식은 아래와 같다.

Quad-tree가 지역을 4분할 하는 것과 유사하게, 경도와 위도를 각각 2분할 한다. 그리고 이를 비트 단위로 번갈아가면서 표현한다. 따라서 2비트가 모이면 1개의 사분면을 표현하게 된다. 이와 같은 분할을 일정 횟수만큼 반복하여 모은 비트를 Base32 형태로 변환하여 문자열로 반환한다.

Geohash에서 정밀도는 분할한 횟수에 따른다. 정밀도가 작으면 사각 범위를 표시하지만, 일정 이상이 되면 점이라고 할 수 있을 만큼의 작은 범위를 표현할 수 있다. "정밀도"는 꽤 중요한 기능이 될 수 있다. R-Tree나 Quad-Tree같은 별도의 인덱스를 위한 삽입, 삭제가 필요 없이 hash 값 자체로 일정 범위의 지역을 나타낼 수 있기 때문이다.

비슷한 위치의 geohash는 공통접두어를 가진다. 공통접두어가 길 수록 근접하다. 아래 지도를 보자.

이들 5개 위치에 대한 geohash는

wydm6d72bv0(127.028428, 37.497868)
wydm6dd6cv0(127.027098,37.499587)
wydm6d5bm40(127.029297,37.496395)
wydm6d3bqe0(127.026615, 37.497774)
wydm6d9sqw0(127.026272, 37.499851,)

이다. wydm6d가 일치하는 것을 확인 할 수 있다. 그 만큼 거리가 가깝단 얘기.

위치기반 서비스

위치기반 서비스를 위한 GeoHash의 장점은 아래와 같이 정리 할 수 있다.

위 그림을 보자 일치하는 Hash 접두사만으로, 어떤 Object들이 어느 위치에 있는지, 근접해 있는지를 간단하게 알아낼 수 있다. SQL의 spatial function으로 이런 일을 하기 위해서는 까다로운 연산을 해야 한다. 물론 geohash를 사용 할 경우, 고정된 구획이 만들어지므로 범위에 오차가(특히 경계면에서) 생길 수 있으므로 이에 대한 보정을 해야 한다. 이 보정연산을 감안하더라도 효율적으로 작동 할 것이다.

일치하는 Hash 문자열에 따른 정확도는 아래와 같다.

아래 그림을 보자.

이동 경로 모니터링, 히트맵, 위치기반 커뮤니케이션도 쉽게 구현 할 수 있을 거다.

Geofencing와의 통합

Geofencing는 아이들의 위치를 모니터링 하기 위한 용도로 사용 할 수 있다. 맵 상의 가상의 울타리를 만들고, 그 위치를 벗어나면 부모에게 알려줄 수 있다. Geohash와 함께 사용한다면, 이동 경로도 케어 할 수 있을 거다.

Geomessaging과의 통합

Geomessaging는 사람, 시스템 혹은 컨텐츠가 지역에 출입 할 때, 해당 지역의 단말 혹은 모니터링 시스템에 메시지를 보내는 기술이다. Geofencing, Geohash와 함께 사용할 수 있을 것이다.

Geofencing는 관리자가 설정한 영역에 대한 메시징을 위해서, geohash는 임의의 공간에서의 메시지 전송을 위해서 (Geofencing와 함께)사용 할 수 있을 것이다.

Geofencing는 가상의 반경 혹은 다각형일 텐데, 필연적으로 많은 연산량이 필요하다. geohash는 적은 연산으로 geomessaging를 구현 할 수 있다. geohash로 빠르게 연산을 하고, Geofencing으로 디테일을 만드는 식으로 구현할 수 있을 것이다.

Geohash 연산

Go언어로 구현했다.

실행 창 늘이기

package main

import (
    "fmt"
    gh "github.com/TomiHiltunen/geohash-golang"
)

func geoRectangle(hash string, length int) {
    adjHash := hash[0:length]
    box := gh.Decode(adjHash)
    t := box.NorthEast()
    b := box.SouthWest()
    fmt.Println("--------------")
    fmt.Println("Hash : ", adjHash)
    fmt.Printf("Length %d : [%f,%f]-[%f,%f]\n", len(adjHash), t.Lat(), t.Lng(), b.Lat(), b.Lng())
    fmt.Println("Neighbor ", gh.CalculateAllAdjacent(adjHash))
}

func main() {
    hash := gh.Encode(37.5689831, 126.993479)
    fmt.Println("GeoHash ", hash)
    geoRectangle(hash, 7)
    geoRectangle(hash, 8)
}

이 코드는 37.5689831, 126.993479 좌표에 대한 geohash와 Length 7과 Length 8에 대한 사각형 범위, 그리고 주변의 geohash들을 출력한다.

빨간색 사각형은 Length 7 대략 <153m * 153m 의 범위를 가지고 있으며, 녹색 사격형은 38.2m x 19.1m 의 사각형 범위를 가지는 것을 확인 할 수 있다.

내 위치를 중심으로 반경 30m 이내에 있는 컨텐처를 검색한다고 가정해보자.

Geohash를 이용해서 위치기반 컨텐츠를 저장/검색하는 경우의 장점은 아래와 같다.

R-Tree가 아닌 B-Tree를 이용 빠르게 작동한다.
서버 캐시가 쉽다. Geohash 값을 Key로 저장하면 된다. REDIS의 LIST가 적당할 것 같다.
클라이언트 역시 간단하게 캐시 할 수 있다. 클라이언트 애플리케이션 개발이 단순해진다.
클러스터링 연산이 쉽다. Geohash Length 별로 컨텐츠를 필터링 할 수 있다.

Geohash와 R-Tree

Geohash는 공간, 특히 점(point)을 색인하는데 효율적(간단하고 빠르고 효과적)이다. 하지만 선과 다각형을 (약간의 노력으로)색인 할 수 있지만 대상에 따라서 적당한 방법이 아닐 수 있다. Geohash를 이용한 다각형 색인은 Georaptor를 참고해 보자.

Geohash는 각 계층별로 고정된 사각형 그리드로 지표면을 색인하며, 같은 계층에서 이 그리드는 서로 겹치지 않는다. 반면 R-Tree는 인덱싱하는 셀의 위치가 크기가 변경되는 동적 그리드다. 또한 R-Tree는 데이터를 입력하고 업데이트 할 때마다 셀이 변경되된다. GeoHash는 셀이 고정되기 때문에 데이터를 업데이트한다고 해서 셀이 변경되는 기능은 제공하지 않는다.

Geohash가 R-Tree와 비교해서 가지는 장점은 아래와 같다.

구현이 쉽다.
데이터가 증가에 따른 성능저하가 없다.
근접검색

단점은 아래와 같다.

임의의 정밀도
선과 다각형을 색인하고 질의하는게 어렵다.
선과 다각형을 색인하기 위한 방법이 있지만 색인이 커질 수 있다.
위경도(longitude/latitude) 좌표계를 기준으로 한다.(다른 좌표계에도 같은 방법을 적용 할 수 있긴 하지만)

단점의 대부분은 "선과 다각형"을 색인하기가 쉽지 않은 특성에 기인한다. 하지만 GIS 애플리케이션을 개발하는게 아니라면 선과 다각형을 써야 하는 경우는 많지 않고 구현이 단순하기 때문에 다양한 영역에서 사용 할 수 있다. 특히 데이터의 추가, 업데이트, 삭제가 빈번한 온라인 위치기반 서비스라면 최고의 선택이 될 수 있다.

Geohash는 2차원 좌표를 1차원 값으로 변환을 하는데, 1차원 데이터는 b-tree로 쉽게 색인 할 수 있어서, 손 쉽게 고성능의 위치 애플리케이션을 개발 할 수 있다.

함께 볼 만 한 것들

Geo-Blocking
Geocoding
Geolocation Database
Geomarketing
Geotagged photo
Geotagging
Geo targeting
Indoor positioning
Location-based service
Mobile phone tracking
Web analytics
W3C Geolocation API
REDIS도 geohash 기반 기능을 제공한다.

참고 문서들

제목	저자	변경일

Search For:

BY TAGS

Contents