CONSTRUCTING MULTIDIMENSIONAL HISTOGRAMS FOR COMPLEX SPATIAL GEOMETRY OBJECTS
First Claim
1. A method comprising:
- identifying spatial objects in an multidimensional space, each of the spatial objects covering an extent of the multidimensional space;
dividing the multidimensional space into partitions;
for each particular partition of the partitions, estimating a weighted count of how many of the spatial objects overlap with the particular partition;
wherein estimating the weighted count for a first particular partition comprises weighting each particular spatial object in a first subset of the spatial objects based on how much each particular spatial object overlaps with the first particular partition, wherein the each particular spatial object in the first subset of the spatial objects only partially overlaps the first particular partition;
wherein the method is performed by one or more computing devices.
1 Assignment
0 Petitions
Accused Products
Abstract
Techniques are described for generating histograms for a multidimensional space. In the presence of large spatial objects, fuzzy splitting techniques are utilized to recursively divide the multidimensional space into partitions, where a single spatial object may belong to multiple partitions. Large spatial objects are essentially broken down into smaller objects that may allow for more efficient partitioning of the multidimensional space. A count of spatial objects in each partition yields a spatial histogram. A spatial object that belongs to multiple partitions may have a weighted count for each of the multiple partitions, based on the extent to which the spatial object overlaps with each partition. Thus, an object that is split among a handful of partitions will only contribute a fraction of a count to each partition. Small partitions having relatively few objects are avoided by refusing to subdivide a partition whose members drop below a threshold number.
31 Citations
19 Claims
-
1. A method comprising:
-
identifying spatial objects in an multidimensional space, each of the spatial objects covering an extent of the multidimensional space; dividing the multidimensional space into partitions; for each particular partition of the partitions, estimating a weighted count of how many of the spatial objects overlap with the particular partition; wherein estimating the weighted count for a first particular partition comprises weighting each particular spatial object in a first subset of the spatial objects based on how much each particular spatial object overlaps with the first particular partition, wherein the each particular spatial object in the first subset of the spatial objects only partially overlaps the first particular partition; wherein the method is performed by one or more computing devices. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A method comprising:
-
dividing a multidimensional space into a set of one or more partitions; selecting a particular partition from the set of one or more partitions, based on the particular partition having a largest size among partitions in the set of one or more partitions that overlap with more than a threshold number of spatial objects; splitting the particular partition into multiple partitions and replacing the particular partition in the set of one or more partitions with the multiple partitions; repeating at least the steps of selecting a particular partition and splitting the particular partition with respect to different partitions in the set of one or more partitions, until the set of one or more partitions includes a target number of partitions; generating a histogram that indicates, for each particular partition of the set of one or more partitions, an estimated count of spatial objects that overlap with the particular partition; using the estimated counts in the histogram to identify a query plan for executing a database query involving spatial objects in the multidimensional space; wherein the method is performed by one or more computing devices. - View Dependent Claims (10)
-
-
11. A method comprising:
-
dividing a multidimensional space into a set of one or more partitions; selecting a particular partition from the set of one or more partitions, based on the particular partition having a largest number of spatial objects that overlap with the particular partition; splitting the particular partition into multiple partitions and replacing the particular partition in the set of one or more partitions with the multiple partitions; splitting each spatial object, in a first set of spatial objects that overlap with two or more partitions in the multiple partitions, into multiple spatial objects that are assigned weights based on size relative to each other, each of the multiple spatial objects residing entirely within a different partition of the multiple partitions; repeating at least the steps of selecting a particular partition and splitting the particular partition with respect to different partitions in the set of one or more partitions, until the set of one or more partitions includes a target number of partitions; generating a histogram that indicates, for each particular partition of the set of one or more partitions, an estimated count of spatial objects that overlap with the particular partition, wherein the estimated counts are based in part on the assigned weights; using the estimated counts in the histogram to identify a query plan for executing a database query involving spatial objects in the multidimensional space; wherein the method is performed by one or more computing devices.
-
-
12. One or more non-transitory media storing instructions which, when executed by one or more computing devices, cause performance of:
-
identifying spatial objects in an multidimensional space, each of the spatial objects covering an extent of the multidimensional space; dividing the multidimensional space into partitions; for each particular partition of the partitions, estimating a weighted count of how many of the spatial objects overlap with the particular partition; wherein estimating the weighted count for a first particular partition comprises weighting each particular spatial object in a first subset of the spatial objects based on how much each particular spatial object overlaps with the first particular partition, wherein the each particular spatial object in the first subset of the spatial objects only partially overlaps the first particular partition. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19)
-
Specification