Determining data structures for spatial data based on spatial data statistics

Patent metadata

Field	Value
Publication number	US-11100119-B2
Application number	US-201815972077-A
Country	US
Kind code	B2
Filing date	May 4, 2018
Priority date	May 4, 2018
Publication date	Aug 24, 2021
Grant date	Aug 24, 2021

Abstract

Some embodiments provide a non-transitory machine-readable medium that stores a program. The program identifies a first data structure having a first type. The first data structure is configured to store a set of geometries. The program further identifies a second data structure associated with the first data structure. The second data structure is configured to store modifications to the set of geometries. The program also perform a merge operation on the first data structure and the second data structure to form a third data structure.

First claim

What is claimed is:

1. A non-transitory machine-readable medium storing a program executable by at least one processing unit of a device, the program comprising sets of instructions for:
identifying a first data structure having a first type, the first data structure configured to store a set of geometries;
identifying a second data structure associated with the first data structure, the second data structure configured to store modifications to the set of geometries; and
performing a merge operation on the first data structure and the second data structure to form a third data structure by:
determining a first set of statistics data associated with the modifications to the set of geometries stored in the second data structure;
retrieving a second set of statistics data associated with the set of geometries stored in the first data structure;
determining a second type of data structure based on a storage cost value and a set of query performance cost values for each of a subset of a plurality of types of data structures identified based on the first and second sets of statistics data, wherein a defined weight value is applied to each query performance cost value in the set of query performance cost values;
applying the modifications stored in the second data structure to the set of geometries stored in the first data structure to form a modified set of geometries;
generating the third data structure having the second type, the third data structure configured to store the modified set of geometries; and
storing the modified set of geometries in the third data structure.

2. The non-transitory machine-readable medium of claim 1 , wherein determining the second type of data structure based on the first and second sets of statistics data comprises:
identifying the subset of the plurality of types of data structures based on the first and second sets of statistics data;
determining cost values for each type of data structure in the subset of the plurality of types of data structures based on the first and second sets of statistics data; and
determining a type of data structure from the subset of the plurality of types of data structures as the second type of data structure based on the determined cost values.

3. The non-transitory machine-readable medium of claim 2 , wherein the cost values for each type of data structure in the subset of the plurality of types of data structures comprises the storage cost value and the set of query performance cost values.

4. The non-transitory machine-readable medium of claim 1 , wherein the modifications to the set of geometries comprises an addition of a geometry to the set of geometries.

5. The non-transitory machine-readable medium of claim 1 , wherein the modifications to the set of geometries comprises a removal of a geometry from the set of geometries.

6. The non-transitory machine-readable medium of claim 1 , wherein the first data structure is immutable.

7. A method comprising:
identifying a first data structure having a first type, the first data structure configured to store a set of geometries;
identifying a second data structure associated with the first data structure, the second data structure configured to store modifications to the set of geometries; and
performing a merge operation on the first data structure and the second data structure to form a third data structure by:
determining a first set of statistics data associated with the modifications to the set of geometries stored in the second data structure;
retrieving a second set of statistics data associated with the set of geometries stored in the first data structure;
determining a second type of data structure based on a storage cost value and a set of query performance cost values for each of a subset of a plurality of types of data structures identified based on the first and second sets of statistics data, wherein a defined weight value is applied to each query performance cost value in the set of query performance cost values;
applying the modifications stored in the second data structure to the set of geometries stored in the first data structure to form a modified set of geometries;
generating the third data structure having the second type, the third data structure configured to store the modified set of geometries; and
storing the modified set of geometries in the third data structure.

8. The method of claim 7 , wherein determining the second type of data structure based on the first and second sets of statistics data comprises:
identifying the subset of the plurality of types of data structures based on the first and second sets of statistics data;
determining cost values for each type of data structure in the subset of the plurality of types of data structures based on the first and second sets of statistics data; and
determining a type of data structure from the subset of the plurality of types of data structures as the second type of data structure based on the determined cost values.

9. The method of claim 8 , wherein the cost values for each type of data structure in the subset of the plurality of types of data structures comprises the storage cost value and the set of query performance cost values.

10. The method of claim 7 , wherein the modifications to the set of geometries comprises an addition of a geometry to the set of geometries.

11. The method of claim 7 , wherein the modifications to the set of geometries comprises a removal of a geometry from the set of geometries.

12. The method of claim 7 , wherein the first data structure is immutable.

13. A system comprising:
a set of processing units; and
a non-transitory machine-readable medium storing instructions that when executed by at least one processing unit in the set of processing units cause the at least one processing unit to:
identify a first data structure having a first type, the first data structure configured to store a set of geometries;
identify a second data structure associated with the first data structure, the second data structure configured to store modifications to the set of geometries; and
perform a merge operation on the first data structure and the second data structure to form a third data structure by:
determining a first set of statistics data associated with the modifications to the set of geometries stored in the second data structure;
retrieving a second set of statistics data associated with the set of geometries stored in the first data structure;
determining a second type of data structure based on a storage cost value and a set of query performance cost values for each of a subset of a plurality of types of data structures identified based on the first and second sets of statistics data, wherein a defined weight value is applied to each query performance cost value in the set of query performance cost values;
applying the modifications stored in the second data structure to the set of geometries stored in the first data structure to form a modified set of geometries;
generating the third data structure having the second type, the third data structure configured to store the modified set of geometries; and
storing the modified set of geometries in the third data structure.

14. The system of claim 13 , wherein determining the second type of data structure based on the first and second sets of statistics data comprises:
identifying the subset of the plurality of types of data structures based on the first and second sets of statistics data;
determining cost values for each type of data structure in the subset of the plurality of types of data structures based on the first and second sets o

Assignees

• Sap Se

Inventors

• Bastian Kai-Niklas
• Jung Michael

Classifications

• G06F16/29 Primary

  Geographical information databases · CPC title

• G06F16/2462 Primary

  Approximate or statistical queries · CPC title

• G06F16/258

  Data format conversion from or to a database · CPC title

• G06F17/18

  for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title

• G06F16/90335

  Query processing · CPC title