Counting bloom filter

1. A method performed under control of a computing device, the method comprising:

obtaining a result of a j-th set of hash functions with regards to a keyword, wherein the j is an integer, and wherein the j-th set of hash functions includes k number of hash functions;

marking a head marker into a bit array of a bloom filter based at least in part on the result of the j-th set of hash functions, if the j is zero, to indicate that the keyword is registered,

wherein the bit array includes d number of slots, an f-bit binary number is recorded in each of the d slots, and the result of the each hash function corresponds to one slot from 1 to the d, and

wherein the marking the head marker includes setting 1 of the f-bit binary number into k number of slots among the d slots of the bit array, and the result of the each hash function which is included in the j-th set of hash functions corresponds to each of the k slots of the bit array; and

marking a tail marker into the bit array of the bloom filter based at least in part on the result of the j-th set of hash functions, if the j is same as or larger than 1, to indicate how many times the keyword is registered,

wherein the marking the tail marker includes increasing the f-bit binary number by one, which is stored in other k number of slots among the d slots of the bit array, and the result of the each hash function which is included in the j-th set of hash functions corresponds to each of the other k slots of the bit array.

2. The method of claim 1 , wherein the other k slots include at least one of the k slots.

3. The method of claim 1 , further comprising:

determining that the f-bit binary number stored in the other k slots of the bit array are larger than zero; and

determining that a counting number of the keyword is the j which is same as or larger than 1.

4. The method of claim 1 , further comprising:

obtaining a result of a (j+1)-th set of hash functions of the keyword;

decreasing the f-bit binary number by one, which is stored in the other k slots among the d slots of the bit array; and

re-marking the tail marker into the bit array of the bloom filter based at least in part on the result of the (j+1)-th set of hash functions, if the j is same as or larger than 1.

5. The method of claim 4 , wherein the re-marking the tail marker includes increasing the f-bit binary number by one, which is stored in the other k number of slots among the d slots of the bit array,

wherein the result of the each hash function which is included in the (j+1)-th set of hash functions corresponds to each of the other k slots of the bit array.

6. A method performed under control of a computing device, the method comprising:

obtaining a result of a particular set of hash functions of an i s -th digit with regards to a keyword, wherein i is an integer greater than one, wherein s is an integer greater than or equal to zero, and wherein the particular set of hash functions includes a particular number of hash functions;

marking a head marker into a bit array of the i s -th digit of a bloom filter based at least in part on the result of the particular set of hash functions, so as to indicate that the keyword is registered, in response to a determination that the particular set is a first set among a first plurality of sets of hash functions,

wherein the bit array includes a first number of slots, and a result of each hash function included in the particular set of hash functions corresponds to one slot among the first number of slots, and

wherein the marking the head marker includes setting 1 as a binary number into a particular number of slots, among the first number of slots, that is equal to the particular number of hash functions, and the result of the each hash function corresponds to each of the particular number of slots; and

marking a tail marker into the bit array of the i s -th digit of the bloom filter based at least in part on the result of the particular set of hash functions, so as to indicate a number of times the keyword is registered, in response to a determination that the particular set is same as or greater than a second set among the first plurality of sets of hash functions,

wherein the marking the tail marker includes increasing the binary number by one, which is stored in other number of slots among the first number of slots, and the result of the each hash function corresponds to each of the other number of slots among the first number of slots, and

wherein the first plurality of sets of hash functions is within a range from the first set to an i-th set.

7. The method of claim 6 , further comprising:

obtaining a result of another set of hash functions of an i (s+1) -th digit with regards to the keyword; and

marking a tail marker into a bit array of the i (s+1) -th digit of the bloom filter based at least in part on the result of the other set of hash functions of the i (s+1) -th digit, wherein the other set of hash functions is a set among a second plurality of sets of hash functions,

wherein the second plurality of sets of hash functions is within a range from a first set to an i-th set.

8. The method of claim 7 , wherein:

the obtaining the result of the other hash functions of the i (s+1) -th digit includes obtaining a result of a particular number of hash functions included in the other set of hash functions, the particular number of hash functions in the other set of hash functions is equal to the particular number of hash functions in the particular set of hash functions,

the marking the tail marker into the bit array of the i (s+1) -th digit includes marking the tail marker into at least one slot of a second number of slots,

the method further comprises

recording a binary number in each of the second number of slots, wherein the binary number is within a range from zero to (i- 1 ),

the first number of slots is same as or greater than the second number of slots, and

the particular number of hash functions in the other set of hash functions is smaller than the first number of slots and the second number of slots.

9. The method of claim 8 ,

wherein the obtaining the result of the other set of hash functions includes obtaining a result of the each hash function included in the other set of hash functions that corresponds to one slot among the second number of slots.

10. The method of claim 9 , wherein:

the marking the tail marker into the bit array of the i (s+1) -th digit includes increasing the binary number by one, which is stored in the other number of slots, among the second number of slots, that is equal to the particular number of hash functions of the bit array of the i (s+1) -th digit, and

the result of the each hash function which is included in the other set of hash functions of the i (s+1) -th digit corresponds to each of the other number of slots among the second number of slots.

11. The method of claim 10 , further comprising:

determining that the binary numbers stored in the other number of slots among the first number of slots of the bit array of the i s -th digit is greater than zero;

determining that a counting number of the i s -th digit is a total number of sets in the first plurality of sets of hash functions;

determining that the binary numbers stored in the other number of slots among the second number of slots of the bit array of the i (s+1) -th digit is greater than zero;

determining that a counting number of the i (s+1) -th digit is a total number of sets in the second plurality of sets of hash functions; and

obtaining a counting number of the keyword based at least in part on the total number of sets in the first plurality of sets of hash functions and the total number of sets in the second plurality of sets of hash functions.

12. The method of claim 10 , further comprising:

obtaining a result of a next set of hash functions of the i s -th digit with regards to the keyword;

wherein the next set of hash functions of the i s -th digit is positioned next to the particular set of hash functions;

decreasing the binary number by one, which is stored in the other number of slots among the first number of slots of the bit array of the i s -th digit;

re-marking the tail marker into the bit array of the i s -th digit of the bloom filter based at least in part on the result of the next set of hash functions of the i s -th digit, in response to a determination that the particular set of hash functions is same as or greater than the second set among the first plurality of sets of hash functions;

obtaining a result of a next set of hash functions of the i (s+1) -th digit with regards to the keyword;

wherein the next set of hash functions of the i (s+1) -th digit is positioned next to the other set of hash functions;

decreasing the binary number by one, which is stored in the particular number of slots among the second number of slots of the bit array of the i (s+1) i-th digit; and

re-marking the tail marker into the bit array of the i (s+1) -th digit of the bloom filter based at least in part on the result of the next set of hash functions of the i (s+1) -th digit, in response to a determination that the other set is same as or greater than a first set among the second plurality of sets of hash functions.

13. A non-transitory computer-readable storage medium having stored thereon computer-executable instructions that, in response to execution, cause a computing device to perform or control performance of operations to:

obtain a result of a j-th set of hash functions with regard to a keyword, wherein the j is an integer, and wherein the j-th set of hash functions includes k number of hash functions;

mark a head marker into a bit array of a bloom filter based at least in part on the result of the j-th set of hash functions, if the j is zero, to indicate that the keyword is registered,

wherein the bit array includes d number of slots, an f-bit binary number is recorded in each of the d slots, and the result of each hash function corresponds to one of from 1 to the d, and

wherein the marking the head marker includes setting 1 of an f-bit binary number into k number of slots among the d slots of the bit array, and the result of each hash function which is included in the j-th set of hash functions corresponds to each of the k slots of the bit array; and

mark a tail marker into the bit array of the bloom filter based at least in part on the result of the j-th set of hash functions, if the j is same as or larger than 1, to indicate how many times the keyword is registered,

wherein the marking the tail marker includes increasing the f-bit binary number by one, which is stored in other k number of slots among the d slots of the bit array, and the result of the each hash function which is included in the j-th set of hash functions corresponds to each of the other k slots of the bit array.

14. A non-transitory computer-readable storage medium having stored thereon computer-executable instructions that, in response to execution, cause a computing device to perform or control performance of operations to:

obtain a result of a j-th set of hash functions of an i s -th digit with regards to a keyword, wherein the i is an integer which is larger than one, wherein the j is an integer which is within a range of from zero to (i- 1 ), wherein the s is an integer which is same as or larger than zero, and wherein the j-th set of hash functions includes k number of hash functions;

mark a head marker into a bit array of the i s -th digit of a bloom filter based at least in part on the result of the j-th set of hash functions, if the j is zero, to indicate that the keyword is registered,

wherein the bit array of the i s -th digit includes d number of slots, and the result of the each hash function included in the j-th set of hash functions corresponds to one of from 1 to the d, and

wherein the mark of the head marker includes setting 1 of an f-bit binary number into k number of slots among the d slots of the bit array of the i s -th digit, and the result of the each hash function corresponds to each of the k slots of the bit array of the i s -th digit; and

mark a tail marker into the bit array of the i s -th digit of the bloom filter based at least in part on the result of the j-th set of hash functions of the i s -th digit, if the j is same as or larger than 1, to indicate a number of times the keyword is registered,

wherein the marking the tail marker includes increasing the f-bit binary number by one, which is stored in other k number of slots among the d slots of the bit array of the i s -th digit, and the result of the each hash function corresponds to each of the other k slots of the bit array of the i s -th digit.

15. A system, comprising:

a memory; and

a computing device operatively coupled to the memory, the computing device comprising:

a hash function generator configured to obtain a result of a particular set of hash functions with regards to a keyword, wherein the particular set of hash functions includes a particular number of hash functions;

a marker coupled to the hash function generator and configured to:

mark a head marker into a bit array of a bloom filter in the memory based at least in part on the result of the particular set of hash functions, so as to indicate that the keyword is registered, in response to a determination that the particular set is a first set among a plurality of sets of hash functions,

wherein the bit array includes a number of slots, and a result of each hash function included in the particular set of hash functions corresponds to one slot among the number of slots, and

wherein the marker is further configured to mark the head marker by setting a binary number into a particular number of slots, among the number of slots, that is equal to the particular number of hash functions; and

mark a tail marker into the bit array of the bloom filter based at least in part on the result of the particular set of hash functions, so as to indicate a number of times the keyword is registered, in response to a determination that the particular set is same as or greater than a second set among the plurality of sets of hash functions,

wherein the marker is further configured to mark the tail marker by increasing the binary number by one, which is stored in other number of slots among the number of slots, and the result of the each hash function corresponds to each of the other number of slots; and

a counter, coupled to the marker, configured to determine a counting number of the keyword based on the marking into the bit array by the marker.

16. The system of claim 15 , wherein the other number of slots includes at least one slot of the particular number of slots.

17. The system of claim 15 , wherein the counter is configured to:

determine that the binary number stored in the other number of slots is greater than zero; and

determine that the counting number of the keyword is equal to the particular set of hash functions which is same as or greater than 1.

18. The system of claim 15 , wherein the hash function generator is configured to:

obtain a result of a set of hash functions with regards to the keyword, wherein the set of hash functions is positioned next to the particular set of hash functions;

decrease the binary number by one, which is stored in the other number of slots among the number of slots of the bit array; and

re-mark the tail marker into the bit array of the bloom filter based at least in part on the result of the set of hash functions, in response to a determination that the particular set of hash functions is same as or greater than the first set.