Managing and Querying Spatial Point Data in Column Stores

• US 20150046411A1
• Filed: 08/08/2013
• Published: 02/12/2015
• Est. Priority Date: 08/08/2013
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Kazmaier, Gerrit Simon, Mindnich, Tobias, Weyerhaeuser, Christoph, Baeumges, Daniel
• Granted Patent: US 10,929,501 B2
• Time in Patent Office: Days
• US Class Current: 707/693
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544

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.

Claims

1. A method comprising:

receiving, by a database comprising a columnar data store storing data in a column-oriented structure, a query of spatial data;

mapping, by at least one data processor, a spatial data set corresponding to the received query to physical storage in the database using a space-filling curve;

compacting, by at least one data processor, the spatial data set; and

retrieving, by at least one data processor, data from the database responsive to the query using the compacted spatial data set.

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

3. A 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. A method as in claim 3, wherein the mapping further comprises:

determining, by at least one data processor, a Hilbert order for the quadrant.

5. A method as in claim 4, wherein the determined Hilbert order provides that each point in the spatial data set has a different Hilbert distance based on spatial proximity.

6. A method as in claim 5, wherein the mapping further comprises:

sorting, by at least one data processor, the points in the spatial data set according to their Hilbert distance.

7. A method as in claim 6, wherein the mapping further comprises:

generating, by at least one data processor, a data dictionary and a corresponding bit compressed vector for each axis of the spatial data set.

8. A method as in claim 2, wherein the spatial data set is compressed so that no two points in the spatial data set have a same Hilbert distance.

9. A method as in claim 8, wherein the spatial data set is compressed so that there are no gaps between distances of points in the spatial data set.

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

11. 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, by a database comprising a columnar data store storing data in a column-oriented structure, a query of spatial data;

mapping a spatial data set corresponding to the received query to physical storage in the database using a space-filling curve;

compacting the spatial data set; and

retrieving data from the database responsive to the query using the compacted spatial data set.

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

13. A computer program product as in claim 12, 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.

14. A computer program product as in claim 13, wherein the mapping further comprises:

determining a Hilbert order for the quadrant.

15. A computer program product as in claim 14, wherein the determined Hilbert order provides that each point in the spatial data set has a different Hilbert distance based on spatial proximity.

16. A computer program product as in claim 15, wherein the mapping further comprises:

sorting the points in the spatial data set according to their Hilbert distance.

17. A computer program product as in claim 16, wherein the mapping further comprises:

generating a data dictionary and a corresponding bit compressed vector for each axis of the spatial data set.

18. A computer program product as in claim 12, wherein the spatial data set is compressed so that no two points in the spatial data set have a same Hilbert distance;

and wherein the spatial data set is compressed so that there are no gaps between distances of points in the spatial data set.

19. A computer program product as in claim 11, wherein the space-filling curve comprises a Z-curve or a Moore curve.

20. A system comprising:

at least one data processor; and

a database comprising a columnar data store storing data in a column-oriented structure;

wherein the database;

receives a query of spatial data;

maps a spatial data set corresponding to the received query to physical storage in the database using a space-filling curve;

compacts the spatial data set; and

retrieves data from the database responsive to the query using the compacted spatial data set.