MEMORY MANAGEMENT USING APPROXIMATED COUNT-MIN SKETCH DATA STRUCTURES

1 . A method comprising:

obtaining a value;

determining whether a count associated with the value exceeds a threshold count based on a count-min sketch data structure;

if the count associated with the value does not exceed the threshold count, increasing the count in the count-min sketch data structure;

if the count associated with the value does exceed the threshold count:

applying a probability function to determine whether to increase the count; and

in response to the probability function indicating an increase to the count, increasing the count in the count-min sketch data structure.

2 . The method of claim 1 , wherein the value comprises a numerical value or string of characters.

3 . The method of claim 1 further comprising:

receiving a data packet comprising the value; and

wherein obtaining the value comprises extracting the value from the data packet.

4 . The method of claim 3 , wherein the value comprises an internet protocol (IP) address.

5 . The method of claim 1 further comprising:

obtaining a query for the count associated with the value;

determining that the count does not exceed the threshold count based on the count-min sketch data structure; and

using the count to respond to the query.

6 . The method of claim 1 further comprising:

obtaining a query for the count associated with the value;

determining that the count exceeds the threshold count based on the count-min sketch data structure;

determining an approximated count using the count from the count-min sketch data structure and an approximated count function; and

using the approximated count as the count to respond to the query.

7 . The method of claim 1 further comprising:

determining the threshold value based on previous counts associated with one or more values.

8 . The method of claim 1 further comprising:

obtaining a second value;

determining whether a second count associated with the second value exceeds the threshold count based on the count-min sketch data structure;

if the second count associated with the second value does not exceed the threshold count, increasing the second count in the count-min sketch data structure;

if the second count associated with the second value does exceed the threshold count:

applying the probability function to determine whether to increase the second count; and

in response to the probability function indicating an increase to the second count, increasing the second count in the count-min data structure.

9 . A computing apparatus comprising:

a storage system;

a processing system operatively coupled to the storage system; and

program instructions stored on the storage system that, when executed by the processing system, direct the processing system to:

obtain a value;

determine whether a count associated with the value exceeds a threshold count based on a count-min sketch data structure;

if the count associated with the value does not exceed the threshold count, increase the count in the count-min sketch data structure;

if the count associated with the value does exceed the threshold count:

apply a probability function to determine whether to increase the count; and

in response to the probability function indicating an increase to the count, increase the count in the count-min sketch data structure.

10 . The computing apparatus of claim 9 , wherein the value comprises a numerical value or a string of characters.

11 . The computing apparatus of claim 9 , wherein the program instructions further direct the processing system to:

receive a data packet comprising the value; and

wherein obtaining the value comprises extracting the value from the data packet.

12 . The computing apparatus of claim 11 , wherein the value comprises an internet protocol (IP) address.

13 . The computing apparatus of claim 9 , wherein the program instructions further direct the processing system to:

obtain a query for the count associated with the value;

determine that the count does not exceed the threshold count based on the count-min sketch data structure; and

use the count to respond to the query.

14 . The computing apparatus of claim 9 , wherein the program instructions further direct the processing system to:

obtain a query for the count associated with the value;

determine that the count exceeds the threshold count based on the count-min sketch data structure;

determine an approximated count using the count from the count-min sketch data structure and an approximated count function; and

use the approximated count as the count to respond to the query.

15 . The computing apparatus of claim 9 , wherein the program instructions further direct the processing system to determine the threshold value based on previous counts associated with one or more values.

16 . The computing apparatus of claim 9 , wherein the program instructions further direct the processing system to:

obtain a second value;

determine whether a second count associated with the second value exceeds the threshold count based on the count-min sketch data structure;

if the second count associated with the second value does not exceed the threshold count, increase the second count in the count-min sketch data structure;

if the second count associated with the second value does exceed the threshold count:

applying the probability function to determine whether to increase the second count; and

in response to the probability function indicating an increase to the second count, increase the second count in the count-min data structure.

17 . A method of operating a computer comprising:

receiving a packet;

identifying a source internet protocol (IP) address in the packet;

determining whether a count associated with the source IP address exceeds a threshold count based on a count-min sketch data structure;

if the count associated with the source IP address does not exceed the threshold count, increasing the count in the count-min sketch data structure;

if the count associated with the value does exceed the threshold count:

applying a probability function to determine whether to increase the count; and

in response to the probability function indicating an increase to the count, increasing the count in the count-min sketch data structure;

obtaining a query for the count associated with the source IP address; and

responding to the query based on the count in the count-min sketch data structure.

18 . The method of claim 17 , wherein responding to the query based on the count in the count-min sketch data structure comprises:

determining an approximated count using the count from the count-min sketch data structure and an approximated count function; and

using the approximated count as the count to respond to the query.

19 . The method of claim 17 further comprising:

determining the threshold value based on previous counts associated with one or more source IP addresses.

20 . The method of claim 17 , wherein responding to the query based on the count in the count-min sketch data structure comprises:

determining that the count in the count-min sketch data structure does not exceed the threshold count; and

using the count to respond to the query.