Patent Document ID: 7868792
Application ID: 12366503

Base Claim:
1. A method for generating a hierarchical data structure associated with a plurality of arbitrary-length bit strings, the method comprising: a) for each of the plurality of arbitrary-length bit strings within a group, 1) hashing the arbitrary-length bit string, using a selected hash function from a plurality of hash functions, to determine a hash value corresponding to a location of a virtual bin, 2) incrementing an occupancy count associated with the determined location of the virtual bin; b) determining a boundary value corresponding to a location of the virtual bin using the occupancy counts of the virtual bin; c) storing an indication of the hash function and the determined boundary value; d) for each of the plurality of arbitrary-length bit strings, assigning the arbitrary-length bit string to one of a first group and a second group using the virtual bin location of its hash value and the determined boundary value, wherein a first bit is assigned to the arbitrary-length bit string if it is assigned to a first group and a second bit is assigned to the arbitrary-length bit string if it is assigned to a second group; e) for each of the groups, repeating acts (a) through (d) to generate two further sub-groups until each of the two further sub-groups has one or less assigned arbitrary-length bit string; and f) storing, for each of the plurality of arbitrary-length bit strings, the arbitrary-length bit string or a pointer thereto, in a memory location defined by a concatenation of the assigned bits.

---

Claim 2:
2. The method of claim 1 wherein a boundary value corresponding to a location of a virtual bin is a value such that the summation of occupancy counts at every location greater than the boundary value is equal to half the summation of occupancy counts at every location of the virtual bin.