지오하시

지오하쉬는 구스타보 니에메이어와^[1] (1966년 유사작업) 지엠 모튼이 2008년 발명한 공공영역 지오코드 시스템으로,^[2] 지리적 위치를 짧은 문자와 숫자로 인코딩한다. 그것은 공간을 격자 모양의 버킷으로 세분하는 계층적 공간 데이터 구조로, 이것은 Z-order 곡선이라고 알려진 것의 많은 응용 프로그램 중 하나이며, 일반적으로 공간을 채우는 곡선이다.

지오하시는 임의의 정밀도와 같은 속성을 제공하며 코드 끝에서 점차 문자를 제거하여 크기를 줄이고 점차 정밀도를 잃을 수 있다. 지오하싱은 두 지오하시 사이에 공유 접두사가 길어질수록 두 지오하시가 공간적으로 더 가까워진다는 것을 보장한다. 두 지점은 매우 가까울 수 있지만 공유 접두사가 짧거나 없기 때문에 이 역은 보장되지 않는다.

역사

Geohash 알고리즘의 핵심 부분과 유사한 솔루션에 대한 첫 번째 이니셔티브는 1966년 G.M. Morton의 보고서인 "A Computer Oriented Geodetic Data Base and a New Technology in File Sequence"에 기록되었다.^[2] Morton 작업은 64비트 정수를 직접 인터리빙하는 것에 기초하여 이 현대판(2014) Geohash-integer 버전과 같이 Z-order 곡선의 효율적인 구현에 사용되었다. 그러나 그의 지오코드 제안은 사람이 읽을 수 있는 것이 아니었고 인기가 없었다.

분명히 2000년대 후반에 G. 나이메이어는 여전히 모튼의 작품에 대해 알지 못하고, 베이스32의 표현을 더하여 재창조했다. 2008년 2월, 시스템 발표와 함께 웹사이트를 개설했다.^[1] http://geohash.org사용자가 지리적 좌표를 지구 상의 위치를 고유하게 식별하는 짧은 URL로 변환하여 이메일, 포럼, 웹사이트에서 참조하는 것이 더 편리하다.

2009년 오픈스트리트맵의 쇼트링크^[3](베이스32 대신 베이스64 사용), 2014년 64비트 지오하시^[4], 2016년 이국적인 힐버트-지오하시^[5] 등 다양한 변형이 개발됐다.

일반 및 주 사용법

Geohash를 얻기 위해 사용자는 단일 입력 상자(위도 및 경도 쌍에 대해 가장 일반적으로 사용되는 형식은 허용됨)에 지오코딩되는 주소 또는 위도 및 경도 좌표를 제공하고 요청을 수행한다.

주어진 Geohash에 해당하는 위도와 경도를 보여주는 것 외에도, geohash.org에서 Geohash로 이동하는 사용자들은 내장된 지도를 받고, GPX 파일을 다운로드 받거나, 특정 GPS 수신기로 직접 웨이포인트를 전송할 수 있다. 지정된 위치에 대한 추가 세부사항을 제공할 수 있는 외부 사이트에도 링크가 제공된다.

예를 들어 좌표 쌍 57.64911,10.40744 (덴마크 주틀란드 반도 끝 부근)의 해시는 약간 짧다. u4pruydqqvj.

Geohash의 주요 사용법은 다음과 같다.

• 고유 식별자로.
• 예를 들어, 데이터베이스에서 점 데이터를 나타내기 위해.

지오하쉬는 또한 지오태깅에 사용되도록 제안되었다.

데이터베이스에서 사용될 때, 지리 데이터 구조는 두 가지 장점을 가진다. 첫째, 지오하시에 의해 인덱싱된 데이터는 연속 슬라이스로 주어진 직사각형 영역에 대한 모든 점을 가질 것이다(조각의 수는 지오하시 "결함선"의 존재와 필요한 정밀도에 따라 달라진다). 이것은 특히 단일 인덱스에 대한 쿼리가 다중 인덱스 쿼리보다 훨씬 쉽거나 빠른 데이터베이스 시스템에서 유용하다. 둘째, 이 인덱스 구조는 빠른 근접 검색에 사용될 수 있다. 즉, 가장 가까운 지점은 종종 가장 가까운 지오시 사이에 있다.

기술 설명

Computing(계산) 및 Matheical(수학) 뷰에 대한 공식 설명.

텍스트 표현

정확한 위도 및 경도 변환의 경우 Geohash는 공간의 반복되는 4분절을 사용하여 연속적인 위도 및 경도 공간 좌표를 계층적 이산 그리드로 변환하기 때문에 베이스 4의 공간 지수다. 콤팩트한 코드가 되기 위해 기본 32를 사용하며, "표준 텍스트 표현"인 다음 알파벳으로 그 값을 나타낸다.

'지오하쉬 문자'(32ghs)는 'a', 'i', 'l', 'o'를 제외한 거의 모든 숫자 0~9와 소문자를 사용한다.

예를 들어 위의 표와 상수 $B{\displaystyle }$= ${\displaystyle 32}$ ${\displaystyle B=32}$을$($를) 사용하는 경우, Geohash ezs42 일반적인 위치 표기법에 의해 십진법으로 변환할 수 있다.

[ezs42]_32ghs = ${\displaystyle [(e\times B^{4})+(z\times B^{3})+(s\times B^{2})+(4\times B^{1})+(2\times B^{0})]_{32ghs}}$

= ${\displaystyle [e]_{32ghs}\times B^{4}+[z]_{32ghs}\times B^{3}+[s]_{32ghs}\times B^{2}+[4]_{32ghs}\times B^{1}+[2]_{32ghs}\times B^{0}}$

= ${\displaystyle [13]_{10}\times B^{4}+[31]_{10}\times B^{3}+[24]_{10}\times B^{2}+[4]_{10}\times B^{1}+[2]_{10}\times B^{0}}$

= ${\displaystyle 13\times 1048576+31\times 32768+24\times 1024+4\times 32+2\times 1}$ = ${\displaystyle 13631488+1015808+24576+128+2=14672002}$

기하학적 표현

Geohash의 기하학적 공간 표현은 다음과 같이 혼합되어 있다.

• 2, 4, 6, ... e자리(짝수)를 가진 지오하시는 디코딩된 쌍(위도, 경도)이 균일한 불확실성을 갖는 "일반 그리드"에서 Z 순서 곡선으로 표시되며 Geo URI로 유효하다.
• 1, 3, 5, ... d자리(이상 숫자)를 가진 지오하시는 "и-order curve"로 표현된다. 디코딩된 쌍의 위도와 경도는 서로 다른 불확실성을 가진다(경도가 잘린다).

인접 셀을 병합하여 결과 사각 격자를 함수 j=플로어(i ÷ 2)로 지수화함으로써 Z 오더로부터 "и-order curve"를 구축할 수 있다. 측면 그림은 64제곱셀의 격자로부터 32개의 직사각형 셀의 격자를 얻는 방법을 보여준다.

인간에게 있어 지오하시의 가장 중요한 특성은 코드 접두사 안에 공간적 위계를 보존한다는 것이다.
예를 들어, 32개의 직사각형에 대한 "1 Geohash digit grid" 그림에서, 위의 코드의 공간 영역 e (위치 4,3에서 회색 청색 원 모양) 접두사와 함께 보존됨 e 1024개의 직사각형(척도 표시)의 "2자리 그리드"에서 em 그리드에서 회색 녹색에서 파란색 원까지).

알고리즘 및 예제

해시 사용 ezs42 예를 들어, 이것이 십진 위도와 경도로 디코딩되는 방법이다. 첫 번째 단계는 위에 표시된 바와 같이 텍스트 "base 32ghs"에서 이를 해독하여 이진 표현을 얻는다.

${\displaystyle [e]_{32ghs}=[13]_{10}=[01101]_{2}}$

${\displaystyle [z]_{32ghs}=[31]_{10}=[11111]_{2}}$

${\displaystyle [s]_{32ghs}=[24]_{10}=[11000]_{2}}$

${\displaystyle [4]_{32ghs}=[4]_{10}=[00100]_{2}}$

${\displaystyle [}$ ${\displaystyle 2}$ ${\displaystyle {}_{}}$ ${\displaystyle {32}_{}}$ g ${\displaystyle h_{}}$ s${\displaystyle {}_{}}$=${\displaystyle }$[ ${\displaystyle 2}$ ${\displaystyle {}_{}}$ ${\displaystyle {10\mathrm{}}_{}{}_{}}$=${\displaystyle }$[ ${\displaystyle 00010}$ ${\displaystyle {}_{}}$ 2 ${\$

이 작업으로 인해 비트가 생성됨 01101 11111 11000 00100 00010. 첫 번째 위치에서 숫자 0으로 왼쪽부터 카운트하기 시작하면 홀수 위치의 숫자가 경도 코드를 형성한다(0111110000000)), 짝수 위치에 있는 숫자가 위도 코드를 형성하는 동안 (101111001001).

그리고 나서 각 이진 코드는 왼쪽에서 오른쪽으로 다시 한 번에 한 비트를 고려하여 일련의 분할에서 사용된다. 위도 값의 경우 -90 ~ +90 구간을 2로 나누어 -90 ~ 0 및 0 ~ +90의 두 구간을 생성한다. 첫 번째 비트가 1이기 때문에 더 높은 간격을 선택하고 현재 간격이 된다. 코드의 모든 비트에 대해 절차가 반복된다. 마지막으로 위도 값은 결과 구간의 중심이다. 경도는 초기 간격이 -180 ~ +180임을 염두에 두고 동등한 방법으로 처리한다.

예를 들어 위도 코드에서 101111001001첫 번째 비트는 1이고, 그래서 우리는 우리의 위도가 0에서 90 사이라는 것을 안다. 더 이상 비트가 없으면 위도가 45로 오차가 ±45인 것 같다. 더 많은 비트를 사용할 수 있기 때문에 다음 비트로 계속 진행할 수 있으며, 각각의 후속 비트는 이 오류를 절반으로 줄일 수 있다. 이 표는 각 비트의 효과를 보여준다. 각 단계에서 범위의 절반은 녹색으로 강조 표시되며, 낮은 비트는 낮은 범위를 선택하고, 높은 비트는 상한 범위를 선택한다.

"평균 값" 열은 단순히 범위의 평균 값인 위도를 보여준다. 각각의 후속 비트는 이 값을 더 정밀하게 만든다.

(위 표의 숫자는 명확성을 위해 소수점 3자리까지 반올림)

최종 라운딩은 신중하게 진행되어야 한다.

${\displaystyle \min \leq \mathrm {round}(값)\leq \max }$

따라서 42.605에서 42.61 또는 42.6으로 반올림하는 것은 맞지만 43으로 반올림하는 것은 맞지 않는다.

자릿수 및 정밀도(km)

근접성 결정에 사용할 때의 제한 사항

에지 케이스

Geohash는 공통 접두사를 기준으로 서로 가까운 점을 찾는 데 사용할 수 있다. 그러나 180도 자오선의 반대편에 있지만 가장자리 케이스 위치는 공통 접두사(물리적 위치의 다른 길이)가 없는 지오하쉬 코드가 된다. 북극과 남극에 가까운 지점들은 매우 다른 지진을 가질 것이다.

적도(또는 그리니치 자오선)의 양쪽에 있는 두 개의 가까운 지점은 세계의 다른 '할프'에 속하기 때문에 긴 공통 접두사를 가지지 않을 것이다. 간단히 말해, 한 위치의 2진 위도(또는 경도)는 011111이 된다... 그리고 나머지 10만.... 그래서 그들은 공통 접두사를 가지지 않고 대부분의 비트가 뒤집힐 것이다. 이는 Z-오더 곡선(이 경우 N-오더 방문이라고 하는 것이 더 적절할 수 있음)에 의존한 결과로도 볼 수 있는데, 이는 근접한 두 지점이 매우 다른 시간에 방문될 수 있기 때문이다. 그러나 공통 접두사가 긴 두 점이 근접하게 된다.

근접탐색을 하기 위해서는 경계상자의 남서쪽 구석(위도와 경도가 낮은 낮은 낮은 지오하시)과 북동쪽 구석(위도와 경도가 높은 지오하시)을 계산해 그 둘 사이의 지오하시를 탐색할 수 있었다. 이 검색은 너무 많은 포인트가 될 수 있는 두 코너 사이의 z 순서 곡선의 모든 포인트를 검색한다. 이 방법은 180경맥과 극에서도 분해된다. Solr은 지오하시에 가까운 가장 가까운 사각형의 접두사를 계산하여 접두사 필터 목록을 사용한다[1].

비선형성

지오하시(이 구현에서)는 경도와 위도의 좌표를 기반으로 하기 때문에 두 지오하시 사이의 거리는 실제 거리로 변환되지 않는 두 지점 사이의 위도/경도 좌표 거리를 반영한다(Haversine 공식 참조).

위도-경도 시스템의 비선형성 예:

• 적도(0도)에서 경도의 길이는 111.320km이고, 위도의 길이는 110.574km로 오차 0.67%이다.
• 30도(중위도)에서 오차는 110.852/96.486 = 14.89%
• 60도(고북극)에서 오차는 111.412/55.800 = 99.67%로 극지방에서 무한대에 도달한다.

이러한 제한은 지오싱에 기인하는 것이 아니라 위도-경도 좌표에 기인하는 것이 아니라 구에 좌표를 매핑하는 것(비선형 및 모듈로 산술과 유사한 값의 래핑)이 어렵고 2차원 공간을 균일하게 탐구하는 것이 어렵기 때문이라는 점에 유의한다. 첫 번째는 지리 좌표계와 지도 투영과 관련이 있고, 다른 하나는 힐버트 곡선 및 z 순서 곡선과 관련이 있다. 일단 거리상 점들을 선형적으로 나타내고 가장자리에서 감싸고 균일하게 탐색할 수 있는 좌표계가 발견되면, 그러한 좌표에 지오하싱을 적용하는 것은 위의 한계로 인해 고통받지 않을 것이다.

지리학을 데카르트 좌표계가 있는 영역에 적용할 수 있지만, 좌표계가 적용되는 영역에만 적용할 수 있다.

이러한 문제에도 불구하고 가능한 해결책이 있으며, 이 알고리즘은 Elasticsearch,^[6] MongoDB,^[7] HBase, Redis,^[8] Auxulo에서^[9] 성공적으로 사용되어 근접 검색을 구현하고 있다.

유사한 인덱싱 시스템

Geohash를 데이터베이스에 문자열로 저장하는 방법의 하나는 공간 키라고도 하며 QuadTiles와 유사하게 위치 코드다.Locational code)^[10][11]가 있다.

일부 지리적 정보 시스템과 빅데이터 공간 데이터베이스에서는 힐버트 곡선 기반 인덱싱을 S2 지오메트리 라이브러리처럼 Z 순서 곡선의 대안으로 사용할 수 있다.^[12]

2019년에는 QA Locate에서^[13] GeohashPhrase라고^[14] 부르는 것을 프런트엔드를 설계하여 구문을 사용하여 Geohash를 코드화하여 구문을 사용하여 구문을 구문 영어로 의사소통을 용이하게 하였다. GeohashPrase 오픈소스를 만들 계획이 있었다.^[15]

라이센싱

Geohash 알고리즘은 2008년 2월 26일, 그것의 발명가에 의해 공공 영역에 투입되었다.^[16]

비교할 수 있는 알고리즘이 성공적으로 특허를^[17] 얻었고 저작권이 인정된 반면,^[18][19] GeoHash는 전혀 다른 알고리즘과 접근법에 기초하고 있다.

참고 항목

• 지오데틱 지오코딩 시스템 목록
• Geohash-36 (Geohash-variant가 아님)
• 그리드(공간 지수)
• 메이든헤드 로케이터 시스템
• 군사 격자 참조 시스템
• 모톤수(숫자 이론)
• 자연 지역 코드
• 번호 매기기 방식
• 개방형 위치 코드(및 코드)
• 공간 이동 곡선
• 무엇3단어
• Z 순서 곡선

참조

외부 링크

• 공식 웹사이트
• 탄성 검색: 최종 가이드 - Geo
• JTS 기하학적 지오하시 근사치
• 지오하쉬 플레이그라운드