# US 2025/0165447 A1 · System and method for efficiently importing geospatial data into the h3 indexing system

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2025/0165447 A1
- Document ID: US20250165447A1
- Status: Published application
- Kind: A1
- Application number: 18/949,779
- Filed: 2024-11-15
- Published: 2025-05-22
- Earliest claimed: 2023-11-16
- Assignees: Southern Oregon University
- Applicants: Southern Oregon University
- Inventors: Kevin Sahr
- Web page: https://patentgrep.com/patent/US20250165447A1

## CPC

- G01C 21/3878: {Hierarchical structures, e.g. layering}
- G06F 16/2246: {Trees, e.g. B+trees}
- G06F 16/29: Geographical information databases
- G01C 21/3446: {Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes}
- G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Determination of addresses in hierarchical grid systems is based on precomputed values used to define skip tables that are applied to permit determination of indices of cells at coarser resolutions than a target cell, without direct computations. The skip tables can be defined to permit skipping direct determination of indices of cells at one or more of the coarser resolutions using integer arithmetic thereby improving computation speeds required for navigation and other applications. Application of skip tables to a target cell at an entry resolution produces indices for cells at one or more skipped over, coarser resolutions and coordinates for a cell at a next coarser resolution. These coordinates can be used to re-apply the skip table so that a complete address associated with a target cell can be found. Target location can be similarly obtained using an inverse skip table.

## Claims

### Claim 1

A method of determining an address of a location in a hierarchical grid system, comprising, with a processor:
identifying a target cell associated with a selected location in a hierarchical grid system; and
applying a skip table to determine cell indices for at least a first cell and a second cell associated with the target cell at successively coarser resolutions.

### Claim 2 (depends on 1)

The method of claim 1, wherein the successively coarser resolutions are resolutions coarser than a resolution of the target cell.

### Claim 3 (depends on 1)

The method of claim 1, wherein the successively coarser resolutions include a resolution of the target cell and a successively coarser resolution than that of the target cell and the cell indices include an index of the target cell.

### Claim 4 (depends on 1)

The method of claim 1, wherein the skip table is an M-level skip table, wherein M is an integer greater than one, and the M-level skip table is applied to determine cell indices for at least M cells at M successively coarser resolutions.

### Claim 5 (depends on 4)

The method of claim 4, wherein the at least M cells at M successively coarser resolutions are cells at resolutions coarser than a resolution of the target cell.

### Claim 6 (depends on 4)

The method of claim 4, wherein the at least M cells at M successively coarser resolutions include a cell at the resolution of the target cell and the cell indices include an index of the target cell.

### Claim 7 (depends on 4)

The method of claim 4, wherein the M-level skip table is applied to determine coordinates of a cell associated with the target cell at a resolution that is successively coarser than the coarsest resolution of the at least M cells.

### Claim 8 (depends on 7)

The method of claim 7, further comprising finding at least one route to or from a location associated with the target cell based on the at least M cells.

### Claim 9 (depends on 8)

The method of claim 8, wherein the at least one route is a shortest route or a route with a shortest travel time.

### Claim 10 (depends on 4)

The method of claim 4, wherein the skip table has a skip table orientation, and further wherein, for a target cell having the skip table orientation the at least M cells at M successive coarser resolutions than the resolution of the target cell.

### Claim 11 (depends on 4)

The method of claim 4, further comprising finding an index associated with a cell at a resolution coarser than that of the at least M cells and having a cell orientation different from a skip table orientation.

### Claim 12 (depends on 1)

The method of claim 1, wherein the hierarchical grid is an aperture 7 hexagonal hierarchical grid or an aperture 3 hexagonal hierarchical grid or a hexagonal hierarchical grid with a mixture of one or more of aperture 3, aperture 4, and aperture 7.

### Claim 13 (depends on 1)

The method of claim 1, wherein the skip table includes cell indices associated with cells of a skip table sector.

### Claim 14 (depends on 1)

The method of claim 1, further comprising receiving location data and identifying the target cell based on the location data.

### Claim 15

A navigation apparatus, comprising:
at least one logical processor; and
at least one processor readable storage medium storing processor-executable instructions to determine a hierarchical address of a target cell using a skip table.

### Claim 16 (depends on 15)

The navigation apparatus of claim 15, wherein the processor-executable instructions to determine the hierarchical address of a target cell using the skip table are based on integer arithmetic.

### Claim 17 (depends on 15)

The navigation apparatus of claim 15, wherein the processor-executable instructions further comprise processor-executable instructions operable to identify the target cell based on a latitude and longitude.

### Claim 18 (depends on 15)

The navigation apparatus of claim 15, wherein the processor-executable instructions are operable to determine cell indices for at least a first cell and a second cell associated with the target cell at successively coarser resolutions based on application of the skip table.

### Claim 19 (depends on 18)

The navigation apparatus of claim 18, wherein the successively coarser resolutions include a resolution of the target cell and a successively coarser resolution than that of the target cell and the cell indices include an index of the target cell.

### Claim 20 (depends on 15)

The navigation apparatus of claim 15, wherein:
the skip table is an M-level skip table, wherein M is an integer greater than one;
the M-level skip table is applied to determine cell indices for at least M cells at M successively coarser resolutions, wherein the cells at M successively coarser resolutions are cells at resolutions coarser than a resolution of the target cell or the cells at M successively coarser resolutions include the target cell; and
the M-level skip table is applied to determine cell coordinates for at least one cell at a next coarser resolution than the M cells.

### Claim 21

A method of determining cell indices in a hierarchical grid system having resolutions associated with cells at a common orientation at regular intervals, comprising, with a processor:
obtaining an M-level skip table associated with a skip table entry resolution, wherein M is an integer greater than 1; and
applying the M-level skip table to a cell in the grid system at a first resolution to obtain a cell index for the cell at the first resolution and M−1 cell indices for M−1 cells in the grid system at successive resolutions coarser than the first resolution, coarser that the first resolution.

### Claim 22 (depends on 21)

The method of claim 21, wherein applying the skip table to the cell at the first resolutions produces coordinates of a corresponding cell at a resolution M.

### Claim 23 (depends on 22)

The method of claim 22, repetitively applying the skip table to cells having coordinates produced with the skip at successively coarser skip table output resolutions to obtain a cell index for the cell at the respective skip table output resolution and M−1 cell indices for M−1 cells in the grid system at the successively coarser resolutions.

### Claim 24

A method of determining a target location based on a set of cell indices in a hierarchical grid system, comprising, with a processor:
determining cell coordinates of a coarsest cell associated with a target location;
obtaining an M-level inverse skip table, wherein M is an integer greater than 1;
successively applying the M-level inverse skip table to find coordinates of M finer cells in the hierarchical grid system; and
obtaining a target spatial location based on coordinates of a cell associated with a finest resolution.