Patent US722682A successfully refreshed from Google Patents.
Patent US5963935A successfully refreshed from Google Patents.
US5963935A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Combining bitmaps within a memory limit
Assignee: Oracle International Corp
•
Filing: 1997-02-28
•
Granted: 1999-10-05
•
Expires: 2017-02-28
Abstract
Abstract A method for combining within memory a limit, a plurality of bitmap streams from bitmaps of indefinite size and number. The bitmap streams are merged into a resulting bitmap which can be used in subsequent logical operations. In order to perform a merge within a memory limit, the method relies on the data compression. When compression by itself may be ineffective, the method produces a resulting bitmap for a reduced range. The ensures the production of a resulting bitmap. When the range is reduced, the method may be repeated to produce a merge for a range beyond the reduced range.
Inventors
- 👤 Cetin Ozbutun
- 👤 Jeffrey I. Cohen
- 👤 Michael Depledge
- 👤 Julian Hyde
- 👤 Hakan Jakobsson
- 👤 Mark Kremer
- 👤 Quoc Tai Tran
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 18:39
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2455; G06F16/24553; G06F16/24558; G06F16/22; G06F16/2228; G06F16/2237; G06F16/2272; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
162 words
A method for combining a plurality of bitmaps to generate a resulting bitmap, the method comprising the steps of: A) selecting a subset of said plurality of bitmaps; B) extracting from said subset of said plurality of bitmaps a set of bitmap segments, wherein said set of bitmap segments includes bitmap segments that cover a particular range of bit positions for each bitmap in said subset of said plurality of bitmaps; C) generating a plurality set of interim bitmap segments based on said set of bitmap segments; D) repeating steps A) through C) until either more than a threshold amount of memory is required to store all interim bitmap segments generated for said particular range of bit positions; or all of said lurality of bitmaps have been selected; and F) if more than said threshold amount of memory is required to store all interim bitmap segments generated for said particular range, then: reducing said particular range, and repeating steps A) through F).
Claim 2
Independent Claim
162 words
A method for combining a plurality of bitmaps to generate a resulting bitmap, the method comprising the steps of: A) selecting a subset of said plurality of bitmaps; B) extracting from said subset of said plurality of bitmaps a set of bitmap segments, wherein said set of bitmap segments includes bitmap segments that cover a particular range of bit positions for each bitmap in said subset of said plurality of bitmaps; C) generating a plurality set of interim bitmap segments based on said set of bitmap segments; D) repeating steps A) through C) until either more than a threshold amount of memory is required to store all interim bitmap segments generated for said particular range of bit positions; or all of said lurality of bitmaps have been selected; and F) if more than said threshold amount of memory is required to store all interim bitmap segments generated for said particular range, then: reducing said particular range, and repeating steps A) through F).
Claim 3
Dependent Claim
22 words
The method of claim 1, wherein the step of generating a set of interim bitmap segments includes generating compressed interim bitmap segments.
Claim 4
Dependent Claim
37 words
The method of claim 2, further including the step determining an amount of memory available to store said set of bitmap segments based on what level of compression is achieved in generating said compressed interim bitmap segments.
Claim 5
Dependent Claim
24 words
The method of claim 1, wherein the step of generating a set of interim bitmap segments includes joining together at least two bitmap segments.
Claim 6
Dependent Claim
31 words
The method of claim 1, wherein the step of generating a set of interim bitmap segments includes generating interim bitmap segments representative of a MERGE between said set of bitmap segments.
Claim 7
Dependent Claim
32 words
The method of claim 1, wherein the step of extracting from said subset of said plurality of bitmaps includes extracting one or more bitmap segments corresponding to a range of row ids.
Claim 8
Dependent Claim
32 words
The method of claim 6, wherein the step of repeating steps A) through F) includes discarding, before performing steps A) though F), interim bitmap segments that do not cover said particular range.
Claim 9
Independent Claim
146 words
A method for combining a plurality of bitmaps to generate a resulting bitmap, the method comprising the steps of: A) selecting a subset of said plurality of bitmaps; B) extracting one or more bitmap segments from said subset of said plurality of bitmaps until memory required to store said one or more bitmap segments would exceed a first amount of memory, wherein said one or more bitmap segments includes bitmap segments that cover a particular range of bit positions for each bitmap in said subset of said plurality of bitmaps; C) generating a set of compressed interim bitmap segments based on said one or more of bitmap segments; and D) until all of said plurality of bitmaps have been selected, adjusting said first amount of memory based on a level of compression achieved in generating said compressed interim bitmap segments, and repeating steps A) through D).
Claim 10
Independent Claim
146 words
A method for combining a plurality of bitmaps to generate a resulting bitmap, the method comprising the steps of: A) selecting a subset of said plurality of bitmaps; B) extracting one or more bitmap segments from said subset of said plurality of bitmaps until memory required to store said one or more bitmap segments would exceed a first amount of memory, wherein said one or more bitmap segments includes bitmap segments that cover a particular range of bit positions for each bitmap in said subset of said plurality of bitmaps; C) generating a set of compressed interim bitmap segments based on said one or more of bitmap segments; and D) until all of said plurality of bitmaps have been selected, adjusting said first amount of memory based on a level of compression achieved in generating said compressed interim bitmap segments, and repeating steps A) through D).
Claim 11
Dependent Claim
25 words
The method of claim 8, wherein the step of generating a set of compressed interim bitmap segments includes joining together at least two bitmap segments.
Claim 12
Dependent Claim
35 words
The method of claim 8, wherein the step of generating a set of compressed interim bitmap segments includes generating compressed interim bitmap segments representative of a MERGE between said set of compressed interim bitmap segments.
Claim 13
Dependent Claim
22 words
The method of claim 8, wherein the step of extracting includes extracting bitmaps segments that correspond to a range of row ids.
Claim 14
Dependent Claim
44 words
The method of claim 11, the method further including the step of if more than a threshold amount of memory is required to store all interim bitmap segments generated for said particular range, then: reducing said particular range, and repeating steps A) through D).
Claim 15
Dependent Claim
197 words
A computer-readable medium carrying one or more sequences of one or more instructions for combining a plurality of bitmaps to generate a resulting bitmap, the one or more sequences of one or more instructions including instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of: A) selecting a subset of said plurality of bitmaps; B) extracting from said subset of said plurality of bitmaps a set of bitmap segments, wherein said set of bitmap segments includes bitmap segments that cover a particular range of bit positions for each bitmap in said subset of said plurality of bitmaps; C) generating a set of interim bitmap segments based on said set of bitmap segments; D) repeating steps A) through C) until either more than a threshold amount of memory is required to store all interim bitmap segments generated for said particular range of bit positions; or all of said plurality of bitmaps have been selected; and F) if more than said threshold amount of memory is required to store all interim bitmap segments generated for said particular range, then: reducing said particular range, and repeating steps A) through F).
Claim 16
Dependent Claim
197 words
A computer-readable medium carrying one or more sequences of one or more instructions for combining a plurality of bitmaps to generate a resulting bitmap, the one or more sequences of one or more instructions including instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of: A) selecting a subset of said plurality of bitmaps; B) extracting from said subset of said plurality of bitmaps a set of bitmap segments, wherein said set of bitmap segments includes bitmap segments that cover a particular range of bit positions for each bitmap in said subset of said plurality of bitmaps; C) generating a set of interim bitmap segments based on said set of bitmap segments; D) repeating steps A) through C) until either more than a threshold amount of memory is required to store all interim bitmap segments generated for said particular range of bit positions; or all of said plurality of bitmaps have been selected; and F) if more than said threshold amount of memory is required to store all interim bitmap segments generated for said particular range, then: reducing said particular range, and repeating steps A) through F).
Claim 17
Dependent Claim
23 words
The computer-readable medium of claim 13, wherein the step of generating a set of interim bitmap segments includes generating compressed interim bitmap segments.
Claim 18
Dependent Claim
43 words
The computer-readable medium of claim 13, further including sequences of instructions for performing the step of determining an amount of memory available to store said set of bitmap segments based on what level of compression achieved in generating said compressed interim bitmap segments.
Claim 19
Dependent Claim
25 words
The computer-readable medium of claim 13, wherein the step of generating a set of interim bitmap segments includes joining together at least two bitmap segments.
Claim 20
Dependent Claim
33 words
The computer-readable medium of claim 13, wherein the step of extracting from said subset of said plurality of bitmaps includes extracting one or more bitmap segments corresponding to a range of row ids.
Claim 21
Dependent Claim
26 words
The computer-readable medium of claim 13, wherein the step of generating a set of compressed interim bitmap segments includes joining together at least two bitmap segments.
Claim 22
Dependent Claim
182 words
A computer-readable medium carrying one or more sequences of one or more instructions for combining a plurality of bitmaps to generate a resulting bitmap, the one or more sequences of one or more instructions including instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of: A) selecting a subset of said plurality of bitmaps; B) extracting one or more bitmap segments from said subset of said plurality of bitmaps until memory required to store said one or more bitmap segments would exceed a first amount of memory, wherein said one or more bitmap segments includes bitmap segments that cover a particular range of bit positions for each bitmap in said subset of said plurality of bitmaps; C) generating a set of compressed interim bitmap segments based on said one or more of bitmap segments; and D) until all of said plurality of bitmaps have been selected, adjusting said first amount of memory based on a level of compression achieved in generating said compressed interim bitmap segments, and repeating steps A) through D).
Claim 23
Dependent Claim
182 words
A computer-readable medium carrying one or more sequences of one or more instructions for combining a plurality of bitmaps to generate a resulting bitmap, the one or more sequences of one or more instructions including instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of: A) selecting a subset of said plurality of bitmaps; B) extracting one or more bitmap segments from said subset of said plurality of bitmaps until memory required to store said one or more bitmap segments would exceed a first amount of memory, wherein said one or more bitmap segments includes bitmap segments that cover a particular range of bit positions for each bitmap in said subset of said plurality of bitmaps; C) generating a set of compressed interim bitmap segments based on said one or more of bitmap segments; and D) until all of said plurality of bitmaps have been selected, adjusting said first amount of memory based on a level of compression achieved in generating said compressed interim bitmap segments, and repeating steps A) through D).
Claim 24
Dependent Claim
23 words
The computer-readable medium of claim 19, wherein the step of extracting includes extracting bitmaps segments that correspond to a range of row ids.
Claim 25
Dependent Claim
45 words
The computer-readable medium of claim 20, the method further including the step of if more than a threshold amount of memory is required to store all interim bitmap segments generated for said particular range, then: reducing said particular range, and repeating steps A) through D).
References Cited (Backward Citations)
US5495608A
Cited
US5502804A
Cited
US5404411A
Cited
US5604850A
Cited
US5425137A
Cited
US5649181A
Cited
US5751921A
Cited
US5519855A
Cited
US5642473A
Cited
US5729735A
Cited
US5715382A
Cited
US5634088A
Cited
US5710915A
Cited
US5706495A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-10-04 | 2003-04-05 | 2003-10-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-10-04 | 2007-04-05 | 2007-10-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-10-04 | 2011-04-05 | 2011-10-05 | $7700.00 | Window Closed / Lapsed |