The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Oct. 06, 2015
Filed:
Mar. 08, 2013
International Business Machines Corporation, Armonk, NY (US);
Iowa State University Research Foundation, Inc., Ames, IA (US);
Srikanta N Tirthapura, Ames, IA (US);
David P Woodruff, Mountain View, CA (US);
International Business Machines Corporation, Armonk, NY (US);
Iowa State University Research Foundation, Inc., Ames, IA (US);
Abstract
A method for estimating aggregates over a stream of axis-aligned rectangles, includes: decomposing the stream along one-dimensional intervals, wherein vertices for the rectangle are located in a predetermined grid; assigning each grid row to buckets, wherein the one-dimensional intervals are placed into buckets according to the corresponding rows in which the one-dimensional intervals are positioned; 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 a first interval corresponding to a given rectangle, wherein the interval has hash function results that meet a predetermined threshold; and inserting a second interval for the rectangle corresponding to the first interval into a one-dimensional algorithm for the corresponding bucket meeting the predetermined threshold.