Managing and querying spatial point data in column stores

Patent metadata

Field	Value
Publication number	US-10929501-B2
Application number	US-201313962725-A
Country	US
Kind code	B2
Filing date	Aug 8, 2013
Priority date	Aug 8, 2013
Publication date	Feb 23, 2021
Grant date	Feb 23, 2021

Abstract

A query of spatial data is received by a database comprising a columnar data store storing data in a column-oriented structure. Thereafter, a spatial data set is mapped to physical storage in the database using a space-filling curve. The spatial data set is then compacted and such compacted data can be used to retrieve data from the database that is responsive to the query. Related apparatus, systems, techniques and articles are also described.

First claim

What is claimed is:

1. A method comprising:
receiving, at a database comprising a columnar data store storing data in a column-oriented structure, a query on a spatial data set occupying a multi-dimensional space;
mapping, by at least one data processor, the spatial data set to physical storage in the database, the spatial data set having a plurality of coordinate values that are encoded using a corresponding plurality of value identifiers, the mapping using a space-filling curve having a minimal order such that the space-filling curve traverses every cell in a grid divided into a minimum quantity of cells, the minimal order of the space-filling curve being determined based at least on a quantity of the plurality of value identifiers used to encode the plurality of coordinate values, the mapping of the spatial data set using the space-filling curve having the minimal order transforming the spatial data set from the multi-dimensional space to a one-dimensional space along the space-filling curve, and the spatial data set being mapped using the space-filling curve having the minimal order such that no two points in the spatial data set are mapped to a same distance on the space-filling curve;
compacting, by the at least one data processor, the spatial data set based at least on the mapping of the spatial data set using the space-filling curve having the minimal order; and
executing, by the at least one data processor, the query by at least retrieving, from the database, at least a portion of the compacted spatial data set responsive to the query.

2. The method as in claim 1 , wherein the space-filling curve comprises a Hilbert curve.

3. The method as in claim 2 , wherein the mapping comprises:
transforming, by at least one data processor, points in the spatial data set into a positive coordinate space; and
defining, by at least one data processor, a quadrant based on boundaries of the transformed points.

4. The method as in claim 3 , wherein the mapping further comprises:
determining, by the least one data processor, the minimal order for the Hilbert curve.

5. The method as in claim 1 , wherein the minimal order further provides that points in the spatial data set have different respective distances on the space-filling curve, and wherein the respective distances vary based at least on a relative spatial proximity between the points in the spatial data set.

6. The method as in claim 1 , wherein the mapping further comprises:
sorting, by the at least one data processor, the points in the spatial data set, the points in the spatial data set being sorted according to a respective distance on the space-filling curve.

7. The method as in claim 6 , wherein the mapping further comprises:
generating, by the at least one data processor, a data dictionary and a corresponding bit compressed vector for each axis of the spatial data set.

8. The method as in claim 1 , wherein the spatial data set is compressed such that no two points in the spatial data set have a same distance on the space-filling curve.

9. The method as in claim 1 , wherein the using of the space-filling curve having the minimal order prevents gaps between points mapped to the space-filling curve.

10. The method as in claim 1 , wherein the space-filling curve comprises a Z-curve or a Moore curve.

11. The method as in claim 1 , wherein the minimal order corresponds to a number of bits required to represent every one of the plurality of value identifiers.

12. A non-transitory computer program product storing instructions which, when executed by at data processor of at least one computing system, result in operations comprising:
receiving, at a database comprising a columnar data store storing data in a column-oriented structure, a query on a spatial data set occupying a multi-dimensional space;
mapping, by at least one data processor, the spatial data set to physical storage in the database, the spatial data set having a plurality of coordinate values that are encoded using a corresponding plurality of value identifiers, the mapping using a space-filling curve having a minimal order such that the space-filling curve traverses every cell in a grid divided into a minimum quantity of cells, the minimal order of the space-filling curve being determined based at least on a quantity of the plurality of value identifiers used to encode the plurality of coordinate values, the mapping of the spatial data set using the space-filling curve having the minimal order transforming the spatial data set from the multi-dimensional space to a one-dimensional space along the space-filling curve, and the spatial data set being mapped using the space-filling curve having the minimal order such that no two points in the spatial data set are mapped to a same distance on the space-filling curve;
compacting, by the at least one data processor, the spatial data set based at least on the mapping of the spatial data set using the space-filling curve having the minimal order; and
executing, by the at least one data processor, the query by at least retrieving, from the database, at least a portion of the compacted spatial data set responsive to the query.

13. The computer program product as in claim 12 , wherein the space-filling curve comprises a Hilbert curve.

14. The computer program product as in claim 13 , wherein the mapping comprises:
transforming points in the spatial data set into a positive coordinate space; and
defining a quadrant based on boundaries of the transformed points.

15. The computer program product as in claim 14 , wherein the mapping further comprises:
determining the minimal order for the Hilbert curve.

16. The computer program product as in claim 12 , wherein the minimal order further provides that points in the spatial data set have different respective distances on the space-filling curve, and wherein the respective distances vary based at least on a relative spatial proximity between the points in the spatial data se.

17. The computer program product as in claim 12 , wherein the mapping further comprises:
sorting the points in the spatial data set, the points in the spatial data set being sorted according to respective distances of the points on the space-filling curve.

18. The computer program product as in claim 17 , wherein the mapping further comprises:
generating a data dictionary and a corresponding bit compressed vector for each axis of the spatial data set.

19. The computer program product as in claim 12 , wherein the using of the space-filling curve having the minimal order prevents gaps between points mapped to the space-filling curve.

20. The computer program product as in claim 12 , wherein the space-filling curve comprises a Z-curve or a Moore curve.

21. A system comprising:
computer hardware comprising at least one data processor; and
a database comprising a columnar data store storing data in a column-oriented structure;
wherein the computer hardware performs database operations comprising:
receiving a query on a spatial data set occupying a multi-dimensional space;
mapping the spatial data set to physical storage in the database, the spatial data set having a plurality of coordinate values that are encoded using a corresponding plurality of value identifiers, the mapping using a space-filling curve having a minimal order such that the space-filling curve traverses every cell in a grid divided into a minimum quantity of cells, the minimal order of the space-filling curve being determined based at least on a

Assignees

• Kazmaier Gerrit Simon
• Mindnich Tobias
• Weyerhaeuser Christoph
• Baeumges Daniel
• Sap Se

Inventors

• Kazmaier Gerrit Simon
• Mindnich Tobias
• Weyerhaeuser Christoph
• Baeumges Daniel

Classifications

• G06F17/10 Primary

  Complex mathematical operations {(function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544)} · CPC title

• G06F16/29

  Geographical information databases · CPC title