System, method and data structure for fast loading, storing and access to huge data sets in real time

• US 9,251,197 B2
• Filed: 06/27/2012
• Issued: 02/02/2016
• Est. Priority Date: 06/27/2011
• Status: Active Grant

• Current Assignee: Jethrodata Ltd.
• Original Assignee: Jethrodata Ltd.
• Inventors: Raufman, Boaz
• Primary Examiner(s): AL HASHEMI, SANA A
• Application Number:
  US14/129,702
• Publication Number:
  US 20140129530A1
• Time in Patent Office: 1,315 Days
• Field of Search: 707/609, 707/687, 707/790, 707/821, 707/953
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/901 Indexing; Data structures therefor; Storage structures for retrieval from the web G06F16/951
• CPC Class Codes: G06F 7/78 for changing the order of data flow, e.g. matrix transposition or LIFO buffers; Overflow or underflow handling therefor

Abstract

A computerized system including a processor and a computer-readable non-transient memory in communication with the processor, the memory storing instructions that when executed manage a novel data structure and related group of algorithms that can be used as a method for representing a set and as a base for very efficient indexing, hash and compression. SHB is an improvement of hierarchical bitmap. An improved database system that can utilize the innovative data structure which includes a raw data stream provided to the system via a data processing module, data blocks, fields indexes tables and a keys table. There is provided an index creating process and a columns creating process, for transforming the data blocks and tables into index blocks and data columns.

Claims

1. A computerized system comprising:

a processor; and

a computer-readable non-transient memory in communication with the processor, the memory storing instructions that when executed manage a Super Hierarchiel Bitmaps (SHB) data structure representing a set of integers that includes;

(a) at least one word, wherein each said word contains a predefined number of, bits, wherein each said bit is selected from the group including 1-bits and 0-bits;

(b) a plurality of bit vectors, each said bit vector containing at least one word, wherein said at least one word is selected from the group including an empty word containing only said 0-bits and a non-empty word containing at least one said 1-bit;

(c) one or more compressed layers representing corresponding one or more non-compressed layers, wherein;

(i) each said non-compressed layer includes one said bit vector, wherein said one or more non-compressed layers are organized sequentially, such that each of said one or more non-compressed layers except for a last non-compressed layer has a subsequent non-compressed layer related thereto;

(ii) the set of integers containing a plurality of positive integer members, wherein each member is represented by a 1-bit in the last non-compressed layer and wherein the position of each said 1-bit in said last non-compressed layer is equal to a value of said positive integer member;

(iii) each said non-empty word is represented by a respective 1-bit in a previous non-compressed layer such that a number of said 1-bits in said previous non-compressed layer is equivalent to a number of said non-empty words in a subsequent non-compressed layer and a position of each of said 1-bit in said previous non-compressed layer represents a corresponding position of each said non-empty word in said subsequent non-compressed layer;

wherein said compressed layers other than a first compressed layer include only said non-empty words, and each position of said empty words in said non-compressed layer is represented by a position of each said 0-bit in said previous non-compressed layer, said empty words in any non-compressed layer being representative of removed empty words in any corresponding compressed layer, and each position of said removed empty words in a second compressed layer is represented by a position of each said 0-bit in said first compressed layer, so that said second compressed layer is decompressed into a second decompressed layer by calculating said positions of said removed empty words in said second compressed layer according to said positions of said 0-bits in said first compressed layer, and each said compressed layer other than said first and second compressed layers is decompressed sequentially by calculating said positions of said removed empty words in each said compressed layer according to said positions of said 0-bits in a previous decompressed layer; and

(d) one or more counter vectors, each of said counter vectors related to each of said one or more compressed layers, wherein for each said word in each of said compressed layers there exists a related counter member and wherein each said counter member holds a counter value which equals a cumulative number of 1-bits, said cumulative number calculated from a first position in each of said bit vectors to each respective said word in said bit vector related to said counter member.

7. The computerized system of claim 1, wherein the processor is configured to create the SHB data structure representing a set of integer members using a SHB Create function.

8. The computerized system of claim 1, wherein the processor is configured to search an integer member U represented by a bit representation in a last compressed layer in said SHB data structure using a SHB Search function.

9. The computerized system of claim 1, wherein at least one of the counter vectors is optimized by using multiple counter vector layers, wherein each of said multiple counter vector layers except for a counter vector layer 1 uses a next counter vector layer of said multiple counter vector layers as a base to calculate the counter values held by the counter members thereof.

11. The computerized system of claim 7, wherein the Create function comprises:

associating said set of integer members with corresponding bit representations in said compressed layers of said SHB data structure, including;

a) obtaining said set of integer members ordered in an ascending order from the lowest value to the highest value;

b) for each integer member in said set, starting from the lowest value, calculating a position of a bit representation in each of said compressed layers, and

c) calculate said counter vector related to each of said compressed layers.

12. The computerized system of claim 8, wherein the SHB search function includes:

calculating in said SHB data structure sequentially in each of said compressed layers, starting from said first compressed layer, an expected position of a bit representation for said U until a condition is met, said condition being that a bit representation in said calculation having a value 0 which indicates that said U is not represented by said SHB data structure;

otherwise said condition is not met and the bit representation in said last compressed layer having a value 1 indicates that said U is represented by said SHB data structure.

13. The computerized system of claim 8, wherein said SHB search function comprises:

1) for the first compressed layer of said SHB data structure, calculating W₀=(U−

1) / K^L,

wherein W₀ indicates an expected actual position of a word that contains the bit representation in the first compressed layer;

K indicates the number of bits included in each said word;

L indicates the number of compressed layers in said SHB data structure;

2) for each compressed layer l of said SHB data structure, starting from said first compressed layer,

i) calculating R_l+1=(U−

1)/K^(L−

(l+1)),

wherein R_l+1 indicates an expected virtual position of a word that contains the bit representation in the corresponding non-compressed layer l+1;

ii) calculating B_l=R_l+1 % K,

wherein B₁ indicates an expected bit position of the bit representation within a word in said compressed layer l;

iii) calculating V_l[W_l] &

2^B_l,

wherein V_l , indicates the bit vector included in the compressed layer l,

W_l indicates the expected actual position of the word that contains the bit representation in the compressed layer l,

V_l[W_l] indicates the word at the expected actual position W_l, in the bit vector V_l, and

&

indicates logical AND operation;

iv) if the value of V_l[W_l] &

2^B_l is 0, determining that U is not an integer member in said data structure;

otherwise if the value of V_l[W_l] &

2^B_l is 1, calculating W_l+1=C_l[W_l]+countLeftBits(V_l[W_l], B_l),

wherein W_l+1 indicates the expected actual position of the word that contains the bit representation in the compressed layer l+1,

C_l[W_l] indicates the counter value held by the counter member related to a previous word of said word at W_l, and

countLeftBits(V_l[W_l], B_l) indicates the number of bits that are set to 1 to the left of the expected bit position B_l within the word V_l[W_l] in said compressed layer l;

v) if said compressed layer l is a last compressed layer of said SHB data structure, determining that U is an integer member in said data structure;

otherwise if said compressed layer l is not the last compressed layer of said SHB data structure, repeating steps i)-v), until U is determined not being an integer member in said data structure, or until said compressed layer l is the last compressed layer of said SHB data structure.

14. The computerized system of claim 9, wherein the bit vector of any given layer of said compressed layers is divided into a plurality of groups each including a predefined number (W) of words, and each counter member of the counter vector in said counter vector layer 1 equals the cumulative number of 1-bits, said cumulative number calculated from a first position in each of said groups to each respective said word within each respective said group in said bit vector related to each said counter member;

said multiple counter vector layers include a counter vector layer 2 in case the W^th word is reached in said counter vector layer 1, and each counter member of the counter vector in said counter vector layer 2 counts the total number of 1-bits for each respective group of W words, wherein memory size of each counter member of the counter vector in the counter vector layer 2 is twice of the memory size of each counter member of the counter vector in the counter vector layer 1;

and wherein said multiple counter vector layers include a counter vector layer X in case the W^(X−

1)^th word is reached in counter vector layer X−

1, and each counter member of the counter vector in the counter vector layer X equals the total number of 1-bits for each respective group of W^(X−

1)words.

16. The computerized system of claim 11, wherein said calculating of said step b) comprises:

1) for the first compressed layer of said SHB data structure, calculating W₀=(U−

1)/K^L,

wherein W₀ indicates an actual position of a word that contains the bit representation in the first compressed layer;

U indicates each said integer member in said set;

K indicates the number of bits included in each said word;

L indicates the number of compressed layers in said SHB data structure;

2) for each compressed layer l of said SHB data structure, starting from said first compressed layer,

i) calculating R_l+1=(U−

1)/K^(L−

(l+1)),

wherein R_l+1 indicates a virtual position of a word that contains the bit representation in the corresponding non-compressed layer l+1;

ii) calculating B_l=R_l+1 % K,

wherein B_l indicates a bit position of the bit representation within a word in said compressed layer l;

iii) calculating V_l[W_l]=V_l[W_l]| 2^B_l,

wherein V_l , indicates the bit vector included in the compressed layer l,

W_lindicates the actual position of the word that contains the bit representation in the compressed layer l,

V_l[W_l] indicates the word at the actual position W_l, in the bit vector V_l, and

| indicates logical OR operation;

iv) if the number of bits in V_l[W_l] increases, calculating T_l=T_l+1,

wherein T_l , indicates a counter representing the total number of bits that are set to 1 in said compressed layer l;

v) calculating W_l+1=T_l−

1,

wherein W_l , indicates the actual position of the word that contains the bit representation in the compressed layer l+1.

17. The computerized system of claim 11, wherein said calculating of said step c) comprises:

for each said compressed layer l, calculating C_l[n+1]=C_l[n]+countBits(V_l[n]),

wherein C_l indicates the counter vector related to said compressed layer l,

n indicates a word position counter in the bit vector of each said compressed layer l,

C_l[n] indicates the counter value held by the counter member related to a previous word of said word at n, and

countBits(V_l[n]) indicates the number of bits that are set to 1 in said word at n.

18. The computerized system of claim 11, wherein the processor is further configured to create an SHB index using said SHB data structure, including:

a) provide index pairs each including a set member constituting an integer member, and a mapped value related to said set member;

b) arrange said index pairs to an ordered set of index pairs according to an ascending order of integer members of said index pairs, wherein said integer members of said ordered set of index pairs being representatives of said set of integer members ordered in said ascending order;

c) creating said SHB data structure from said set of integer members;

d) allocate a value vector V associated with said created SHB data structure, wherein each member of said value vector V[n] holds a mapped value related to a respective integer member of a nth index pair of said ordered set of index pairs.

19. The computerized system of claim 11, wherein the processor is further configured to convert an array of non-compressed numeric values to an array of corresponding compressed values using said SHB data structure, comprising:

1) create said SHB data structure from said array of non-compressed numeric values, wherein said array of non-compressed numeric values being representatives of said set of integer members;

2) determine a number of bits representing each said non-compressed numeric value using said SHB data structure, and

3) generate the array of compressed values representing corresponding non-compressed numeric values, each compressed value in said array of compressed values being represented by said number of bits.

20. The computerized system of claim 13, wherein said step v) further comprises:

getting a serial number S of said integer member U represented by said bit representation in said last compressed layer in said SHB data structure, wherein said S equals C_l[W_l]+countLeftBits(V_l[W_l], B_l)+1 if said compressed layer l is the last compressed layer of said SHB data structure and U is determined to be an integer member in said data structure.

21. The computerized system of claim 18, wherein the processor is further configured to search for a given mapped value of an integer member in said SHB index by getting a serial number s of said integer member in said SHB data structure, and retrieving the given mapped value of said integer member in the value vector V according to the serial number s.

22. The computerized system of claim 19, wherein said number of bits equals Log2(size(SHB)), wherein said size(SHB) indicates the number of non-compressed numeric values represented in said SHB data structure;

and

wherein said generating in said step

     3) comprises;

get a serial number of each said non-compressed numeric value in said SHB data structure,

translate said serial number to a corresponding compressed value of said non-compressed numeric value, said compressed value being represented by said number of bits, and

place said compressed value into said array of compressed values according to a position of the corresponding non-compressed numeric value in said array of non-compressed numeric values.

23. The computerized system of claim 21, wherein the processor is configured to create hash for a plurality of keys in a key set, using said SHB index, comprising:

a) hash said keys with a hash function ƒ

to respective hashed values;

b) collect said keys in a key vector K and said respective hashed values thereof in a hashed value vector H, so that a position m of a key k in said key vector is equal to a corresponding position m of a respective hashed value of said key k in said hashed value vector, such that H[M]=ƒ

(K[m]);

c) create said SHB data structure based on said hashed values in said hashed value vector H, wherein the hashed values being representatives of said set of integer members;

d) create a position vector V, wherein V[s] equals the position m of said key k in said key vector K, such that K[V[s]]=k, wherein s indicates a serial number of a respective hashed value H[m] in said SHB data structure;

whereby the hashed values in said SHB data structure being representatives of said integer members, and V[s] being representatives of said mapped values related to said respective integer members.

24. The computerized system of claim 22, wherein the processor is further configured to convert said array of compressed values to said array of numeric values, comprising:

prepare a reverse index for each compressed value; and

obtain the corresponding non-compressed numeric value for each said compressed value according to said reverse index.

25. The computerized system of claim 23, wherein the processor is further configured to determine if a key k1 is in said key set, comprising:

a) hash said key k1 with said hash function ƒ

to a hashed value ƒ

(k1);

b) search for said hashed value ƒ

(k1) of said key k1 in said SHB data structure;

c) if the hashed value ƒ

(k1) is not found in said SHB data structure, k1 is determined not to be in said key set;

or

if the hashed value ƒ

(k1) is found in said SHB data structure, compare said key k1 to a key k2 at a position in said key vector K indicated by the position vector V;

if k1 equals k2, k1 is determined to be in said key set, or if k1 does not equal k2, rehash k1 until said key k2 that equals k1 is found, or until the hashed value is not found in said SHB data structure.

2. A computerized method of searching for an integer member U, comprising:

A. providing a Super Hierarchiel Bitmaps (SHB) data structure representing a set of integer members, the SHB data structure being stored on a computer-readable non-transient memory in communication with a processor, the SHB data structure including;

(a) at least one word, wherein each said word contains a predefined number of bits, wherein each said bit is selected from the group including 1-bits and 0-bits;

(b) a plurality of bit vectors, each said bit vector containing at least one word, wherein said at least one word is selected from the group including an empty word containing only said 0-bits and a non-empty word containing at least one said 1-bit;

(c) one or more compressed layers representing corresponding one or more non-compressed layers, wherein;

(i) each said non-compressed layer includes one said bit vector, wherein said one or more non-compressed layers are organized sequentially, such that each of said one or more non-compressed layers except for a last non-compressed layer has a subsequent non-compressed layer related thereto;

(ii) the set of integers containing a plurality of positive integer members, wherein each member is represented by a 1-bit in the last non-compressed layer and wherein the position of each said 1-bit in said last non-compressed layer is equal to a value of said positive integer member;

(iii) each said non-empty word is represented by a respective 1-bit in a previous non-compressed layer such that a number of said 1-bits in said previous non-compressed layer is equivalent to a number of said non-empty words in a subsequent non-compressed layer and a position of each of said 1-bit in said previous non-compressed layer represents a corresponding position of each said non-empty word in said subsequent non-compressed layer;

wherein said compressed layers other than a first compressed layer include only said non-empty words, and each position of said empty words in said non compressed layer is represented by a position of each said 0-bit in said previous non-compressed layer, said empty words in any non-compressed layer being representative of removed empty words in any corresponding compressed layer, and each position of said removed empty words in a second compressed layer is represented by a position of each said 0-bit in said first compressed layer, so that said second compressed layer is decompressed into a second decompressed layer by calculating said positions of said removed empty words in said second compressed layer according to said positions of said 0-bits in said first compressed layer, and each said compressed layer other than said first and second compressed layers is decompressed sequentially by calculating said positions of said removed empty words in each said compressed layer according to said positions of said 0-bits in a previous decompressed layer; and

(d) one or more counter vectors, each of said counter vectors related to each of said one or more compressed layers, wherein for each said word in each of said compressed layers there exists a related counter member and wherein each said counter member holds a counter value which equals a cumulative number of 1-bits, said cumulative number calculated from a first position in each of said bit vectors to each respective said word in said bit vector related to said counter member;

B. searching for said integer member U represented by a bit representation in a last compressed layer in said SHB data structure using a SHB Search function.

10. The computerized method of claim 2, wherein said SHB search function includes:

calculating in said SHB data structure sequentially in each of said compressed layers, starting from said first compressed layer, an expected position of a bit representation for said U until a condition is met, said condition being that a bit representation in said calculation having a value 0 which indicates that said U is not represented by said SHB data structure;

otherwise said condition is not met and the bit representation in said last compressed layer having a value 1 indicates that said U is represented by said SHB data structure.

15. The computerized method of claim 10 further comprises:

getting a serial number S of said integer member U represented by said bit representation in said last compressed layer in said SHB data structure.

3. A computerized method of creating a Super Hierarchiel Bitmaps (SHB) data structure representing a set of integer members using a SHB Create function, the SHB data structure being stored on a computer-readable non-transient memory in communication with a processor, comprising:

A. obtaining said set of integer members ordered in an ascending order from the lowest value to the highest value;

B. creating said SHB data structure that represents said set of integer members, said SHB data structure includes;

(a) at least one word, wherein each said word contains a predefined number of bits, wherein each said bit is selected from the group including 1-bits and 0-bits;

(b) a plurality of bit vectors, each said bit vector containing at least one word, wherein said at least one word is selected from the group including an empty word containing only said 0-bits and a non-empty word containing at least one said 1-bit;

(c) one or more compressed layers representing corresponding one or more non-compressed layers, wherein;

(i) each said non-compressed layer includes one said bit vector, wherein said one or more non-compressed layers are organized sequentially, such that each of said one or more non-compressed layers except for a last non-compressed layer has a subsequent non-compressed layer related thereto;

(ii) the set of integers containing a plurality of positive integer members, wherein each member is represented by a 1-bit in the last non-compressed layer and wherein the position of each said 1-bit in said last non-compressed layer is equal to a value of said positive integer member;

(iii) each said non-empty word is represented by a respective 1-bit in a previous non-compressed layer such that a number of said 1-bits in said previous non-compressed layer is equivalent to a number of said non-empty words in a subsequent non-compressed layer and a position of each of said 1-bit in said previous non-compressed layer represents a corresponding position of each said non-empty word in said subsequent non-compressed layer;

wherein said compressed layers other than a first compressed layer include only said non-empty words, and each position of said empty words in said non compressed layer is represented by a position of each said 0-bit in said previous non-compressed layer, said empty words in any non-compressed layer being representative of removed empty words in any corresponding compressed layer, and each position of said removed empty words in a second compressed layer is represented by a position of each said 0-bit in said first compressed layer, so that said second compressed layer is decompressed into a second decompressed layer by calculating said positions of said removed empty words in said second compressed layer according to said positions of said 0-bits in said first compressed layer, and each said compressed layer other than said first and second compressed layers is decompressed sequentially by calculating said positions of said removed empty words in each said compressed layer according to said positions of said 0-bits in a previous decompressed layer; and

(d) one or more counter vectors, each of said counter vectors related to each of said one or more compressed layers, wherein for each said word in each of said compressed layers there exists a related counter member and wherein each said counter member holds a counter value which equals a cumulative number of 1-bits, said cumulative number calculated from a first position in each of said bit vectors to each respective said word in said bit vector related to said counter member.

4. A computerized method of creating a Super Hierarchiel Bitmaps (SHB) index using an SHB data structure, the SHB data structure representing a set of integer members, said SHB data structure being stored on a computer-readable non-transient memory in communication with a processor, comprising:

A. providing index pairs each including a set member constituting an integer member, and a mapped value related to said set member;

B. arranging said index pairs to an ordered set of index pairs according to an ascending order of integer members of said index pairs, wherein said integer members of said ordered set of index pairs being representatives of said set of integer members ordered in said ascending order;

C. creating said SHB data structure that represents said set of integer members, said SHB data structure includes;

(a) at least one word, wherein each said word contains a predefined number of bits, wherein each said bit is selected from the group including 1-bits and 0-bits;

(b) a plurality of bit vectors, each said bit vector containing at least one word, wherein said at least one word is selected from the group including an empty word containing only said 0-bits and a non-empty word containing at least one said 1-bit;

(c) one or more compressed layers representing corresponding one or more non-compressed layers, wherein;

(i) each said non-compressed layer includes one said bit vector, wherein said one or more non-compressed layers are organized sequentially, such that each of said one or more non-compressed layers except for a last non-compressed layer has a subsequent non-compressed layer related thereto;

(ii) the set of integers containing a plurality of positive integer members, wherein each member is represented by a 1-bit in the last non-compressed layer and wherein the position of each said 1-bit in said last non-compressed layer is equal to a value of said positive integer member;

(iii) each said non-empty word is represented by a respective 1-bit in a previous non-compressed layer such that a number of said 1-bits in said previous non-compressed layer is equivalent to a number of said non-empty words in a subsequent non-compressed layer and a position of each of said 1-bit in said previous non-compressed layer represents a corresponding position of each said non-empty word in said subsequent non-compressed layer;

wherein said compressed layers other than a first compressed layer include only said non-empty words, and each position of said empty words in said non compressed layer is represented by a position of each said 0-bit in said previous non-compressed layer, said empty words in any non-compressed layer being representative of removed empty words in any corresponding compressed layer, and each position of said removed empty words in a second compressed layer is represented by a position of each said 0-bit in said first compressed layer, so that said second compressed layer is decompressed into a second decompressed layer by calculating said positions of said removed empty words in said second compressed layer according to said positions of said 0-bits in said first compressed layer, and each said compressed layer other than said first and second compressed layers is decompressed sequentially by calculating said positions of said removed empty words in each said compressed layer according to said positions of said 0-bits in a previous decompressed layer; and

(d) one or more counter vectors, each of said counter vectors related to each of said one or more compressed layers, wherein for each said word in each of said compressed layers there exists a related counter member and wherein each said counter member holds a counter value which equals a cumulative number of 1-bits, said cumulative number calculated from a first position in each of said bit vectors to each respective said word in said bit vector related to said counter member;

D. allocating a value vector V associated with said created SHB data structure, wherein each member of said value vector V[n] holds a mapped value related to a respective integer member of a nth index pair of said ordered set of index pairs.

5. A computerized method of creating hash for a plurality of keys in a key set using a Super Hierarchiel Bitmaps (SHB) index based on a SHB data structure, the SHB data structure representing a set of integer members, said SHB data structure being stored on a computer-readable non-transient memory in communication with a processor, comprising:

A. hash said keys with a hash function ƒ

to respective hashed values;

B. collect said keys in a key vector K and said respective hashed values thereof in a hashed value vector H, so that a position m of a key k in said key vector is equal to a corresponding position m of a respective hashed value of said key k in said hashed value vector, such that H[m]=ƒ

(K[m]);

C. create said SHB data structure representing said hashed values in said hashed value vector H, wherein the hashed values being representatives of said set of integer members, said SHB data structure includes;

(a) at least one word, wherein each said word contains a predefined number of bits, wherein each said bit is selected from the group including 1-bits and 0-bits;

(b) a plurality of bit vectors, each said bit vector containing at least one word, wherein said at least one word is selected from the group including an empty word containing only said 0-bits and a non-empty word containing at least one said 1-bit;

(c) one or more compressed layers representing corresponding one or more non-compressed layers, wherein;

(i) each said non-compressed layer includes one said bit vector, wherein said one or more non-compressed layers are organized sequentially, such that each of said one or more non-compressed layers except for a last non-compressed layer has a subsequent non-compressed layer related thereto;

(ii) the set of integers containing a plurality of positive integer members, wherein each member is represented by a 1-bit in the last non-compressed layer and wherein the position of each said 1-bit in said last non-compressed layer is equal to a value of said positive integer member;

(iii) each said non-empty word is represented by a respective 1-bit in a previous non-compressed layer such that a number of said 1-bits in said previous non-compressed layer is equivalent to a number of said non-empty words in a subsequent non-compressed layer and a position of each of said 1-bit in said previous non-compressed layer represents a corresponding position of each said non-empty word in said subsequent non-compressed layer;

wherein said compressed layers other than a first compressed layer include only said non-empty words, and each position of said empty words in said non compressed layer is represented by a position of each said 0-bit in said previous non-compressed layer, said empty words in any non-compressed layer being representative of removed empty words in any corresponding compressed layer, and each position of said removed empty words in a second compressed layer is represented by a position of each said 0-bit in said first compressed layer, so that said second compressed layer is decompressed into a second decompressed layer by calculating said positions of said removed empty words in said second compressed layer according to said positions of said 0-bits in said first compressed layer, and each said compressed layer other than said first and second compressed layers is decompressed sequentially by calculating said positions of said removed empty words in each said compressed layer according to said positions of said 0-bits in a previous decompressed layer; and

(d) one or more counter vectors, each of said counter vectors related to each of said one or more compressed layers, wherein for each said word in each of said compressed layers there exists a related counter member and wherein each said counter member holds a counter value which equals a cumulative number of 1-bits, said cumulative number calculated from a first position in each of said bit vectors to each respective said word in said bit vector related to said counter member;

D. create a position vector V, wherein V[s] equals the position m of said key k in said key vector K, such that K[V[s]]=k, wherein s indicates a serial number of a respective hashed value H[m] in said SHB data structure;

whereby the hashed values in said SHB data structure being representatives of said integer members, and V[s] being representatives of said mapped values related to said respective integer members.

6. A computer program product that includes a computer-readable non-transient memory storing instructions for performing a method of searching for an integer member U, comprising:

A. providing a Super Hierarchiel Bitmaps (SHB) data structure representing a set of integer members, the SHB data structure being stored on a computer-readable non-transient memory in communication with a processor, the SHB data structure including;

(a) at least one word, wherein each said word contains a predefined number of bits, wherein each said bit is selected from the group including 1-bits and 0-bits;

(b) a plurality of bit vectors, each said bit vector containing at least one word, wherein said at least one word is selected from the group including an empty word containing only said 0-bits and a non-empty word containing at least one said 1-bit;

(c) one or more compressed layers representing corresponding one or more non-compressed layers, wherein;

(i) each said non-compressed layer includes one said bit vector, wherein said one or more non-compressed layers are organized sequentially, such that each of said one or more non-compressed layers except for a last non-compressed layer has a subsequent non-compressed layer related thereto;

(ii) the set of integers containing a plurality of positive integer members, wherein each member is represented by a 1-bit in the last non-compressed layer and wherein the position of each said 1-bit in said last non-compressed layer is equal to a value of said positive integer member;

(iii) each said non-empty word is represented by a respective 1-bit in a previous non-compressed layer such that a number of said 1-bits in said previous non-compressed layer is equivalent to a number of said non-empty words in a subsequent non-compressed layer and a position of each of said 1-bit in said previous non-compressed layer represents a corresponding position of each said non-empty word in said subsequent non-compressed layer;

wherein said compressed layers other than a first compressed layer include only said non-empty words, and each position of said empty words in said non compressed layer is represented by a position of each said 0-bit in said previous non-compressed layer, said empty words in any non-compressed layer being representative of removed empty words in any corresponding compressed layer, and each position of said removed empty words in a second compressed layer is represented by a position of each said 0-bit in said first compressed layer, so that said second compressed layer is decompressed into a second decompressed layer by calculating said positions of said removed empty words in said second compressed layer according to said positions of said 0-bits in said first compressed layer, and each said compressed layer other than said first and second compressed layers is decompressed sequentially by calculating said positions of said removed empty words in each said compressed layer according to said positions of said 0-bits in a previous decompressed layer; and

(d) one or more counter vectors, each of said counter vectors related to each of said one or more compressed layers, wherein for each said word in each of said compressed layers there exists a related counter member and wherein each said counter member holds a counter value which equals a cumulative number of 1-bits, said cumulative number calculated from a first position in each of said bit vectors to each respective said word in said bit vector related to said counter member;

searching for said integer member U represented by a bit representation in a last compressed layer in said SHB data structure using a SHB Search function.