# US 10,503,780 B1 · Apparatus and method for forming a grid-based geospatial primary index and secondary index

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

- Number: US 10,503,780 B1
- Document ID: US10503780B1
- Status: Granted
- Kind: B1
- Application number: 15/424,686
- Filed: 2017-02-03
- Granted: 2019-12-10
- Earliest claimed: 2017-02-03
- Assignees: MarkLogic Corporation
- Applicants: MarkLogic Corporation
- Inventors: Jacob Richard Fowler
- Web page: https://patentgrep.com/patent/US10503780B1

## CPC

- G06F 16/9014: {hash tables}
- G06F 16/29: Geographical information databases
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method implemented by a computer with a processor and a memory storing instructions executed by the processor includes mapping a geographic input region to a set of blocks. For each block in the set of blocks, ellipsoidal geographic coordinates of the geographic input region are transformed to flat coordinates. The block is stored in a primary index when the block does not contain a boundary of the geographic input region. The block is stored in a secondary index when the block does contain a boundary of the geographic input region.

## Claims

### Claim 1

A method implemented by a computer with a processor and a memory storing instructions executed by the processor, comprising:
mapping a geographic input region to a set of blocks;
for each block in the set of blocks:
transforming ellipsoidal geographic coordinates of the geographic input region to flat coordinates,
storing the block in a primary index when the block does not contain a boundary of the geographic input region to form a non-boundary entry,
storing the block in a secondary index when the block does contain a boundary of the geographic input region to form a boundary entry;
after mapping the geographic input region to the set of blocks, resolving a geospatial query including a query geohash utilizing the primary index and the secondary index to identify stored non-boundary entries and stored boundary entries that correspond to the query geohash; and
returning to a user the stored non-boundary entries and stored boundary entries that correspond to the query geohash.

### Claim 2 (depends on 1)

The method of claim 1 further comprising storing for each block in the set of blocks a prefix string.

### Claim 3 (depends on 2)

The method of claim 2 wherein the prefix string is a geohash.

### Claim 4 (depends on 2)

The method of claim 2 further comprising storing for each block in the set of blocks prefix sub-strings derived from the prefix string.

### Claim 5 (depends on 4)

The method of claim 4 wherein the prefix sub-strings are geohash substrings derived from a geohash prefix string.