Performance and memory bandwidth utilization for tree searches using tree fragmentation

A system for accessing memory through employment of data trees, comprising:

• a main memory;
• a local store functionally coupled to the main memory;
• and
• a plurality of tree fragments stored in the main memory, wherein the tree fragments are further loadable into the local store with substantially one memory access.

A method for improving performance of leaf node memory access and storage, comprising:

• determining a plurality of tree fragments from a data tree comprising a plurality of leaf nodes and decision nodes, the determined plurality of tree fragments comprising a decision node and a plurality of leaf nodes;
• hashing an indicia associated with a plurality of table entries, thereby creating hash table entries;
• assigning a first tree fragment to at least one hash table entry;
• and
• assigning a second tree fragment to at least one leaf node in the first tree fragment.

A method for improving performance of leaf node memory access and storage, comprising:

• creating a plurality of tree fragments from a data tree comprising a plurality of leaf nodes;
• storing the tree fragment in a contiguous area of memory as a function of a size of an input of a store;
• hashing an indicia associated with the plurality of table entries, thereby creating hash table entries;
• assigning a tree fragment to at least one hash entry;
• selecting a leaf node of the tree fragment;
• and
• assigning a second tree fragment to the selected leaf node.

A computer program product for initializing a data structure that employs a hash table and a plurality of tree fragments, the computer program product having a medium with a computer program embodied thereon, the computer program comprising:

• computer code for creating the hash table;
• computer code for creating the plurality of tree fragments;
• computer code for storing a tree fragment in its own contiguous memory segment;
• computer code for hashing at least one table entry corresponding to each tree fragment, thereby creating at least one hash key and at least one hash table entry;
• and
• computer code for assigning the tree fragment to at least one hash table entry.

A processor for initializing a data structure that employs a hash table and a plurality of tree fragments, the processor including a computer program comprising:

• computer code for determining a plurality of tree fragments from a data tree comprising a plurality of leaf nodes, the determined plurality of tree fragments comprising a decision node and one or more leaf nodes;
• computer code for storing each tree fragment in its own contiguous memory;
• computer code for hashing at least one table entry corresponding to each sub-tree fragment, thereby creating at least one hash key and at least one hash table entry;
• and
• computer code for assigning a tree fragment to at least one hash table entry.