SYSTEM, METHOD AND DATA STRUCTURE FOR FAST LOADING, STORING AND ACCESS TO HUGE DATA SETS IN REAL TIME

• US 20140129530A1
• Filed: 06/27/2012
• Published: 05/08/2014
• Est. Priority Date: 06/27/2011
• Status: Active Grant

• Current Assignee: Jethrodata Ltd.
• Original Assignee: Jethrodata Ltd.
• Inventors: Raufman, Boaz
• Granted Patent: US 9,251,197 B2
• Time in Patent Office: Days
• US Class Current: 707/693
• 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

2. The computerized system of claim 1, wherein the data structure is created from set of integers using a Super Hierarchiel Bitmaps (SHB) Create function.

4. A machine-readable storage device having machine readable instructions tangibly stored thereon which, when executed by the machine, cause the machine to perform a method of database management, the method comprising the steps of:

(a) receiving, at a data loader process, a row of values of a raw data record;

(b) decomposing, at said loader process, said row of values to separate field values, said separation being dictated by a data scheme;

(c) assigning a numerical value key id to each said field value of said row of values;

(d) storing in a keys table one unique instance for each said key id;

(e) storing sequentially each said key id in a pre-allocated computer readable data memory block, said data block including rows divided into fields according to said data scheme separation, each said row having a record id indicating a position of said row in said data block within said plurality of data blocks;

(f) storing field indexes in a field indexes file, each said field index being equivalent to a list of unique instances of each said key id found in given said separate field in a given said data block;

(g) converting said field index to a Super Hierarchiel Bitmap (SHB) format;

(h) generating inverted indexes, including said field indexes and, for each unique instance of each said key id for each said separate field, a vector of said record ids of said rows in which said key ids equivalent to said field index are stored; and

(i) allocating a new said data memory block when a current row id of a said row of said key ids exceeds a preallocated number of rows in said data block.

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 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) a plurality of layers, each said layer includes one said bit vector, wherein said plurality of layers are organized sequentially;

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

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

(f) a plurality of compressed layers replacing said plurality of layers wherein said layers other than a first said layer is compressed to a said compressed layer by removing all of said empty words from said plurality of layers such that each position of said removed empty words in a said layer is represented by a position of each said 0-bit in said previous said layer, so that said compressed layer is decompressed by calculating said position of said removed empty words according to said position of said 0-bits in said previous layer;

(g) a said compressed layer situation sequentially before a subsequent said compressed layer wherein said 0-bits of said removed empty words, of said compressed layer situated sequentially before said subsequent compressed layer, are calculated when decompressing said subsequent compressed layer; and

(h) a plurality of counter vectors, each of said counter vectors related to each of said plurality of layers, wherein for each said word in each of said 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.

5. The machine-readable storage device of claim 4, wherein one unique instance of each of said raw data values is stored in said keys table, and wherein a said assigned key id of a said raw data value is equal to a position of said raw data value in said keys table.

6. The machine-readable storage device of claim 4, wherein each of said raw data values are selected from the group of data types including:

an integer, and a non-integer.

7. The machine-readable storage device of claim 6, wherein one unique instance of each of said non-integers is stored in said keys table, and wherein said assigned key id of a said non-integer is equal to a position of said non-integer field value in said keys table.

8. The machine-readable storage device of claim 6, for a given non-integer field value, a SHB Hash mechanism returns an existing key id for said given non-integer field value.

9. The machine-readable storage device of claim 4, wherein said field index further includes a counter storing a number of instances of said key ids in each said separate field.

10. The machine-readable storage device of claim 4, wherein said converting uses a data structure selected from the group including:

a tree, and a list, said list being ordered before said converting.

11. The machine-readable storage device of claim 6, wherein said key id of a said integer raw data value is derived using a reversible function.

11-1. The machine-readable storage device of claim 4, wherein said inverted indexes are created by:

(i) reading, sequentially, for each said separate field, said rows of said key ids stored in said data memory block;

(ii) providing a vector for each unique instance of a said key id in a said separate field in a said data block, said vector including a list of record ids of each of said rows which hold said key id in said separate field of a said data block.

12. The machine-readable storage device of claim 11, wherein said reversible function includes adding a predefined constant to said integer raw data value.

3. The computerized system of claim 1 wherein a positive integer member is searched using a Super Hierarchiel Bitmaps (SHB) Search function.

13. The machine-readable storage device of claim 4, wherein said raw data record is in a csv format.

14. The computerized system of claim 12, wherein each of said raw data values are selected from the group of data types including:

an integer, and a non-integer.

15. The computerized system of claim 12, wherein said plurality of ordered lists of said plurality of record ids are stored in a vector.

16. The computerized system of claim 12, wherein said plurality of ordered lists of said plurality of record ids are stored in a Compressed Hierarchical Bitmap (CHB).

17. The computerized system of claim 12, wherein said relationship is characterised as a mapping relationship.

12-2. 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 maintain a database management system that includes;

(a) a data-processing module configured to receive a plurality of rows of raw data values and decompose said rows of raw data values into separate fields of raw data values, wherein said data-processing module is further configured to assign a numerical value key id to each said raw data value;

(b) a plurality of Data Blocks each including a plurality of said key ids sequentially stored in rows according to said separate fields;

(c) a plurality of logical record ids, each said record id being for each of said key id rows, said record id having a value equal a sequential position of said row of key ids in said plurality of Data Blocks;

(d) a plurality of Data Columns, each Data Column holding a plurality of said key ids of a given said separate field of a said Data Block;

(e) a plurality of Inverted Indexes Blocks, each said Inverted Indexes Block having stored a plurality of ordered lists of said plurality of record ids and each said ordered list relating to each unique key id in a said separate field;

(f) a keys table, including a list of one unique instance of each said raw data value, wherein a sequential position of said raw data value is equivalent to a said assigned key id of said raw data value; and

(g) a plurality of field indexes, each said field index includes a list of unique instances of each said key ids of a said separate field of a said data block.

13-3. The computerized system of claim 12, wherein each said Data Block is a pre allocated memory block containing a predefined number of said rows of key ids, and each said row of key ids has a predefined size.