# US 10,372,705 B2 · Parallel querying of adjustable resolution geospatial database > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,372,705 B2 - Document ID: US10372705B2 - Status: Granted - Kind: B2 - Application number: 15/096,218 - Filed: 2016-04-11 - Published: 2017-01-12 - Granted: 2019-08-06 - Earliest claimed: 2015-07-07 - Assignees: International Business Machines Corporation - Applicants: International Business Machines Corporation - Inventors: Sergio A. Bermudez Rodriguez; Marcus O. Freitag; Hendrik F. Hamann; Levente Klein; Fernando J. Marianno - Web page: https://patentgrep.com/patent/US10372705B2 ## CPC - G06F 16/24532: {of parallel queries} - G06F 16/29: Geographical information databases - G06F 16/9537: Spatial or temporal dependent retrieval, e.g. spatiotemporal queries - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract An embodiment includes dividing a map into a first grid comprising a first plurality of cells with a first resolution and into a second grid comprising a second plurality of cells with a second resolution; determining that, because an initial portion of a key of a first cell of the second grid comprises a key of a first cell of the first grid, the first cell of the first grid comprises the first cell of the second grid; storing the first and the second grid in memories of distributed servers, wherein the first cell of the first grid and the first cell of the second grid are stored in a same one of the distributed servers or are stored in neighboring ones of the distributed servers; and directing respective processors of the distributed servers to perform a parallel search of the first grid and the second grid using the keys. ## Claims ### Claim 1 A method for accelerating networked parallel searches, the method comprising: receiving at least a first geospatial map at a main server from at least one network; dividing, using at least one of one or more hardware processors, at least a portion of the first map into a first grid comprising a first plurality of cells with a first resolution; dividing, using at least one of the one or more hardware processors, at least the portion of the first map into a second grid comprising a second plurality of cells with a second resolution, wherein the second resolution is a multiple of the first resolution; assigning, using at least one of the one or more hardware processors, each of the first plurality of cells and the second plurality of cells a unique key using z-order indexing, wherein key length is inversely proportional to resolution such that keys assigned to each of the second plurality of cells are longer than keys assigned to each of the first plurality of cells; determining, using at least one of the one or more hardware processors, that, because an initial portion of a key of a first cell of the second grid comprises a key of a first cell of the first grid, the first cell of the first grid comprises the first cell of the second grid; storing the first grid and the second grid in memories of a plurality of distributed servers, wherein the first cell of the first grid and the first cell of the second grid are stored in a same one of the distributed servers or are stored in neighboring ones of the distributed servers; receiving a query at the main server from the at least one network; and the main server directing respective processors of the plurality of distributed servers to perform a parallel search of the first grid and the second grid using the keys for one or more results responsive to the query. ### Claim 2 (depends on 1) The method of claim 1, wherein at least one corner of at least one of the cells of the second grid is aligned to at least one corner of at least one of the cells of the first grid. ### Claim 3 (depends on 1) The method of claim 1, wherein the first plurality of cells and the second plurality of cells comprise rectangular cells. ### Claim 4 (depends on 3) The method of claim 3, wherein the first plurality of cells and the second plurality of cells comprise square cells. ### Claim 5 (depends on 1) The method of claim 1, wherein each of the first grid and the second grid is based at least in part on longitude and latitude. ### Claim 6 (depends on 1) The method of claim 1, further comprising associating each of the first plurality of cells and the second plurality of cells with a timestamp, wherein each of the first grid and the second grid is based at least in part on the associated timestamp. ### Claim 7 (depends on 1) The method of claim 1, further comprising: determining, using the keys, that a second cell of the first grid neighbors a second cell of the second grid; and wherein, when storing the first grid and the second grid in respective memories of the plurality of distributed servers, the second cell of the first grid and the second cell of the second grid are stored in a same one of the distributed servers or are stored in neighboring ones of the distributed servers. ### Claim 8 (depends on 1) The method of claim 1, further comprising: receiving at least a second geospatial map at the main server from the at least one network; dividing at least a portion of the second map into a third grid comprising a third plurality of cells with a third resolution; determining that at least a portion of a third cell of the first or second grid overlaps at least a portion of a third cell of the third grid; storing the third grid in memories of the plurality of distributed servers, wherein the third cell of the first or second grid and the third cell of the third grid are stored in a same one of the distributed servers or are stored in neighboring ones of the distributed servers; responsive to the query, performing a parallel search of the first grid, the second grid, and the third grid for one or more results. ### Claim 9 (depends on 8) The method of claim 8, wherein at least one of the first resolution and the second resolution is equal to the third resolution. ### Claim 10 (depends on 8) The method of claim 8, wherein the third cell of the first or second grid is identical to the third cell of the third grid. ### Claim 11 (depends on 8) The method of claim 8, wherein the first and second maps have different native resolutions. ### Claim 12 (depends on 8) The method of claim 8, further comprising aligning the third plurality of cells with at least one of the first plurality of cells and the second plurality of cells. ### Claim 13 (depends on 12) The method of claim 12, wherein the aligning comprises interpolation to preserve accuracy. ### Claim 14 (depends on 13) The method of claim 13, further comprising selecting the interpolation from a group comprising cubic interpolation, linear interpolation, bilinear interpolation, and nearest-neighbors interpolation. ### Claim 15 (depends on 8) The method of claim 8, further comprising: determining that a fourth cell of the third grid neighbors a fourth cell of the first or second grid; and wherein, when storing the third grid in memories of the plurality of distributed servers, the third cell of the first or second grid and the third cell of the third grid are stored in a same one of the distributed servers or are stored in neighboring ones of the distributed servers. ### Claim 16 (depends on 8) The method of claim 8, further comprising: assigning each of the third plurality of cells a key using z-order indexing, wherein the first, second, and third grids share a common coordinate system. ### Claim 17 (depends on 1) The method of claim 1, wherein the one or more results have a specified resolution. ### Claim 18 (depends on 17) The method of claim 17, wherein the specified resolution is included in the query. ### Claim 19 (depends on 17) The method of claim 17, wherein the specified resolution is a native resolution of the first map. ### Claim 20 (depends on 17) The method of claim 17, wherein the specified resolution is an available resolution in a geodatabase. ### Claim 21 (depends on 17) The method of claim 17, wherein the specified resolution is preselected for a given use case. ### Claim 22 (depends on 1) The method of claim 1, wherein a first portion of the one or more results has a different resolution than a second portion of the one or more results. ### Claim 23 An apparatus, comprising: a memory; and at least one processor coupled with the memory and operative: to receive at least a first map from at least one network; to divide at least a portion of the first map into a first grid comprising a first plurality of cells with a first resolution; to divide at least the portion of the first map into a second grid comprising a second plurality of cells with a second resolution, wherein the second resolution is a multiple of the first resolution; to assign each of the first plurality of cells and the second plurality of cells a unique key using z-order indexing, wherein key length is inversely proportional to resolution such that keys assigned to each of the second plurality of cells are longer than keys assigned to each of the first plurality of cells; to determine that, because an initial portion of a key of a first cell of the second grid comprises a key of a first cell of the first grid, the first cell of the first grid comprises the first cell of the second grid; to store the first grid and the second grid in memories of a plurality of distributed servers, wherein the first cell of the first grid and the first cell of the second grid are stored in a same one of the distributed servers or are stored in neighboring ones of the distributed servers; to receive a query at the main server from the at least one network; and to direct respective processors of the plurality of distributed servers to perform a parallel search of the first grid and the second grid using the keys for one or more results responsive to the query. ### Claim 24 A computer program product comprising a non-transitory machine-readable storage medium having machine-readable program code embodied therewith, said machine-readable program code comprising: machine-readable program code configured: to receive at least a first map from at least one network; to divide at least a portion of the first map into a first grid comprising a first plurality of cells with a first resolution; to divide at least the portion of the first map into a second grid comprising a second plurality of cells with a second resolution, wherein the second resolution is a multiple of the first resolution; to assign each of the first plurality of cells and the second plurality of cells a unique key using z-order indexing, wherein key length is inversely proportional to resolution such that keys assigned to each of the second plurality of cells are longer than keys assigned to each of the first plurality of cells; to determine that, because an initial portion of a key of a first cell of the second grid comprises a key of a first cell of the first grid, the first cell of the first grid comprises the first cell of the second grid; to store the first grid and the second grid in memories of a plurality of distributed servers, wherein the first cell of the first grid and the first cell of the second grid are stored in a same one of the distributed servers or are stored in neighboring ones of the distributed servers; to receive a query at the main server from the at least one network; and to direct respective processors of the plurality of distributed servers to perform a parallel search of the first grid and the second grid using the keys for one or more results responsive to the query.