Columnwise spatial aggregation

• US 9,465,835 B2
• Filed: 06/25/2012
• Issued: 10/11/2016
• Est. Priority Date: 06/25/2012
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Weyerhaeuser, Christoph, Mindnich, Tobias, Baeumges, Daniel, Kazmaier, Gerrit Simon
• Primary Examiner(s): Le, Debbie
• Assistant Examiner(s): Mobin, Hasanul
• Application Number:
  US13/532,646
• Publication Number:
  US 20130346418A1
• Time in Patent Office: 1,569 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/244 Grouping and aggregation
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

A spatial aggregation query of a database is processed by receiving data specifying a maximum bounded rectangle for point data responsive to the query and specifying one or more grid partitions of the maximum bounded rectangle (in which at least one of the partitions is partially aggregated. Thereafter, for each partition, a number of points responsive to the query in each partition and a center of gravity of the points in each partition is computed. Data characterizing the corresponding computed number of points and center of gravity is then provided (e.g., persisted, loaded, transmitted, displayed, etc.). Related apparatus, systems, techniques and articles are also described.

Claims

1. A method for processing a spatial aggregation query of a database comprising:

receiving first data comprising (i) a maximum bounded rectangle for point data responsive to the query, (ii) one or more grid partitions of the maximum bounded rectangle, and (iii) one or more key figures, the point data including geographical information about a plurality of data points, the maximum bounded rectangle defining a geographical area which includes at least a portion of the plurality of data points, the one or more grid partitions defining areas within the maximum bounded rectangle that can be at least partially aggregated, and the one or more key figures defining information about the plurality of points, the information comprising values unrelated to the geographical information;

computing, for each grid partition, a quantity of grid points responsive to the query;

computing, for each grid partition, a center of gravity of the grid points, the center of gravity computed by weighting the grid points based on at least one of the one or more key figures; and

providing, for at least one partition, second data characterizing the corresponding computed quantity of points and the center of gravity.

2. A method as in claim 1, wherein the received first data further comprises four coordinates corresponding to four corners of the maximum bounded rectangle.

3. A method as in claim 1, wherein the second data is computed in parallel for two or more grid partitions.

4. A method as in claim 1, wherein the database is a columnwise database storing columnar data.

5. A method as in claim 4, wherein the database is an in-memory database.

6. A method as in claim 1, further comprising:

computing, for each of the one or more grid partitions, aggregations of the one or more key figures.

7. A method as in claim 1, further comprising:

computing, for each of the one or more grid partitions, a maximum bounded rectangle; and

providing third data characterizing the maximum bounded rectangle computed for each of the one or more grid partitions.

8. A method as in claim 1, wherein the receiving, computing, and providing are implemented by at least one data processor of at least one computing system.

9. A method as in claim 1, wherein the providing second data comprises one or more of:

persisting the second data, loading the second data, transmitting the second data, and displaying the second data.

10. A non-transitory computer-readable medium storing instructions, when executed by a processor, cause operations comprising:

receiving first data comprising (i) a maximum bounded rectangle for point data responsive to the query, (ii) one or more grid partitions of the maximum bounded rectangle, and (iii) one or more key figures, the point data including geographical information about a plurality of data points, the maximum bounded rectangle defining a geographical area which includes at least a portion of the plurality of data points, the one or more grid partitions defining areas within the maximum bounded rectangle that can be at least partially aggregated, and the one or more key figures defining information about the plurality of points, the information comprising values unrelated to the geographical information;

computing, for each grid partition, a quantity of grid points responsive to the query;

computing, for each grid partition, a center of gravity of the grid points, the center of gravity computed by weighting the grid points based on at least one of the one or more key figures; and

providing for at least one partition, second data characterizing the corresponding computed quantity of points and the center of gravity.

11. A non-transitory computer-readable medium as in claim 10, wherein the received first data further comprises four coordinates corresponding to four corners of the maximum bounded rectangle.

12. A non-transitory computer-readable medium as in claim 10, wherein the second data is computed in parallel for two or more grid partitions.

13. A non-transitory computer-readable medium as in claim 10, wherein the database is a columnwise database storing columnar data.

14. A non-transitory computer-readable medium as in claim 13, wherein the database is an in-memory database.

15. A non-transitory computer-readable medium as in claim 10, wherein the operations further comprise:

computing, for each of the one or more grid partitions, aggregations of the one or more key figures.

16. A non-transitory computer-readable medium as in claim 10, wherein the operations further comprise:

computing, for each of the one or more grid partitions, a maximum bounded rectangle; and

providing third data characterizing the maximum bounded rectangle computed for each of the one or more grid partitions.

17. A non-transitory computer-readable medium as in claim 10, wherein the providing second data comprises one or more of:

persisting the second data, loading the second data, transmitting the second data, and displaying the second data.

18. A system for processing a spatial aggregation query of a database comprising:

one or more data processors;

memory storing instructions, which when executed by at least one data processor, result in operations comprising;

receiving data comprising (i) a maximum bounded rectangle for point data responsive to the query, (ii) one or more grid partitions of the maximum bounded rectangle, and (iii) one or more key figures, the point data including geographical information about a plurality of data points, the maximum bounded rectangle defining a geographical area which includes at least a portion of the plurality of data points, the one or more grid partitions defining areas within the maximum bounded rectangle that can be at least partially aggregated, and the one or more key figures defining information about the plurality of points, the information comprising values unrelated to the geographical information;

computing, for each grid partition, a quantity of grid points responsive to the query;

computing, for each grid partition, a center of gravity of the grid points, the center of gravity computed by weighting the grid points based on at least one of the one or more key figures; and

providing, for at least one partition, data characterizing the corresponding computed quantity of points and the center of gravity.