Processing Spatial Joins Using a Mapreduce Framework

• US 20140297585A1
• Filed: 03/29/2013
• Published: 10/02/2014
• Est. Priority Date: 03/29/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gupta, Himanshu, Subramaniam, L. Venkata, Chawda, Bhupesh S., Faruquie, Tanveer A.
• Granted Patent: US 9,311,380 B2
• Time in Patent Office: Days
• US Class Current: 707/610
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning

Abstract

Techniques, systems, and articles of manufacture for processing spatial joins using a MapReduce framework. A method includes partitioning a spatial data domain based on a distribution of spatial data objects across multiple nodes of a cluster of machines, defining at least one operation to be performed on the partitioned spatial data domain based on one or more predicates of a query, and executing the at least one defined operation on the partitioned spatial data domain to determine a response to the query.

Claims

1. A method comprising:

partitioning a spatial data domain based on a distribution of spatial data objects across multiple nodes of a cluster of machines;

defining at least one operation to be performed on the partitioned spatial data domain based on one or more predicates of a query; and

executing the at least one defined operation on the partitioned spatial data domain to determine a response to the query;

wherein at least one of the steps is carried out by a computer device.

2. The method of claim 1, comprising:

defining the distribution of spatial data objects across multiple nodes of the cluster of machines.

3. The method of claim 2, wherein said defining comprises defining the distribution of spatial data objects such that said distribution of spatial data objects across the multiple nodes of the cluster of machines is balanced.

4. The method of claim 1, wherein said partitioning comprises partitioning the spatial data domain in the x-dimension and/or the y-dimension of the spatial data domain.

5. The method of claim 1, wherein said partitioning comprises partitioning in accordance with a partition strategy.

6. The method of claim 1, wherein said partitioning comprises configuring multiple containers in the x-dimension and/or the y-dimension of the spatial data domain, wherein each of the multiple containers has a uniform size.

7. The method of claim 6, comprising:

determining the number of spatial data objects starting in each of the multiple containers; and

merging one or more partitions in the spatial data domain such that each resulting partition has an equal number of spatial data objects.

8. The method of claim 1, wherein said one or more predicates comprise at least one of an overlap parameter, a range parameter, and a nearest neighbor parameter.

9. The method of claim 1, wherein said at least one operation comprises at least a project operation, wherein said project operation determines a partition in which the start point of a spatial data object resides.

10. The method of claim 1, wherein said at least one operation comprises at least a split operation, wherein said split operation determines all partitions that share at least one point of a spatial data object.

11. The method of claim 1, wherein said at least one operation comprises at least a replication operation, wherein said replication operation determines all partitions that satisfy a given condition.

12. The method of claim 1, comprising:

compiling two or more spatial joins on the spatial data domain determined in response to the query to generate a composite output.

13. An article of manufacture comprising a computer readable storage medium having computer readable instructions tangibly embodied thereon which, when implemented, cause a computer to carry out a plurality of method steps comprising:

partitioning a spatial data domain based on a distribution of spatial data objects across multiple nodes of a cluster of machines;

defining at least one operation to be performed on the partitioned spatial data domain based on one or more predicates of a query; and

executing the at least one defined operation on the partitioned spatial data domain to determine a response to the query.

14. The article of manufacture of claim 13, wherein said one or more predicates comprise at least one of an overlap parameter, a range parameter, and a nearest neighbor parameter.

15. The article of manufacture of claim 13, wherein said at least one operation comprises at least a project operation, wherein said project operation determines a partition in which the start point of a spatial data object resides.

16. The article of manufacture of claim 13, wherein said at least one operation comprises at least a split operation, wherein said split operation determines all partitions that share at least one point of a spatial data object.

17. The article of manufacture of claim 13, wherein said at least one operation comprises at least a replication operation, wherein said replication operation determines all partitions that satisfy a given condition.

18. The article of manufacture of claim 13, wherein the method steps comprise:

compiling two or more spatial joins on the spatial data domain determined in response to the query to generate a composite output.

19. A system comprising:

at least one distinct software module, each distinct software module being embodied on a tangible computer-readable medium;

a memory; and

at least one processor coupled to the memory and operative for;

partitioning a spatial data domain based on a distribution of spatial data objects across multiple nodes of a cluster of machines;

defining at least one operation to be performed on the partitioned spatial data domain based on one or more predicates of a query; and

executing the at least one defined operation on the partitioned spatial data domain to determine a response to the query.

20. A method comprising:

partitioning a spatial data domain based on a distribution of spatial data objects across multiple nodes of a cluster of machines;

implementing a bounding around each spatial data object in the partitioned spatial data domain;

processing one or more predicates of a query against each bounding in the partitioned spatial data domain to one or more of the one or more predicates that are applicable to the spatial data objects;

defining at least one operation to be performed on the partitioned spatial data domain based on the one or more predicates of the query; and

executing the at least one defined operation on the partitioned spatial data domain to determine a response to the query;

wherein at least one of the steps is carried out by a computer device.