Indexing algorithms

[danlooo]

Indexing cells is crucial for reading speed.
We want to put nearby points in cells with similar cell ids.
This is required for fast access of compressed chunks.
Generalized Balanced Ternary (GBT) (Gibson & Lucas, 1982) is a hierarchical prefix code system for aperture 7 grids.
We use GBT to define a central place index (CPI) that works with apertures 3,4 and 7 at all resolutions
Current implementations of CPI: Uber H3, DGGRID FULLER 500m.
A cell may have multiple indices, because it might belong to multiple parents. We need to define one of them to be used.
Pentagon id = Hexagon ID in which one non-centroid sub cell id was removed.

Advantages of Hierarchical Central Place indexing

• All parent cells are encoded just in the cell ID
• Works with apertures 3,4, and 7
• Automatically places nearby cell ids into similar cell IDs (Math. Definition of a space as set of nested sets)
• Natural chunking scheme (just based on digits)

Additional information

[danlooo]

Can we just calculate the Shortest Traveling Salesperson Path visiting all cell center point vertices exactly once while minimizing travel distance. But is this equivalent to having the shortest local distance on average? For chunking we don't care to go thousands of kilometers occasionally e.g. start at a new polyhedral face.

There are recursively defined Hamiltonian Paths for the 2D plane, i.e. space-filling curves e.g. Hilbert curve and Gosper curve for rectangles and hexagons, respectively. These might not be shortest solutions for TSP.

A Hamiltonian Cycle would be also nice to have, since the earth is a sphere and GCN kernels may want to go round and round multiple times. Then it is always fast whether to start in Americas or Asia, because the cell id would be always continuous. This should not affect chunking. However, we should prioritize average distance to neighboring cell ids instead of forcing the Hamiltonian cycle.