Multi-Level Directory Tree with Fixed Superblock and Block Sizes for Select Operations on Bit Vectors
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
17 Citations
18 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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
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. - View Dependent Claims (9, 10, 11, 12, 13)
-
-
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. - View Dependent Claims (15, 16, 17, 18)
- at least one data processor; and
Specification