US6141656A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Query processing using compressed bitmaps
Assignee: Oracle International Corp
•
Filing: 1997-02-28
•
Granted: 2000-10-31
•
Expires: 2017-02-28
Abstract
Abstract A method for performing logical operations on bitmap streams from segmented bitmaps. The logical operations include the AND, OR, and Set Minus operations. One embodiment of the invention performs the logical AND operation on a plurality of bitmap streams by searching for a set of overlapping bitmap segments. The ranges corresponding to the overlap among the overlapping bitmap segments are scanned to generate non-gap results. One embodiment of the invention performs the logical OR operation on a plurality of bitmap streams. To generate a result for a given range, only the bitmap segments overlapping the given range are ORed together. One embodiment of the invention performs a Set Minus between bitmap streams. A set minus is the ANDing of a first condition with the negation of another condition. To generate a set minus result, the ranges corresponding to the gaps in the bitmap associated with the negated condition are ignored.
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:30
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; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99934; Y10S707/99941; Y10S707/99942
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
142 words
A method of combining a plurality of bitmaps to generate a resulting bitmap that represents the AND operation between said plurality of bitmaps, the method comprising the steps of: A) searching said plurality of bitmaps for a first set of overlapping bitmap segments, wherein each bitmap segment from said plurality of bitmaps is associated with a range, wherein each range associated with each bitmap segment of said first set of overlapping bitmap segments overlaps with the ranges associated with all other bitmap segments in said first set of overlapping bitmap segments; B) generating a first result based on said first set, wherein said first result is representative of a bitwise AND of said plurality of bitmaps for a range shared by all bitmap segments of said first set of overlapping bitmap segments; and C) storing said first result in said resulting bitmap.
Claim 2
Independent Claim
142 words
A method of combining a plurality of bitmaps to generate a resulting bitmap that represents the AND operation between said plurality of bitmaps, the method comprising the steps of: A) searching said plurality of bitmaps for a first set of overlapping bitmap segments, wherein each bitmap segment from said plurality of bitmaps is associated with a range, wherein each range associated with each bitmap segment of said first set of overlapping bitmap segments overlaps with the ranges associated with all other bitmap segments in said first set of overlapping bitmap segments; B) generating a first result based on said first set, wherein said first result is representative of a bitwise AND of said plurality of bitmaps for a range shared by all bitmap segments of said first set of overlapping bitmap segments; and C) storing said first result in said resulting bitmap.
Claim 3
Dependent Claim
135 words
The method of claim 1, further including the steps of: D) searching a plurality of bitmaps for a next set of overlapping bitmap segments, wherein each range associated with each bitmap segment of said next set of overlapping bitmap segments overlaps with the ranges associated with all other bitmap segments in said next set of overlapping bitmap segments; E) generating a next result based on said next set of overlapping bitmap segments, wherein said next result is representative of a bitwise AND of said plurality of bitmaps for a range shared by all bitmap segments of said next set of overlapping bitmap segments; F) storing said next result in said resulting bitmap; and G) repeating the steps (D) through (F) until said plurality of bitmaps do not contain another next set of overlapping bitmap segments.
Claim 4
Dependent Claim
20 words
The method of claim 1, wherein the step of searching said plurality of bitmaps includes searching at least three bitmaps.
Claim 5
Dependent Claim
134 words
The method of claim 1, further including the steps of: establishing a tentative point of alignment for said first set of overlapping bitmap segments, said tentative point of alignment corresponding to the beginning of a range associated with a map from a particular bitmap segment from said set of overlapping bitmap segments; determining whether each remaining bitmap segment from said first set of overlapping bitmap segments includes a map associated with a range that overlaps said tentative point of alignment; and if each remaining bitmap segment from said first set of overlapping bitmap segments includes a map associated with a range that overlaps said tentative point of alignment, then generating a result representative of a bitwise AND between said plurality of bitmaps for a range having a beginning at said tentative point of alignment.
Claim 6
Dependent Claim
44 words
The method of claim 4, wherein the step determining whether each remaining bitmap segment from said set of overlapping bitmap segments includes a map further includes inspecting each remaining bitmap segment in an order that corresponds to the sparseness of said remaining bitmap segment.
Claim 7
Dependent Claim
94 words
The method of claim 4, wherein the step of generating a result representative of a bitwise AND between said plurality of bitmaps for a range having a beginning at said tentative point of alignment further includes: finding a minimum map beginning at said tentative point of alignment, wherein each of said set of overlapping bitmap segments contains a map completely overlapping the range associated with said minimum map; and generating a result representative of a bitwise AND between said plurality of bitmaps for a range having a beginning at said tentative point of alignment.
Claim 8
Dependent Claim
25 words
The method of claim 4, further including establishing the end of the range associated with said minimum map as a next tentative point of alignment.
Claim 9
Independent Claim
124 words
A method of combining a plurality of bitmaps to generate a resulting bitmap representing the OR operation between said plurality of bitmaps, the method comprising the steps of: establishing an aligned set of bitmap segments from said plurality of said bitmaps, wherein said aligned set is associated with an alignment position, wherein said alignment position is associated with a range, wherein each member of said aligned set contains a map overlapping said alignment position; performing a bitwise OR operation of maps from said members of said aligned set that overlap said alignment position to generate a first result; and establishing said first result as the result representing the bitwise OR operation between said plurality of bitmaps for the range corresponding to said aligned position.
Claim 10
Independent Claim
124 words
A method of combining a plurality of bitmaps to generate a resulting bitmap representing the OR operation between said plurality of bitmaps, the method comprising the steps of: establishing an aligned set of bitmap segments from said plurality of said bitmaps, wherein said aligned set is associated with an alignment position, wherein said alignment position is associated with a range, wherein each member of said aligned set contains a map overlapping said alignment position; performing a bitwise OR operation of maps from said members of said aligned set that overlap said alignment position to generate a first result; and establishing said first result as the result representing the bitwise OR operation between said plurality of bitmaps for the range corresponding to said aligned position.
Claim 11
Dependent Claim
29 words
The method of claim 8, wherein the step of establishing an aligned set includes establishing an aligned set of bitmap segments from a set of at least three bitmaps.
Claim 12
Dependent Claim
54 words
The method of claim 8, further including the step of: incrementing said aligned position; and after incrementing said aligned position: adding to said aligned set nonmember bitmap segments with maps overlapping said aligned position, and removing from said aligned set members of said aligned set that do not contain maps overlapping said aligned position.
Claim 13
Dependent Claim
66 words
The method of claim 10, wherein: said aligned set is associated with an upper bound, said upper bound being the beginning of the next lowest range following said alignment position that is associated with any map from said plurality of bitmaps; and the step of adding to said aligned set further includes adding to said aligned set when said aligned position corresponds to said upper bound.
Claim 14
Dependent Claim
66 words
The method of claim 11, wherein: said aligned set is associated with an upper bound, said upper bound being the beginning of the next lowest range following said alignment position that is associated with any map from said plurality of bitmaps; and the method further includes the of step of if said aligned set contains no members, then incrementing said aligned position to said upper bound.
Claim 15
Independent Claim
116 words
A method of combining a plurality of bitmaps to generate a resulting bitmap representing a SET MINUS operation between said plurality of bitmaps, the method comprising the steps of: establishing one bitmap of said plurality of bitmaps as a minuend bitmap; establishing another bitmap from said plurality of bitmaps as a subtrahend bitmap; finding one or more portions of said minuend bitmap that independently represent a SET MINUS operation between said minuend bitmap and said subtrahend bitmap for one or more ranges corresponding to said one or more portions; and establishing said one or more portions as representative of said SET MINUS operation for the one or more ranges corresponding to said one or more portions.
Claim 16
Independent Claim
116 words
A method of combining a plurality of bitmaps to generate a resulting bitmap representing a SET MINUS operation between said plurality of bitmaps, the method comprising the steps of: establishing one bitmap of said plurality of bitmaps as a minuend bitmap; establishing another bitmap from said plurality of bitmaps as a subtrahend bitmap; finding one or more portions of said minuend bitmap that independently represent a SET MINUS operation between said minuend bitmap and said subtrahend bitmap for one or more ranges corresponding to said one or more portions; and establishing said one or more portions as representative of said SET MINUS operation for the one or more ranges corresponding to said one or more portions.
Claim 17
Dependent Claim
26 words
The method of claim 13, wherein the step of finding includes finding a portion of said minuend bitmap corresponding to a gap in said subtrahend bitmap.
Claim 18
Dependent Claim
26 words
The method of claim 13, wherein the step of finding includes finding a portion in said minuend bitmap corresponding to a gap in said minuend bitmap.
Claim 19
Dependent Claim
54 words
The method of claim 13, further including the step establishing as representative of a SET MINUS operation for a particular range a result of a bitwise AND operation between a portion of said minuend corresponding to said particular range and a one's compliment of a portion of said subtrahend corresponding to said particular range.
Claim 20
Dependent Claim
172 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 that represents the AND operation between said plurality of bitmaps, wherein the execution of the one or more sequences of the one or more instructions causes the one or more processors to perform the steps of: A) searching said plurality of bitmaps for a first set of overlapping bitmapsegments, wherein each bitmap segment from said plurality of bitmaps is associated with a range, wherein each range associated with each bitmap segment of said first set of overlapping bitmap segments overlaps with the ranges associated with all other bitmap segments in said first set of overlapping bitmap segments; B) generating a first result based on said first set, wherein said first result is representative of a bitwise AND of said plurality of bitmaps for a range shared by all bitmap segments of said first set of overlapping bitmap segments; and C) storing said first result in said resulting bitmap.
Claim 21
Dependent Claim
172 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 that represents the AND operation between said plurality of bitmaps, wherein the execution of the one or more sequences of the one or more instructions causes the one or more processors to perform the steps of: A) searching said plurality of bitmaps for a first set of overlapping bitmapsegments, wherein each bitmap segment from said plurality of bitmaps is associated with a range, wherein each range associated with each bitmap segment of said first set of overlapping bitmap segments overlaps with the ranges associated with all other bitmap segments in said first set of overlapping bitmap segments; B) generating a first result based on said first set, wherein said first result is representative of a bitwise AND of said plurality of bitmaps for a range shared by all bitmap segments of said first set of overlapping bitmap segments; and C) storing said first result in said resulting bitmap.
Claim 22
Dependent Claim
20 words
The method of claim 17, wherein the step of searching said plurality of bitmaps includes searching at least three bitmaps.
Claim 23
Dependent Claim
155 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 representing the OR operation between said plurality of bitmaps, wherein the execution of the one or more sequences of the one or more instructions causes the one or more processors to perform the steps of: establishing an aligned set of bitmap segments from said plurality of said bitmaps, wherein said aligned set is associated with an alignment position, wherein said alignment position is associated with a range, wherein each member of said aligned set contains a map overlapping said alignment position; performing a bitwise OR operation of maps from said members of said aligned set that overlap said alignment position to generate a first result; and establishing said first result as the result representing the bitwise OR operation between said plurality of bitmaps for the range corresponding to said aligned position.
Claim 24
Dependent Claim
155 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 representing the OR operation between said plurality of bitmaps, wherein the execution of the one or more sequences of the one or more instructions causes the one or more processors to perform the steps of: establishing an aligned set of bitmap segments from said plurality of said bitmaps, wherein said aligned set is associated with an alignment position, wherein said alignment position is associated with a range, wherein each member of said aligned set contains a map overlapping said alignment position; performing a bitwise OR operation of maps from said members of said aligned set that overlap said alignment position to generate a first result; and establishing said first result as the result representing the bitwise OR operation between said plurality of bitmaps for the range corresponding to said aligned position.
Claim 25
Dependent Claim
30 words
The computer-readable media of claim 19, wherein the step of establishing an aligned set includes establishing an aligned set of bitmap segments from a set of at least three bitmaps.
Claim 26
Dependent Claim
60 words
The computer-readable media of claim 19, further including sequences of instructions for performing the steps of: incrementing said aligned position; and after incrementing said aligned position: adding to said aligned set nonmember bitmap segments with maps overlapping said aligned position, and removing from said aligned set members of said aligned set that do not contain maps overlapping said aligned position.
Claim 27
Dependent Claim
67 words
The computer-readable media of claim 21, wherein: said aligned set is associated with an upper bound, said upper bound being the beginning of the next lowest range following said alignment position that is associated with any map from said plurality of bitmaps; and the step of adding to said aligned set further includes adding to said aligned set when said aligned position corresponds to said upper bound.
Claim 28
Dependent Claim
72 words
The computer-readable media of claim 22, wherein: said aligned set is associated with an upper bound, said upper bound being the beginning of the next lowest range following said alignment position that is associated with any map from said plurality of bitmaps; and the computer-readable media further includes sequences of instructions for performing the step of if said aligned set contains no members, then incrementing said aligned position to said upper bound.
Claim 29
Dependent Claim
141 words
The computer-readable medium of claim 19, further including sequences of instructions for performing the steps of: D) searching a plurality of bitmaps for a next set of overlapping bitmap segments, wherein each range associated with each bitmap segment of said next set of overlapping bitmap segments overlaps with the ranges associated with all other bitmap segments in said next set of overlapping bitmap segments; E) generating a next result based on said next set of overlapping bitmap segments, wherein said next result is representative of a bitwise AND of said plurality of bitmaps for a range shared by all bitmap segments of said next set of overlapping bitmap segments; F) storing said next result in said resulting bitmap; and G) repeating the steps (D) through (F) until said plurality of bitmaps do not contain another next set of overlapping bitmap segments.
Claim 30
Dependent Claim
140 words
The computer-readable medium of claim 19, further including sequences of instructions for performing the steps of: establishing a tentative point of alignment for said first set of overlapping bitmap segments, said tentative point of alignment corresponding to the beginning of a range associated with a map from a particular bitmap segment from said set of overlapping bitmap segments; determining whether each remaining bitmap segment from said first set of overlapping bitmap segments includes a map associated with a range that overlaps said tentative point of alignment; and if each remaining bitmap segment from said first set of overlapping bitmap segments includes a map associated with a range that overlaps said tentative point of alignment, then generating a result representative of a bitwise AND between said plurality of bitmaps for a range having a beginning at said tentative point of alignment.
Claim 31
Dependent Claim
46 words
The computer-readable medium of claim 25, wherein the step of determining whether each remaining bitmap segment from said set of overlapping bitmap segments includes a map further includes inspecting each remaining bitmap segment in an order that corresponds to the sparseness of said remaining bitmap segment.
Claim 32
Dependent Claim
95 words
The computer-readable medium of claim 25, wherein the step of generating a result representative of a bitwise AND between said plurality of bitmaps for a range having a beginning at said tentative point of alignment further includes: finding a minimum map beginning at said tentative point of alignment, wherein each of said set of overlapping bitmap segments contains a map completely overlapping the range associated with said minimum map; and generating a result representative of a bitwise AND between said plurality of bitmaps for a range having a beginning at said tentative point of alignment.
Claim 33
Dependent Claim
34 words
The computer-readable medium of claim 25, further including sequences of instructions for performing the step of establishing the end of the range associated with said minimum map as a next tentative point of alignment.
References Cited (Backward Citations)
US4606002A
Cited
US4817036A
Cited
US5495608A
Cited
US5430869A
Cited
US5475837A
Cited
US5649181A
Cited
US5560007A
Cited
US5504889A
Cited
US5664172A
Cited
EP0772139A2
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-10-31 | 2004-05-01 | 2004-10-31 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-10-31 | 2008-05-01 | 2008-10-31 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-10-31 | 2012-05-01 | 2012-10-31 | $7700.00 | Window Closed / Lapsed |