# US 2021/0342325 A1 · Memory management using approximated count-min sketch data structures

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0342325 A1
- Document ID: US20210342325A1
- Status: Published application
- Kind: A1
- Application number: 16/921,230
- Filed: 2020-07-06
- Published: 2021-11-04
- Earliest claimed: 2020-05-01
- Assignees: Fastly, Inc.
- Applicants: Fastly, Inc.
- Inventors: Pierre-Louis Dubouilh
- Web page: https://patentgrep.com/patent/US20210342325A1

## CPC

- G06F 16/2282: {Tablespace storage structures; Management thereof}
- G06F 16/22: Indexing; Data structures therefor; Storage structures
- G06F 16/245: Query processing
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Disclosed herein are systems, methods, and software to use approximated counting with count-min sketch data structures. In one implementation, a computer may identify a value in a data object and determine whether a count identified in a count-min sketch data structure and associated with the value exceeds a threshold count. If the count does not exceed the threshold count, the computer may increase the count in a count-min sketch data structure. If the count does exceed the threshold, the computer may apply 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.

## Claims

### Claim 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.

### Claim 2 (depends on 1)

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

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 3)

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

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 1)

The method of claim 1 further comprising:
determining the threshold value based on previous counts associated with one or more values.

### Claim 8 (depends on 1)

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.

### Claim 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.

### Claim 10 (depends on 9)

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

### Claim 11 (depends on 9)

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.

### Claim 12 (depends on 11)

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

### Claim 13 (depends on 9)

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.

### Claim 14 (depends on 9)

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.

### Claim 15 (depends on 9)

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.

### Claim 16 (depends on 9)

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.

### Claim 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.

### Claim 18 (depends on 17)

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.

### Claim 19 (depends on 17)

The method of claim 17 further comprising:
determining the threshold value based on previous counts associated with one or more source IP addresses.

### Claim 20 (depends on 17)

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.
