출처

H3: Uber’s Hexagonal Hierarchical Spatial Index (2018/06/27)

작자

Isaac BrodskyIsaac Brodsky is a software engineer on Uber’s Marketplace Intelligence team.

Uber

Uber 홈 페이지
그들은 전 세계를 휩쓸고 있는 블랙카 서비스, 택배의 Uber Eats, 필요에 따라 항공편을 이용하는 Uber AIR 등을 통해 생활을 바꾸려 하고 있다.
소프트뱅크는 일본 진출을 지지한다
참조: 소프트뱅크, 우버의 출자 완료

H3

각종 크기의 육각형을 격자로 하는 새로운 색인 시스템 (좌표 시스템)
(크기가 다른 육각형, 층별 육각형에 대한 설명은 나중에 진행됩니다.)

본문

※ 의역된 부분이 있으므로 인용원을 참조하십시오.

왜 H3

공간 데이터 집합(예를 들어 지도)을 분석할 때 격자 시스템은 매우 중요하다.이곳의 격자 시스템은 지구 표면을 어떤 격자로 분할하는 구조를 가리킨다.
이를 바탕으로 Uber는 다음과 같은 가능한 격자 시스템을 실현하기 위해 H3를 개발했다.

승차 비용과 승차 노선 최적화

공간 데이터의 시각화와 탐색

H3를 사용하여 지리 정보를 분석할 수 있습니다.도시 수준에서 동태적인 가격 결정 등 결정을 진행하다.Uber는 시장 분석, 최적화를 위해 H3를 사용합니다.H3는 이를 위해 설계된 것으로 우리는 층을 나누는 육각형을 사용했다.

개원

올해(2018년) 초 Uber는 Github에서 H3개원를 만들었다.
그리고 지난주 공개H3 JavaScript.

문장의 목적

이 글에서 우리는'H3 특징의 격자 시스템을 왜 사용하는가','H3의 시작 안내서'를 토론할 것이다.

배경

매일 수백만 건의 이벤트(주문)가 Uber로 전송됩니다.차를 타고 싶은 사람이 요구하자 운전사가 운전을 시작했다.배가 고픈 사람은 밥을 먹어야 한다.그 활동들은 어딘가에서 발생했다.예를 들어 승객들은 집에서 승차 요청을 할 수도 있고, 기사는 몇 마일 떨어진 회사에서 이 요청을 승인할 수도 있다.
이러한 이벤트 정보는 서비스를 통해 Uber가 사용자 시장을 이해하고 최적화하는 데 도움이 됩니다.예를 들어 이 도시의 어느 지역에서 수요가 공급을 초과하면 상응하는 가격에 변화가 발생할 수 있다.아니면, uber POOL(합승 서비스) 기사와 2개의 승차 요구가 매우 가까운 일은 분명히 알려줄 수 없다.
Uber 시장의 데이터에서 정보와 통찰력을 얻으려면 도시 전체의 데이터를 분석해야 한다.도시는 지리적으로 다양성이 있기 때문에 반드시 작은 입도로 분석해야 한다.그러나'정확하게 사건 발생 장소를 찾는'최고 정밀도 분석은 어려울 뿐만 아니라 원가도 높아진다.따라서 지역 분석은 훨씬 실용적이다.

그림은 점 정보가 지역 정보로 변하는 모습이다.(시내 차→육각형 안의 차→차의 수량에 따라 육각형을 착색)
격자 시스템은 이벤트를 육각형 영역(셀)에 넣는 데 사용됩니다.데이터 포인트가 육각형으로 막혀 있기 때문에 육각형을 넣은 데이터를 사용하면 데이터 포인트를 나타낼 수 있다.예를 들어 우리는 서비스를 전개하는 시육각형 내의 공급과 수요를 평가함으로써 가격 상승을 계산한다.육각형은 Uber 시장 분석의 기초이다.

왜 육각형이야?

육각형도 중요하다.시내의 사용자는 일반적으로 이동하는데 육각형은 사용자가 시내에서 이동할 때 발생하는 양적 오차(정보를 연속(아날로그)에서 이산(디지털)으로 바꿀 때 발생하는 오차)를 최소화한다.반경과 간단하게 비슷할 수도 있다.
예: Engineering Uber Predictions in Real Time with ELK
육각형 이외의 선택으로 아래도 가능하다.

다각형

우편번호를 사용한 구역 구분이 그 예이지만, 코를 골고 사용하기 어려운 크기를 분석하기 때문에 우리의 의도와 무관하게 변경될 가능성도 있다.(사진은 맨해튼 ZIP 코드 (우편번호) 지도)

Uber 운영자 경험 매핑

→ 거리의 변화에 따라 갱신해야 하며 구역의 경계선을 정하는 것도 어렵다
(사람에 속하고 비용이 높음)
격자 시스템은 Uber가 서비스를 전개하는 시내에서 비교할 수 있는 형식과 크기를 가지고 있으며, 속인의 변경도 필요 없다.격자 시스템은 도로와 시내 지역을 배열하지 않지만 다른 한편, 격자에 대해 분류(집합)를 통해 지역을 효과적으로 표시할 수 있다.분류를 통해 분석이 더욱 편리해졌다.

H3

Uber는 육각형 격자 시스템과 층별 색인 시스템의 장점을 얻기 위해 H3를 개발했다.
지구상에서 격자 시스템을 응용할 때 적어도 두 가지를 고려해야 한다.

지도 투영

지도의 격자

지도 투영

지구상의 위치라는 3차원 정보를 지도상의 점이라는 2차원 정보로 삼다

지구상의 그물

2차원으로 변한 후 지구의 격자 시스템에 따라 격자를 넣는다.
각종 투영 격자의 조합은 무한하다.메카토 도법과 정방망격은 유명한 예이다.이 조합은 못 쓰는 것은 아니지만 단점이 많다.우선 메카토 도법으로 인한 사이즈 변형을 놓칠 수 없다.일부 칸은 상당히 다른 구역을 포함할 것이다.격자점도 한 가지 단점이 있다. 즉, 분석할 때 여러 조의 계수가 필요하다는 것이다.그 원인은 정사각형 격자의 기하학적 성질에 있고 인접한 도형은 두 가지가 있다.공유 모서리의 섹션은 4 방향과 * 공유 교점의 섹션은 * 4 방향입니다.

뽑힌 건요.

투영 방법은 심사방위도법을 선택할 수 있다.20면체의 중심에서 표면으로 투영하다.

20면체의 투영은 20의 2차 평면을 생성한다.
20면체는 2차원으로 확장할 수 있지만 H3는 이렇게 하지 않고 지구 표면에 울타리를 남긴다.(위 이미지)
그물 모양으로 뽑힌 것은 당연히 육각형이다.다음 그림과 같이 육각 격자선은 인접 셀의 거리와 동일하게 전체 영역과 모서리를 공유합니다.(삼각형, 사각형 참조)
이것은 경사도를 분석하고 매끄럽게 할 때 매우 편리한 특성이다.

H3의 격자는 122개의 기본 단원으로 구성되어 있다.반복 항목을 무시하면 20면체의 면마다 10개의 육각형이 있다.일부 칸은 여러 면에 존재한다.(아래 그림 경계의 셀 참조)

우리는 12개의 오각형을 도입했다. 왜냐하면 20면체는 육각형으로만 채울 수 없기 때문이다.(축구, 오각형: 12개, 육각형: 20개) 20면체의 정점은 각각 1개이다.
H3는 16레벨 해상도를 지원합니다.해상도가 한 단계 높아지면 셀 크기는 7분의 1입니다.육각형은 7개의 육각형으로 완벽하게 나눌 수 없기 때문에 해상도가 높은 칸은'대략'부모 칸에 포함될 것이다.

이것은 포지셔닝에 도움이 된다.하위 셀은 부모 셀에만 대체적으로 포함되기 때문에 위치를 정할 때 영역을 끊어야 하기 때문에 영역의 변형이 발생합니다.
그러나 다른 상황에서 경계는 정확하게 정의된다.

Getting started with H3

H3의 인덱스 시스템은 Github에 게시됩니다.라이브러리 자체는 C 언어로 쓰여 있지만 많은 언어를 지원합니다.만약 처음이라면 Bindings를 사용하는 것을 권장합니다.Uber는 자바, 자바스크립트가 사용하는 Bindings를 공개해 지역사회가 더 많은 언어를 대응하는 데 기여했다.파이썬과 고의 Bindings는 조만간 공개될 예정이다.

기본 함수

geoToH3: 경도 위도 정보를 64Bit H3 인덱스로 변환하거나 해상도를 지정할 수 있습니다.

kRing

등등

추가 정보

H3는 Uber의 시장 정량 분석을 허용합니다.이제 개원하면 너도 세계의 육각형을 형화할 수 있다!
"Github 저장소 추적", "#uberH3 태그가 달린 트위터"H3 커뮤니티에 가입하세요!