Method and mechanism for performing spatial joins
First Claim
1. A method of determining which of a plurality of first objects interacts within a space with which of a plurality of second objects according to a spatial predicate, said method comprising the computer-implemented steps of:
- decomposing the plurality of first objects and the plurality of second objects into respective sets of one or more cells, wherein each cell of the respective sets of one or more cells defines a region in said space and has a cell size no larger than a predetermined cell size;
filtering from among pairs of the first objects and second objects, respectively, to determine first candidate pairs of the first objects and the second objects, respectively, that share common cells at the predetermined cell size, andfiltering from among the first candidate pairs of the first objects and second objects, respectively, to determine second candidate pairs of the first objects and the second objects, respectively, that share overlapping cells of cell sizes smaller than the predetermined cell size; and
selecting from among the second candidate pairs resulting pairs of the first objects and the second objects that indicate a first object that interacts with the second object according to the spatial predicate.
2 Assignments
0 Petitions
Accused Products
Abstract
A method and mechanism for performing a spatial join between two sets of objects employs a two-pass primary filter. The objects are decomposed into variable-sized cells no larger than a predetermined cell size and stored in respective spatial indexes. The spatial indexes include a code for the variable-size cells of the object and a code for the fixed-size supercell of the variable-size cells. The first pass can be implemented as an equijoin filtering operation using the fixed-size cell codes corresponding to the predetermined cell size, and the second pass as a join operation using the variable-size cell codes at smaller cell sizes.
67 Citations
30 Claims
-
1. A method of determining which of a plurality of first objects interacts within a space with which of a plurality of second objects according to a spatial predicate, said method comprising the computer-implemented steps of:
-
decomposing the plurality of first objects and the plurality of second objects into respective sets of one or more cells, wherein each cell of the respective sets of one or more cells defines a region in said space and has a cell size no larger than a predetermined cell size; filtering from among pairs of the first objects and second objects, respectively, to determine first candidate pairs of the first objects and the second objects, respectively, that share common cells at the predetermined cell size, and filtering from among the first candidate pairs of the first objects and second objects, respectively, to determine second candidate pairs of the first objects and the second objects, respectively, that share overlapping cells of cell sizes smaller than the predetermined cell size; and selecting from among the second candidate pairs resulting pairs of the first objects and the second objects that indicate a first object that interacts with the second object according to the spatial predicate. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A computer-readable medium bearing instructions for determining which of a plurality of first objects interacts within a space with which of a plurality of second objects according to a spatial predicate, said instructions, when executed by one or more processors, arranged to cause the one or more processors to perform the steps of:
-
decomposing the plurality of first objects and the plurality of second objects into respective sets of one or more cells, wherein each cell of the respective sets of one or more cells defines a region in said space and has a cell size no larger than a predetermined cell size; filtering from among pairs of the first objects and second objects, respectively, to determine first candidate pairs of the first objects and the second objects, respectively, that share common cells at the predetermined cell size, and filtering from among the first candidate pairs of the first objects and second objects, respectively, to determine second candidate pairs of the first objects and the second objects, respectively, that share overlapping cells of cell sizes smaller than the predetermined cell size; and selecting from among the second candidate pairs resulting pairs of the first objects and the second objects that indicate a first object that interacts with the second object according to the spatial predicate. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. A method of performing a spatial join according to a spatial predicate of a set of first objects and a set of second objects, comprising the computer-implemented steps of:
-
building a first spatial index for the set of first objects, said first spatial index including an entry indicating an identifier for one of the first objects, a fixed-length code identifying a location of a cell in which at least part of the one of the first object exists, and a variable-length code identifying a location of a cell in which at least part of the one of the first object exists; building a second spatial index for the set of second objects, said second spatial index including an entry indicating an identifier for one of the second objects, a fixed-length code identifying a location of a cell in which at least part of the one of the second object exists, and a variable-length code identifying a location of a cell in which at least part of the one of the second object exists; performing a first join operation on the first spatial index and the second spatial index based on the fixed-length codes; performing a second join operation on results of the first join operation based on the variable length codes; and performing a spatial join operation on results of the second join operation based on the spatial predicate. - View Dependent Claims (20, 21)
-
-
22. A computer-readable medium bearing instructions for performing a spatial join according to a spatial predicate of a set of first objects and a set of second objects, said instructions arranged, when executed by one or more processors, to cause the one or more processors to perform the steps of:
-
building a first spatial index for the set of first objects, said first spatial index including an entry indicating an identifier for one of the first objects, a fixed-length code identifying a location of a cell in which part of the one of the first object exists, and a variable-length code identifying a location of a cell in which part of the one of the first object exists; building a second spatial index for the set of second objects, said second spatial index including an entry indicating an identifier for one of the second objects, a fixed-length code identifying a location of a cell in which part of the one of the second object exists, and a variable-length code identifying a location of a cell in which part of the one of the second object exists; performing a first join operation on the first spatial index and the second spatial index based on the fixed-length codes; performing a second join operation on results of the first join operation based on the variable length codes; and performing a spatial join operation on results of the second join operation based on the spatial predicate. - View Dependent Claims (23, 24)
-
-
25. A method of performing a spatial join according to a spatial predicate of a set of first objects and a set of second objects, comprising the computer-implemented steps of:
-
performing a first join operation between the set of first objects and the set of second objects based on fixed-length codes identifying cells in which at least part of the first objects and second objects exist; performing a second join operation on results of the first join operation based on the variable length codes identifying cells in which at least part of the first objects and second objects exist; and performing a spatial join operation on results of the second join operation based on the spatial predicate. - View Dependent Claims (26, 27)
-
-
28. A computer-readable medium performing a spatial join according to a spatial predicate of a set of first objects and a set of second objects, said instructions arranged, when executed by one or more processors, to cause the one or more processors to perform the steps of:
-
performing a first join operation between the set of first objects and the set of second objects based on fixed-length codes identifying cells in which at least part of the first objects and second objects exist; performing a second join operation on results of the first join operation based on the variable length codes identifying cells in which at least part of the first objects and second objects exist; and performing a spatial join operation on results of the second join operation based on the spatial predicate. - View Dependent Claims (29, 30)
-
Specification