Method and system for optimizing direct tables and trees

A method for selecting a direct table and a plurality of corresponding trees in a computer system, the method comprising the steps of:

• (a) selecting a plurality of widths for the direct table;
• (b) probabilistically determining at least one desired property of the direct table and the plurality of corresponding trees for the plurality of widths, the at least one desired property is a speed of lookup for the direct table and the plurality of corresponding trees, wherein probabilistically determining the at least one property step (b) further includes the step of:
• (b1) for the plurality of widths, probabilistically determining a minimum possible depth and a maximum possible depth for the plurality of trees utilizing a number of items;
• and
• (c) selecting a width of the plurality widths for the direct table and the plurality of corresponding trees based on the at least one desired property of the direct table and the plurality of corresponding trees, the width selecting step (c) further including the step of
• (c1) selecting the width for the direct table to minimize the speed of lookup for the direct table and the plurality of corresponding trees.

A system for searching for a plurality of items comprising:

• a direct table having a width;
• and
• the plurality of corresponding trees for the direct table;
• the width being selected form a plurality of widths by probabilistically determining at least one desired property of the direct table and a plurality of corresponding trees for the plurality of widths and selecting the width for the direct table and the plurality of corresponding trees based on the at least one desired property of the direct table and the plurality of corresponding trees;
• wherein the at least one desired property is a total cost of the direct table and the plurality of corresponding trees and wherein the width for the direct table is selected to minimize the total cost of a direct table and the plurality of corresponding trees
• wherein the at least on property is probabilistically determined by determining an expected value of a number of tree nodes of the corresponding trees for the plurality of widths and determining the sum of the cost of the direct table and the plurality of corresponding trees utilizing the expected value.

A system for searching for a plurality of items comprising:

• a direct table having a width;
• and
• the plurality of corresponding trees for the direct table;
• the width being selected form a plurality of widths by probabilistically determining at least one desired property of the direct table and a plurality of corresponding trees for the plurality of widths and selecting the width for the direct table and the plurality of corresponding trees based on the at least one desired property of the direct table and the plurality of corresponding trees;
• wherein the at least one desired property is a speed of lookup for the direct table and the plurality of corresponding trees and wherein the width is further selected by selecting the width of the plurality of widths that minimizes the speed of the lookup for the direct table and the plurality of corresponding trees;
• wherein the at least one property is determined by probabilistically determining a minimum possible depth and a maximum possible depth for the plurality of trees utilizing a number of items.