[Uber Open Source] Engineering Sub-City Geos for a Hyper-Local Marketplace with Uber

Summary

In this presentation, the speaker introduces H3, a geospatial indexing system using hexagonal grid cells. The video explains the challenges of representing complex geographic data and why H3, built on the icosahedron, was designed to overcome these hurdles. Hexagons were chosen for their uniformity, minimal distortion, and efficient space-filling properties. The H3 library enables powerful algorithms for geographic analysis, including neighborhood searches and region definitions. The system supports multiple resolutions, making it suitable for a wide range of applications from large-scale mapping to detailed urban analysis.

Takeaways

• 😀 H3 is a geographic grid system built around hexagonal cells, providing a clean and scalable way to index geographic data.
• 😀 Grid systems help abstract messy geographic data into uniform cells for easier analysis and comparisons across the globe.
• 😀 The H3 system uses hexagons for better space-filling, uniform adjacency, and a more efficient way to model geographic flow.
• 😀 Unlike squares or triangles, hexagons ensure uniform adjacency with 6 unambiguous neighbors, enhancing algorithm performance.
• 😀 Hexagons, as compared to squares, offer superior properties for handling geographic data, particularly in algorithms for traversing neighbors or radius searches.
• 😀 The H3 grid system supports multiple levels of resolution, offering varying granularities down to roughly 1 square meter.
• 😀 Hexagonal tiling, based on an icosahedron, provides a globe-spanning system that minimizes distortion compared to other projections.
• 😀 The H3 grid system uses a hierarchical structure, where cells can be subdivided into smaller ones, ensuring flexibility across different geographic scales.
• 😀 H3 is open-source and available in various programming languages, such as C, Java, Python, JavaScript, and Go, through community-contributed bindings.
• 😀 H3’s unique indexing system uses 64-bit numbers to represent grid cells, enabling efficient data transfer and computational handling for large-scale geographic applications.

Q & A

What is the main focus of the presentation?

The presentation focuses on introducing H3, a geospatial grid system based on hexagons, and discussing its advantages, implementation, and practical applications in geographic data indexing and analysis.

Why are grid systems important in geospatial analysis?

Grid systems are important because they provide a clean, consistent structure for abstracting complex geographic spaces, making data analysis, algorithms, and geographic comparisons more manageable and efficient.

What are the common types of grid systems mentioned in the presentation?

The presentation mentions several grid systems including the graticule (latitude/longitude), Web Mercator tiles, S2 grid system, and H3, each offering different ways of dividing and indexing geographic data.

What are the key advantages of using hexagons as the basis for a grid system?

Hexagons are preferred because they provide uniform adjacency (six unambiguous neighbors), compact space-filling properties, and better suitability for modeling algorithms related to flow and proximity, compared to squares or triangles.

What challenge does the H3 system face with hierarchical relationships between cells?

The main challenge is that hexagons do not have perfect child containment, meaning that smaller hexagons may not be perfectly contained within larger ones. This creates a small margin of error, which requires careful handling in certain algorithms.

How does H3 handle the issue of grid cell indexing?

H3 uses a 64-bit identifier to uniquely index each cell. This identifier encodes information such as the resolution, base cell, and child index, allowing for precise geospatial data management and efficient data transfer.

Why are triangles considered a poor choice for a geographic grid system?

Triangles are considered poor because they have ambiguous neighbors at the corners, which complicates algorithms for geographic analysis. Additionally, flipping the orientation of neighbors for every cell adds complexity to grid management.

What is the Dymaxion projection, and why was it chosen for the H3 system?

The Dymaxion projection, developed by Buckminster Fuller, was chosen for the H3 system because it minimizes distortion and positions all the vertices on water, reducing issues with Pentagon cells that appear when projecting the icosahedron onto the Earth's surface.

What are the practical uses of the H3 library discussed in the presentation?

The H3 library is used for various geospatial tasks, such as identifying which grid cell a geographic point belongs to, finding neighboring cells, transforming polygons into H3 cells, and analyzing geographic areas with multiple resolutions for more precise data aggregation and analysis.

What role do 'Pentagons' play in the H3 grid system, and how are they managed?

Pentagons arise due to the icosahedron projection used in H3, where five faces converge at vertices. These Pentagon cells introduce minor distortions, but with only 12 of them in each resolution level, they are rarely a significant issue in practice, especially at higher resolutions.