Geospatial queries using associated distribution data

• US 9,336,236 B2
• Filed: 01/21/2014
• Issued: 05/10/2016
• Est. Priority Date: 01/21/2014
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Statchuk, Craig A.
• Primary Examiner(s): Robinson, Greta
• Application Number:
  US14/159,528
• Publication Number:
  US 20150205838A1
• Time in Patent Office: 840 Days
• Field of Search: 707/713, 707/714, 707/724, 707/743, 707/E17.054
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

Embodiments of the present invention disclose a method, computer program product, and system for optimizing spatial queries, the method comprising a computer receiving a spatial data set, and a target spatial shape. The computer determining a distribution data set which aligns with the geometry of the spatial data set. The computer performing a query to determine a list of full and partial shapes of the spatial data set located within the target spatial shape. The computer determining a ratio for a determined partial shape of the spatial data set using the distribution data set. The computer determining an apportioned value of a variable of the spatial data set within the determined partial shape. The computer summarizing into a result set the value of the variable within the determined list of full and partial shapes of the spatial data set.

Claims

1. A method for optimizing spatial queries, the method comprising:

a computer receiving a first spatial data set and a target spatial shape, wherein a geometry of the first spatial data set does not align with a geometry of the target spatial shape;

the computer receiving a distribution data set, wherein the geometry of the distribution data set aligns with the geometry of the first spatial data set;

the computer performing a query including one or more of an intersection query and a union query to determine a list of full and partial shapes of the first spatial data set which are located within the target spatial shape;

the computer determining a ratio for a determined partial shape of the first spatial data set using the distribution data set;

the computer determining an apportioned value of a variable of the first spatial data set within the determined partial shape, wherein the apportioned value of the variable is based on a full value of the variable and the determined ratio; and

the computer summarizing into a result set the value of the variable within the determined list of full and partial shapes of the first spatial data set, and outputting the result set.

2. The method of claim 1, further comprising:

the computer determining whether the geometry of the first spatial data set does not align with the geometry of the target spatial shape, wherein i.) the geometry of the first spatial data set includes at least one shape defined by points, lines, or polygons, ii.) the geometry of the target spatial shape includes at least one shape defined by points, lines, or polygons, iii.) the first spatial data set encompasses the target spatial shape, and iv.) a sub-set of one or more full shapes within the first spatial data set cannot be combined to form a composite shape equivalent to the target spatial shape.

3. The method of claim 1, further comprising:

the computer determining whether the geometry of the distribution data set aligns with the geometry of the first spatial data set, wherein i.) the geometry of the distribution data set includes at least one shape defined by points, lines, or polygons, and ii.) a sub-set of one or more full shapes within the distribution data set can be combined to form a composite shape equivalent to each full shape within the first spatial data set.

4. The method of claim 1, wherein the computer determining a ratio for a determined partial shape of the first spatial data set using the distribution data set comprises:

the computer identifying a full shape of the first spatial data set which encompasses the determined partial shape of the first spatial data set;

the computer identifying a composite shape of the distribution data set which is equivalent to the identified full shape of the first spatial data set;

the computer determining a boundary curve that separates the identified full shape of the first spatial data set with the determined partial shape of the first spatial data set; and

the computer determining a ratio of a data density from the distribution data set within the determined partial shape of the first spatial data set compared to a data density from the distribution data set within the identified composite shape of the distribution data set.

5. The method of claim 4, further comprising:

the computer determining the data density from the distribution data set by calculating a volume under a graph of the distribution data set.

6. The method of claim 1, further comprising:

the computer receiving a second spatial data set, wherein the geometry of the first spatial data set does not align with the geometry of the second spatial set; and

the computer performing a query including one or more of an intersection query and a union query to determine a list of full and partial shapes from the second spatial data set which are located within the target spatial shape.

7. The method of claim 1, further comprising:

the computer receiving a second spatial data set and criteria which defines the target spatial shape from a sub-set of one or more full shapes within the second spatial data set.

8. A computer program product for optimizing spatial queries, the computer program product comprising:

one or more computer-readable storage media and program instructions stored on the one or more computer-readable storage media, the program instructions comprising;

program instructions to receive a first spatial data set and a target spatial shape, wherein a geometry of the first spatial data set does not align with a geometry of the target spatial shape;

program instructions to receive a distribution data set, wherein the geometry of the distribution data set aligns with the geometry of the first spatial data set;

program instructions to perform a query including one or more of an intersection query and a union query to determine a list of full and partial shapes of the first spatial data set which are located within the target spatial shape;

program instructions to determine a ratio for a determined partial shape of the first spatial data set using the distribution data set;

program instructions to determine an apportioned value of a variable of the first spatial data set within the determined partial shape, wherein the apportioned value of the variable is based on a full value of the variable and the determined ratio; and

program instructions to summarize into a result set the value of the variable within the determined list of full and partial shapes of the first spatial data set, and output the result set.

9. The computer program product of claim 8, further comprising:

program instructions to determine whether the geometry of the first spatial data set does not align with the geometry of the target spatial shape, wherein i.) the geometry of the first spatial data set includes at least one shape defined by points, lines, or polygons, ii.) the geometry of the target spatial shape includes at least one shape defined by points, lines, or polygons, iii.) the first spatial data set encompasses the target spatial shape, and iv.) a sub-set of one or more full shapes within the first spatial data set cannot be combined to form a composite shape equivalent to the target spatial shape.

10. The computer program product of claim 8, further comprising:

program instructions to determine whether the geometry of the distribution data set aligns with the geometry of the first spatial data set, wherein i.) the geometry of the distribution data set includes at least one shape defined by points, lines, or polygons, and ii.) a sub-set of one or more full shapes within the distribution data set can be combined to form a composite shape equivalent to each full shape within the first spatial data set.

11. The computer program product of claim 8, wherein program instructions to determine a ratio for a determined partial shape of the first spatial data set using the distribution data set comprises:

program instructions to identify a full shape of the first spatial data set which encompasses the determined partial shape of the first spatial data set;

program instructions to identify a composite shape of the distribution data set which is equivalent to the identified full shape of the first spatial data set;

program instructions to determine a boundary curve that separates the identified full shape of the first spatial data set with the determined partial shape of the first spatial data set; and

program instructions to determine a ratio of a data density from the distribution data set within the determined partial shape of the first spatial data set compared to a data density from the distribution data set within the identified composite shape of the distribution data set.

12. The computer program product of claim 11, further comprising:

program instructions to determine the data density from the distribution data set by calculating a volume under a graph of the distribution data set.

13. The computer program product of claim 8, further comprising:

program instructions to receive a second spatial data set, wherein the geometry of the first spatial data set does not align with the geometry of the second spatial set; and

program instructions to perform a query including one or more of an intersection query and a union query to determine a list of full and partial shapes from the second spatial data set which are located within the target spatial shape.

14. The computer program product of claim 8, further comprising:

program instructions to receive a second spatial data set and criteria which defines the target spatial shape from a sub-set of one or more full shapes within the second spatial data set.

15. A computer system for optimizing spatial queries, the computer system comprising:

one or more computer processors;

one or more computer-readable storage media;

program instructions stored on the computer-readable storage media for execution by at least one of the one or more processors, the program instructions comprising;

program instructions to receive a first spatial data set and a target spatial shape, wherein a geometry of the first spatial data set does not align with a geometry of the target spatial shape;

program instructions to receive a distribution data set, wherein the geometry of the distribution data set aligns with the geometry of the first spatial data set;

program instructions to perform a query including one or more of an intersection query and a union query to determine a list of full and partial shapes of the first spatial data set which are located within the target spatial shape;

program instructions to determine a ratio for a determined partial shape of the first spatial data set using the distribution data set;

program instructions to determine an apportioned value of a variable of the first spatial data set within the determined partial shape, wherein the apportioned value of the variable is based on a full value of the variable and the determined ratio; and

program instructions to summarize into a result set the value of the variable within the determined list of full and partial shapes of the first spatial data set, and output the result set.

16. The computer system of claim 15, further comprising:

program instructions to determine whether the geometry of the first spatial data set does not align with the geometry of the target spatial shape, wherein i.) the geometry of the first spatial data set includes at least one shape defined by points, lines, or polygons, ii.) the geometry of the target spatial shape includes at least one shape defined by points, lines, or polygons, iii.) the first spatial data set encompasses the target spatial shape, and iv.) a sub-set of one or more full shapes within the first spatial data set cannot be combined to form a composite shape equivalent to the target spatial shape.

17. The computer system of claim 15, further comprising:

program instructions to determine whether the geometry of the distribution data set aligns with the geometry of the first spatial data set, wherein i.) the geometry of the distribution data set includes at least one shape defined by points, lines, or polygons and ii.) a sub-set of one or more full shapes within the distribution data set can be combined to form a composite shape equivalent to each full shape within the first spatial data set.

18. The computer system of claim 15, wherein program instructions to determine a ratio for a determined partial shape of the first spatial data set using the distribution data set comprises:

program instructions to identify a full shape of the first spatial data set which encompasses the determined partial shape of the first spatial data set;

program instructions to identify a composite shape of the distribution data set which is equivalent to the identified full shape of the first spatial data set;

program instructions to determine a boundary curve that separates the identified full shape of the first spatial data set with the determined partial shape of the first spatial data set; and

program instructions to determine a ratio of a data density from the distribution data set within the determined partial shape of the first spatial data set compared to a data density from the distribution data set within the identified composite shape of the distribution data set.

19. The computer system of claim 18, further comprising:

program instructions to determine the data density from the distribution data set by calculating a volume under a graph of the distribution data set.

20. The computer system of claim 15, further comprising:

program instructions to receive a second spatial data set, wherein the geometry of the first spatial data set does not align with the geometry of the second spatial set; and

program instructions to perform a query including one or more of an intersection query and a union query to determine a list of full and partial shapes from the second spatial data set which are located within the target spatial shape.