Summarizing a stream of multidimensional, axis-aligned rectangles

1. A computer program product, comprising:

a non-transitory computer readable storage medium to store a computer readable program, wherein the computer readable program, when executed by a processor within a computer, causes the computer to perform operations for estimating aggregates over a stream of axis-aligned rectangles, the operations comprising:

decomposing a stream of data represented by a plurality of axis-aligned rectangles along one-dimensional intervals, wherein all vertices for each rectangle are located in a grid having a predetermined area;

assigning each row in the grid to one of a plurality of buckets, wherein the one-dimensional intervals for each rectangle are placed into the buckets according to the corresponding rows in which the one-dimensional intervals are positioned;

maintaining an instance of a one-dimensional algorithm in each bucket; and

estimating a sum of a number of grid points touched by at least one of the rectangles in each row of the grid to approximate a volume of the axis-aligned rectangles by:

using pairwise-independent hash functions in a multi-dimensional algorithm to determine buckets that include an interval corresponding to a given rectangle, wherein the interval has hash function results that meet a predetermined threshold; and

inserting the interval for the rectangle into the one-dimensional algorithm for the corresponding bucket having hash function results that meet the predetermined threshold.

2. The computer program product of claim 1 , wherein assigning each row in the grid further comprises:

subsampling each row in the grid into a plurality of levels; and

randomly hashing the subsampled rows into the plurality of buckets.

3. The computer program product of claim 2 , wherein subsampling each row further comprises subsampling the rows into a number of levels based on a number of rows in the grid.

4. The computer program product of claim 1 , wherein a number of buckets is constant based on a number of rows in the grid.

5. The computer program product of claim 1 , wherein inserting the interval for the rectangle corresponding to the one-dimensional interval into the one-dimensional algorithm for the corresponding bucket further comprises updating a sketch for a zeroth frequency moment for the corresponding bucket.

6. The computer program product of claim 1 , wherein using the pairwise-independent hash functions further comprises rejecting rows in the grid that comprise hash function results below the predetermined threshold.

7. The computer program product of claim 1 , wherein decomposing the stream of data further comprises:

imposing the grid on the axis-aligned rectangles; and

shifting the rectangles to fit to the grid points.

8. A method for estimating aggregates over a stream of axis-aligned rectangles, comprising:

decomposing a stream of data represented by a plurality of axis-aligned rectangles along one-dimensional intervals, wherein all vertices for each rectangle are located in a grid having a predetermined area;

assigning each row in the grid to one of a plurality of buckets, wherein the one-dimensional intervals for each rectangle are placed into the buckets according to the corresponding rows in which the one-dimensional intervals are positioned;

maintaining an instance of a one-dimensional algorithm in each bucket; and

estimating a sum of a number of grid points touched by at least one of the rectangles in each row of the grid to approximate a volume of the axis-aligned rectangles by:

using pairwise-independent hash functions in a multi-dimensional algorithm to determine buckets that include an interval corresponding to a given rectangle, wherein the interval has hash function results that meet a predetermined threshold; and

inserting the interval for the rectangle into the one-dimensional algorithm for the corresponding bucket having hash function results that meet the predetermined threshold.

9. The method of claim 8 , wherein assigning each row in the grid further comprises:

subsampling each row in the grid into a plurality of levels; and

randomly hashing the subsampled rows into the plurality of buckets.

10. The method of claim 9 , wherein subsampling each row further comprises subsampling the rows into a number of levels based on a number of rows in the grid.

11. The method of claim 8 , wherein a number of buckets is constant based on a number of rows in the grid.

12. The method of claim 8 , wherein inserting the interval for the rectangle corresponding to the one-dimensional interval into the one-dimensional algorithm for the corresponding bucket further comprises updating a sketch for a zeroth frequency moment for the corresponding bucket.

13. The method of claim 8 , wherein using the pairwise-independent hash functions further comprises rejecting rows in the grid that comprise hash function results below the predetermined threshold.

14. The method of claim 8 , wherein decomposing the stream of data further comprises:

imposing the grid on the axis-aligned rectangles; and

shifting the rectangles to fit to the grid points.

15. An aggregate approximation system, comprising:

a receiver configured to receive a stream of data represented by a plurality of axis-aligned rectangles along one-dimensional intervals;

a volume estimator configured to:

decompose the stream of data, wherein all vertices for each rectangle are located in a grid having a predetermined area;

assign each row in the grid to one of a plurality of buckets, wherein the one-dimensional intervals for each rectangle are placed into the buckets according to the corresponding rows in which the one-dimensional intervals are positioned;

maintain an instance of a one-dimensional algorithm in each bucket; and

estimate a sum of a number of grid points touched by at least one of the rectangles in each row of the grid to approximate a volume of the axis-aligned rectangles by:

using pairwise-independent hash functions in a multi-dimensional algorithm to determine buckets that include an interval corresponding to a given rectangle, wherein the interval has hash function results that meet a predetermined threshold; and

inserting the interval for the rectangle into the one-dimensional algorithm for the corresponding bucket having hash function results that meet the predetermined threshold.

16. The system of claim 15 , wherein assigning each row in the grid further comprises:

subsampling each row in the grid into a plurality of levels; and

randomly hashing the subsampled rows into the plurality of buckets.

17. The system of claim 16 , wherein subsampling each row further comprises subsampling the rows into a number of levels based on a number of rows in the grid.

18. The system of claim 15 , wherein inserting the interval for the rectangle corresponding to the one-dimensional interval into the one-dimensional algorithm for the corresponding bucket further comprises updating a sketch for a zeroth frequency moment for the corresponding bucket.

19. The system of claim 15 , wherein using the pairwise-independent hash functions further comprises rejecting rows in the grid that comprise hash function results below the predetermined threshold.

20. The system of claim 15 , wherein decomposing the stream of data further comprises:

imposing the grid on the axis-aligned rectangles; and

shifting the rectangles to fit to the grid points.