Processing spatial joins using a mapreduce framework

• US 9,311,380 B2
• Filed: 03/29/2013
• Issued: 04/12/2016
• Est. Priority Date: 03/29/2013
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chawda, Bhupesh S., Gupta, Himanshu, Subramaniam, L. Venkata, Faruquie, Tanveer A
• Primary Examiner(s): Reyes, Mariela
• Assistant Examiner(s): VU, THONG H
• Application Number:
  US13/853,451
• Publication Number:
  US 20140297585A1
• Time in Patent Office: 1,110 Days
• Field of Search: 707/737, 707/610, 707/639, 707/743, 707/741
• US Class Current: 1/1
• 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 into multiple portions of partitioned spatial data via a MapReduce framework 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 each of the multiple portions of the partitioned spatial data domain based on one or more spatial predicates of a query, wherein;

said at least one operation is selected from a group consisting of (i) a project operation that determines a partition in which the start point of a given spatial data object resides, (ii) a split operation that determines all partitions that share at least one point of a given spatial data object, and (iii) a replication operation that determines all partitions that satisfy a given condition; and

said one or more spatial predicates are selected from a group consisting of (i) an overlap parameter that indicates that two or more portions of the spatial data each possess at least one identical value, (ii) a range parameter that indicates that any point in a first portion of the spatial data is within a given distance of any point in a second portion of the spatial data, and (iii) a nearest neighbor parameter that indicates that a first portion of the spatial data is nearer to a second portion of the spatial data than any other portion of the spatial data; and

executing the at least one defined operation on each of the multiple portions of the partitioned spatial data domain to determine a response to the query, wherein each of the multiple portions of the partitioned spatial data is processed exclusively by a distinct map task within the MapReduce framework;

wherein said partitioning, said defining, and said executing are 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, comprising:

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

9. 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 into multiple portions of partitioned spatial data via a MapReduce framework 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 each of the multiple portions of the partitioned spatial data domain based on one or more spatial predicates of a query, wherein;

said at least one operation is selected from a group consisting of (i) a project operation that determines a partition in which the start point of a given spatial data object resides, (ii) a split operation that determines all partitions that share at least one point of a given spatial data object, and (iii) a replication operation that determines all partitions that satisfy a given condition; and

said one or more spatial predicates are selected from a group consisting of (i) an overlap parameter that indicates that two or more portions of the spatial data each possess at least one identical value, (ii) a range parameter that indicates that any point in a first portion of the spatial data is within a given distance of any point in a second portion of the spatial data, and (iii) a nearest neighbor parameter that indicates that a first portion of the spatial data is nearer to a second portion of the spatial data than any other portion of the spatial data; and

executing the at least one defined operation on each of the multiple portions of the partitioned spatial data domain to determine a response to the query, wherein each of the multiple portions of the partitioned spatial data is processed exclusively by a distinct map task within the MapReduce framework.

10. The article of manufacture of claim 9, 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.

11. A system comprising:

a memory; and

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

partitioning a spatial data domain into multiple portions of partitioned spatial data via a MapReduce framework 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 each of the multiple portions of the partitioned spatial data domain based on one or more spatial predicates of a query, wherein;

said at least one operation is selected from a group consisting of (i) a project operation that determines a partition in which the start point of a given spatial data object resides, (ii) a split operation that determines all partitions that share at least one point of a given spatial data object, and (iii) a replication operation that determines all partitions that satisfy a given condition; and

said one or more spatial predicates are selected from a group consisting of (i) an overlap parameter that indicates that two or more portions of the spatial data each possess at least one identical value, (ii) a range parameter that indicates that any point in a first portion of the spatial data is within a given distance of any point in a second portion of the spatial data, and (iii) a nearest neighbor parameter that indicates that a first portion of the spatial data is nearer to a second portion of the spatial data than any other portion of the spatial data; and

executing the at least one defined operation on each of the multiple portions of the partitioned spatial data domain to determine a response to the query, wherein each of the multiple portions of the partitioned spatial data is processed exclusively by a distinct map task within the MapReduce framework.

12. A method comprising:

partitioning a spatial data domain into multiple portions of partitioned spatial data via a MapReduce framework 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 spatial predicates of a query against each bounding in the partitioned spatial data domain to one or more of the one or more spatial predicates that are applicable to the spatial data objects;

defining at least one operation to be performed on each of the multiple portions of the partitioned spatial data domain based on one or more spatial predicates of a query, wherein;

said at least one operation is selected from a group consisting of (i) a project operation that determines a partition in which the start point of a given spatial data object resides, (ii) a split operation that determines all partitions that share at least one point of a given spatial data object, and (iii) a replication operation that determines all partitions that satisfy a given condition; and

said one or more spatial predicates are selected from a group consisting of (i) an overlap parameter that indicates that two or more portions of the spatial data each possess at least one identical value, (ii) a range parameter that indicates that any point in a first portion of the spatial data is within a given distance of any point in a second portion of the spatial data, and (iii) a nearest neighbor parameter that indicates that a first portion of the spatial data is nearer to a second portion of the spatial data than any other portion of the spatial data

executing the at least one defined operation on each of the multiple portions of the partitioned spatial data domain to determine a response to the query, wherein each of the multiple portions of the partitioned spatial data is processed exclusively by a distinct map task within the MapReduce framework;

wherein said partitioning, said implementing, said processing, said defining, and said executing are carried out by a computer device.