Patent ID: 9143449
Filing Date: 2015-09-22
Classification: G06F,H04L

Abstract:
1. A method for performing a lookup, comprising: providing a plurality of data nodes, each data node comprising a data section and an array section, the array section comprising a plurality of pointers capable of linking each data node to at least one of the data nodes; providing a plurality of data trees, each data tree including at least one of the data nodes; providing an array having a plurality of bins, each bin comprising a counter indicating a number of data nodes associated with the bin and a pointer capable of linking the bin to at least one of the data trees; receiving a lookup request; performing a plurality of hash functions on the lookup request to obtain a plurality of outputs, each of the outputs being associated with a bin; identifying the bin associated with each of the outputs; determining whether a counter of the bin associated with each of the outputs is nonzero; upon determining that the counter of the bin associated with each of the outputs is nonzero, identifying the bin having the counter with a lowest value; identifying a data tree linked to the bin having the counter with the lowest value; and retrieving an entry corresponding to the lookup request from the identified data tree.