Efficient high performance scalable pipelined searching method using variable stride multibit tries

A method for performing a search within a data collection to locate a target result that corresponds to a key, the key including a plurality of key bits, the method comprising:

• creating a plurality of tables in non-transient media, each table being configured to process a group of bits from the key, where said processing yields a processing result;
• providing table links that connect the tables to form a search tree, each table link being at least part of a processing result for a preceding table, each table link including information specifying a location of a subsequent table pointed to by the table link and a bit assignment for the subsequent table, the bit assignment being a number of bits from the key to be processed by the subsequent table, the tables, table links, and bit assignments being selected according to a distribution of information within the data collection;
• processing a first group of bits from the key using a first table in the search tree to obtain a first processing result;
• if the first processing result is a first table link, obtaining from the first table link the location and the bit assignment of the subsequent table to which the first table link points, and processing a next group of bits from the key using the subsequent table pointed to by the first table link, the next group of bits from the key having a number of bits equal to the bit assignment of the subsequent table;
• and
• successively processing next groups of bits from the key using subsequent tables pointed to by table pointers until a processing result is obtained that provides the target result.