Generating a hierarchical data structure associated with a plurality of known arbitrary-length bit strings used for detecting whether an arbitrary-length bit string input matches one of a plurality of known arbitrary-length bit string
View Patent ↗Generating and using a high-speed, scalable, and easily updateable data structure are described. The proposed data structure provides minimal perfect hashing functionality while intrinsically supporting low-cost set-membership queries. In other words, in some embodiments, it provides at most one match candidate in a set of known arbitrary-length bit strings that is used to match the query.
1. A method for generating a hierarchical data structure associated with a plurality of arbitrary-length bit strings, the method comprising:
a) hashing, for each of the plurality of arbitrary-length bit strings, the arbitrary-length bit string;
b) partitioning, for each of the plurality of arbitrary-length bit strings, results of the hashing to a next level of the hierarchical data structure to generate partition results;
c) defining a next level bit map based on the partition results;
d) repeating acts (a) through (c); and
e) storing, for each of the plurality of arbitrary-length bit strings, the arbitrary-length bit string or a pointer thereto, in a memory location,
wherein a hash of one of the arbitrary-length bit strings at each level of the hierarchical data structure defines a bit location of the next level bit map, and
wherein a concatenation of at least one bit starting at the defined bit location of the next level bit map at each level of the hierarchical data structure defines an address of the memory location storing the arbitrary-length bit string or a pointer thereto.
2. The method of claim 1 wherein acts (a) through (c) are repeated until further partitioning is not possible.
3. The method of claim 1 wherein the hierarchical data structure is a K-ary trie, where K is a whole number greater than or equal to 2.
4. The method of claim 3 wherein the hierarchical data structure provides a perfect hashing function.
5. The method of claim 1 wherein the hierarchical data structure is a K-ary trie, where K is an integer power of 2 and wherein the hierarchical data structure provides a minimal perfect hashing function.
6. The method of claim 1 wherein the hierarchical data structure is a binary trie.
7. The method of claim 6 wherein the hierarchical data structure provides a minimal perfect hashing function.
8. The method of claim 1 wherein the arbitrary-length bit string is a communications network intrusion signature.
9. The method of claim 1 wherein the arbitrary-length bit string is a nucleotide sequence.
10. The method of claim 1 wherein acts (a)-(d) comprise:
for each of the plurality of arbitrary-length bit strings,
1) hashing the arbitrary-length bit string, using a first hashing function, to determine a bit location of a data bit map,
2) setting a bit of the data bit map at the determined bit location to “1”, and
3) incrementing a count of an occupancy map corresponding to the determined bit location;
partitioning the arbitrary-length bit strings using counts of the occupancy table to
1) determine, for each of the arbitrary-length bit strings, whether the arbitrary length bit string will be hashed to a first of two sub-data bit maps or a second of two sub-data bit maps;
2) generate a next node bit map, having a same number of bits as the data bit map, wherein, for each of a plurality of bit locations of the next node bit map, a value at the bit location is set to “0” if an arbitrary length bit string hashed to the corresponding bit location of the data bit map is to be hashed to the first of the two sub-data bit maps, and is set to “1” if an arbitrary length bit string hashed to the corresponding bit location of the data bit map is to be hashed to the second of the two sub-data bit maps, and
for each of the plurality of arbitrary-length bit strings,
1) hashing the arbitrary length bit string, using a second hashing function, to determine a bit location of the sub-data bit map to which the arbitrary length bit string has been partitioned,
2) setting a bit of the sub-data bit map to which the arbitrary length bit string has been partitioned, at the determined bit location, to “1”, and
3) incrementing a count of a first or second sub-occupancy map corresponding to the determined bit location of the first or second sub-data bit map; and
for each of the sub-data bit maps, repeating acts (b) and (c) to generate two further sub-data bit maps until each of the two further sub-data bit maps has an occupancy count of 1 or less.
11. The method of claim 1 wherein the act of partitioning uses a greedy algorithm.
12. The method of claim 1 wherein the act of partitioning uses a blackjack algorithm.
13. The method of claim 1 wherein at least one of the acts of partitioning uses a blackjack algorithm and at least one subsequent act of partitioning uses a greedy algorithm.
14. Apparatus for generating a hierarchical data structure associated with a plurality of arbitrary-length bit strings, the apparatus comprising: at least one processor programmed to:
a) hash, for each of the plurality of arbitrary-length bit strings, the arbitrary-length bit string,
b) partition, for each of the plurality of arbitrary-length bit strings, results of the hashing to a next level of the hierarchical data structure to generate partition results, and
c) define a next level bit map based on the partition results; and a storage device storing, for each of the plurality of arbitrary-length bit strings, the arbitrary-length bit string or a pointer thereto, in a memory location,
wherein a hash of one of the arbitrary-length bit strings at each level of the hierarchical data structure defines a bit location of the next level bit map, and
wherein a concatenation of at least one bit starting at the defined bit location of the next level bit map at each level of the hierarchical data structure defines an address of the memory location storing the arbitrary-length bit string or a pointer thereto.
15. The apparatus of claim 14 wherein the hierarchical data structure is a K-ary trie, where K is a whole number greater than or equal to 2.
16. The apparatus of claim 15 wherein the hierarchical data structure provides a perfect hashing function.
17. The apparatus of claim 14 wherein the hierarchical data structure is a K-ary trie, where K is an integer power of 2 and wherein the hierarchical data structure provides a minimal perfect hashing function.
18. The apparatus of claim 14 wherein the hierarchical data structure is a binary trie.
19. The apparatus of claim 18 wherein the hierarchical data structure provides a minimal perfect hashing function.
20. The apparatus of claim 14 wherein the arbitrary-length bit string is a communications network intrusion signature.
21. The apparatus of claim 14 wherein the arbitrary-length bit string is a nucleotide sequence.
22. The apparatus of claim 14 wherein the at least one processor uses a greedy algorithm for the partitioning.
23. The apparatus of claim 14 wherein the at least one processor uses a blackjack algorithm for the partitioning.
24. The apparatus of claim 14 wherein the at least one processor uses a blackjack algorithm and then uses a greedy algorithm for the partitioning.
25. The apparatus of claim 14 wherein the at least one processor includes at least one of (A) a microprocessor, (B) a field programmable gate array, and (C) an application specific integrated circuit.