Hybrid spatial index
AssigneeMicrosoft Technology Licensing, LLC
InventorsBosko MIHIC, Teodor DELIBASIC
Life of this patent
Estimating the term…
Abstract
Example implementations include a method, apparatus, and computer-readable medium configured for indexing records using a hybrid spatial index. The hybrid spatial index is an integer that indicates a spatial location of an object. The hybrid spatial index can indicate a cell that overlaps the object or a stripe that covers the object. The method, apparatus, or computer-readable medium may associate an integer spatial index with a record of an object. In at least some cases, the integer spatial index indicates a stripe of cells covering the object. The method, apparatus, or computer-readable medium may select the record based on the spatial index being within a range of spatial indices for a spatial predicate.
Claims23
An apparatus for indexing data comprising:
- one or more memories, individually or in combination, storing computer-executable instructions;
- and
- one or more processors coupled to the one or more memories and, individually or in combination, configured to execute the instructions to:
- associate an integer spatial index with a record of an object, wherein the integer spatial index indicates a stripe of cells covering the object;
- and
- select the record based on the spatial index being within a range of spatial indices for a spatial predicate, wherein to select the record based on the spatial index, the one or more processors, individually or in combination, are configured to:
- receive a query with the spatial predicate that indicates an area in which to select objects;
- emit a range of spatial indices from a start ID to a limit ID for one or more stripes that capture the area based on a direction and width category:
- identify any records with a spatial index between the start ID and the limit ID of each emitted stripe;
- and
- filter identified records based on an actual stripe width and a secondary stripe dimension of a respective emitted stripe to remove some false positive identifications.
(canceled)
A method of indexing data comprising:
- associating an integer spatial index with a record of an object, wherein the integer spatial index indicates a stripe of cells covering the object;
- and
- selecting the record based on the spatial index being within a range of spatial indices for a spatial predicate, wherein selecting the record based on the spatial index comprises:
- receiving a query with the spatial predicate that indicates an area in which to select objects;
- emitting a range of spatial indices from a start ID to a limit ID for one or more stripes that capture the area based on a direction and width category;
- identifying any records with a spatial index between the start ID and the limit ID of each emitted stripe;
- and
- filtering identified records based on an actual stripe width and a secondary stripe dimension of a respective emitted stripe to remove some false positive identifications.
(canceled)
One or more non-transitory computer-readable storage media having stored thereon computer-executable instructions that when executed by one or more processors cause the one or more processors, individually or in combination, to:
- associate an integer spatial index with a record of an object, wherein the integer spatial index indicates a stripe of cells covering the object;
- and
- select the record based on the spatial index being within a range of spatial indices for a spatial predicate, wherein the instructions to select the record based on the spatial index comprise instructions to:
- receive a query with the spatial predicate that indicates an area in which to select objects;
- emit a range of spatial indices from a start ID to a limit ID for one or more stripes that capture the area based on a direction and width category;
- identify any records with a spatial index between the start ID and the limit ID of each emitted stripe;
- and
- filter identified records based on an actual stripe width and a secondary stripe dimension of a respective emitted stripe to remove some false positive identifications.
Dependencies are inferred from the claim text.