Multi-Level Directory Tree with Fixed Superblock and Block Sizes for Select Operations on Bit Vectors

• US 20180173710A1
• Filed: 12/15/2016
• Published: 06/21/2018
• Est. Priority Date: 12/15/2016
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Maftuleac, Daniela, Lopez-Ortiz, Alejandro, Pound, Jeffrey, Salinger, Alejandro
• Granted Patent: US 10,984,029 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: G06F 16/3347 using vector based model

Abstract

A bit vector having a bit vector length is accessed. A select operator directory tree can be generated using the bit vector. The select operator directory tree includes a first level of superblocks including large superblocks and small superblocks, a second level of blocks including large blocks and small blocks, each block associated with one of the superblocks, and a third level of sub-blocks, each sub-block associated with a block. The large superblocks each have, a length greater than a first constant that is independent of the bit vector length and the large blocks each have a length greater than a second constant that is independent of the bit vector length. The select operator directory tree can be stored. Related apparatus, systems, techniques and articles are also described.

Claims

1. A method comprising:

accessing a bit vector having a bit vector length;

generating, using the bit vector, a select operator directory tree including;

a first level of superblocks including large superblocks and small superblocks;

a second level of blocks including large blocks and small blocks, each block associated with one of the superblocks;

a third level of sub-blocks, each sub-block associated with a block; and

the large superblocks each have a length greater than a first constant that is independent of the bit vector length and the large blocks each have a length greater than a second constant that is independent of the bit vector length; and

storing the select operator directory tree.

2. The method of claim 1, wherein blocks associated with large superblocks characterize explicit positions of a bit-type of the bit vector, blocks associated with small superblocks characterize locations of sub-blocks, the sub-blocks associated with the large blocks characterize explicit positions of the bit-type of the bit vector, and sub-blocks associated with small blocks characterize a cumulative number of occurring bit-types in a portion of the bit vector.

3. The method of claim 1, wherein the first level of superblocks is represented as at least a first level array storing a location of a predetermined occurrence of a bit-type in the bit vector, the second level of blocks is represented as at least a plurality of second level arrays, and the third level of sub-blocks is represented as at least a plurality of third level arrays.

4. The method of claim 1, wherein generating the select operator directory tree includes:

determining a boundary of each superblock in the bit vector as a predetermined occurrence of a bit-type in the bit vector;

determining whether each superblock is large or small based on whether a given superblock has a length greater than the first constant that is independent of the bit vector length;

storing explicit positions of the bit-type of each large superblock in each associated block;

determining boundary of each block associated with a small superblock in the bit vector;

determining whether each block associated with the small superblocks is large or small based on whether a given block has a length greater than the second constant that is independent of the bit vector length;

storing explicit positions of the bit-type of each large block in each associated sub-block; and

storing, in each respective sub-block associated with each respective large block, a cumulative number of occurring bit-types in an associated portion of the bit vector.

5. The method of claim 4, wherein the predetermined occurrence of the bit-type in the bit vector defining the boundary of each superblock is 2¹². The first constant that is independent of the bit vector length is equal to 2²⁰, and the second constant that is independent of the bit vector length is equal to 2¹⁴.

6. The method of claim 1, wherein a bit-type is a 0 bit or a 1 bit, and wherein the bit vector is an array of 0 and 1 bits.

7. The method of claim 1, wherein at least one of the accessing, the generating, and the storing is performed by at least one data processor forming part of at least one computing system.

8. A method comprising:

receiving data characterizing a bit vector and a bit-select value;

searching a select operator directory tree for a position of a bit-select value occurrence of a bit-type, the select operator directory tree including;

a first level of superblocks including large superblocks and small superblocks;

a second level of blocks including large blocks and small blocks, each block associated with one of the superblocks;

a third level of sub-blocks, each sub-block associated with a block;

the large superblocks each have a length greater than a first constant that is independent of a bit vector length and the large blocks each have a length greater than a second constant that is independent of the bit vector length; and

providing the position of the bit-select value occurrence of the bit-type.

9. The method of claim 8, wherein blocks associated with large superblocks characterize explicit positions of the bit-type of the bit vector, blocks associated with small superblocks characterize locations of sub-blocks, the sub-blocks associated with the large blocks characterize explicit positions of the bit-type of the bit vector, and sub-blocks associated with small blocks characterize a cumulative number of occurring bit-types in a portion of the bit vector.

10. The method of claim 8, wherein the first level of superblocks is represented as at least a first level array storing a location of a predetermined occurrence of the bit-type in the bit vector, the second level of blocks is represented as at least a plurality of second level arrays, and the third level of sub-blocks is represented as at least a plurality of third level arrays.

11. The method of claim 10, wherein the searching includes:

determining if the bit-select value is contained in the first level array;

determining, using the first level array, a superblock having the bit-select value occurrence of the bit-type;

determining one of the plurality of second level arrays associated with determined superblock;

determining if the bit-select value is contained in the determined one of the plurality of second level arrays;

determining one of the plurality of the third level arrays associated with the determined second level array having the bit-select value occurrence of the bit-type; and

determining a position of the bit-select value occurrence of the bit-type from the determined one of the plurality of the third level arrays.

12. The method of claim 8, wherein a bit-select operation is performed during a text search engine operation.

13. The method of claim 8, wherein at least one of the receiving, the searching, and the providing is performed by at least one data processor forming part of at least one computing system.

14. A system comprising:

at least one data processor; and

memory storing instructions, which when executed by the at least one data processor, implement operations comprising;

receiving data, characterizing a bit vector and a bit-select value;

searching a select operator directory tree for a position of a bit-select value occurrence of a bit-type, the select operator directory tree including;

a first level of superblocks including large superblocks and small superblocks;

a second level of blocks including large blocks and small blocks, each block associated with one of the superblocks;

a third level of sub-blocks, each sub-block associated with a block;

the large superblocks each have a length greater than a first constant that is independent of a bit vector length and the large blocks each have a length greater than a second constant that is independent of the bit vector length; and

providing the position of the bit-select value occurrence of the bit-type.

15. The system of claim 14, wherein blocks associated with large superblocks characterize explicit positions of the bit-type of the bit vector, blocks associated with small superblocks characterize locations of sub-blocks, the sub-blocks associated with the large blocks characterize explicit positions of the bit-type of the bit vector, and sub-blocks associated with small blocks characterize a cumulative number of occurring bit-types in a portion of the bit vector.

16. The system of claim 14, wherein the first level of superblocks is represented as at least a first level array storing a location of a predetermined occurrence of the bit-type in the bit vector, the second level of blocks is represented as at least a plurality of second level arrays, and the third level of sub-blocks is represented as at least a plurality of third level arrays.

17. The system of claim 16, wherein the searching includes:

determining if the bit-select value is contained in the first level array;

determining, using the first level array, a superblock having the bit-select value occurrence of the bit-type;

determining one of the plurality of second level arrays associated with the determined superblock;

determining if the bit-select value is contained in the determined one of the plurality of second level arrays;

determining one of the plurality of the third level arrays associated with the determined second level array having the bit-select value occurrence of the bit-type; and

determining a position of the bit-select value occurrence of the bit-type from the determined one of the plurality of the third level arrays.

18. The system of claim 14, wherein a bit-select operation is performed during a text search engine operation.