US 12,222,872 B1 · Method and apparatus for generating a histogram

Abstract

A method and apparatus for generating a histogram includes receiving an input key, determining if a linked-list node associated with the input key exists in the linked-list memory, in response to determining that a linked-list node associated with the input key does exist in the linked-list memory, increasing at least one count stored in the linked-list node associated with the input key, in response to determining that a linked-list node associated with the input key does not exist in the linked-list memory, determining if an available slot exists in the key storage memory, in response to determining that an available slot does not exist in the key storage memory determining a reclaimed slot in the key storage memory and a reclaimed node in the linked-list memory that is associated with the reclaimed slot, transmitting the data stored in the reclaimed slot in the key storage memory and the at least one count associated with the data stored in the reclaimed slot to an external device, and storing the key input in the reclaimed slot in the key storage memory and creating a new linked-list node associated with the reclaimed slot in the linked-list memory having at least one count.

Claims20

Dependent claims

A method of generating a histogram at a histogram engine having a linked-list memory and key storage memory, the method comprising:

receiving an input key;
determining if a linked-list node associated with the input key exists in the linked-list memory;
in response to determining that a linked-list node associated with the input key does exist in the linked-list memory, increasing at least one count stored in the linked-list node associated with the input key;
in response to determining that a linked-list node associated with the input key does not exist in the linked-list memory, determining if an available slot exists in the key storage memory;
in response to determining that an available slot does not exist in the key storage memory:
determining a reclaimed slot in the key storage memory and a reclaimed node in the linked-list memory that is associated with the reclaimed slot;
transmitting the data stored in the reclaimed slot in the key storage memory and the at least one count associated with the data stored in the reclaimed slot to an external device;
and
storing the key input in the reclaimed slot in the key storage memory and creating a new linked-list node associated with the reclaimed slot in the linked-list memory having at least one count.

6 more elements

An apparatus for generating a data histogram, the memory comprising:

a linked-list memory and a key storage memory;
at least one processor configured to:
receive an input key;
determine if a linked-list node associated with the input key exists in the linked-list memory;
in response to determining that a linked-list node associated with the input key does exist in the linked-list memory, increase at least one count stored in the linked-list node associated with the input key;
in response to determining that a linked-list node associated with the input key does not exist in the linked-list memory, determine if an available slot exists in the key storage memory;
in response to determining that an available slot does not exist in the key storage memory:
determine a reclaimed slot in the key storage memory and a reclaimed node in the linked-list memory that is associated with the reclaimed slot;
transmit the data stored in the reclaimed slot in the key storage memory and the at least count stored in the reclaimed node associated with the data stored in the reclaimed slot to an external device;
and
store the key input in the reclaimed slot in the key storage memory and creating a new linked-list node associated with the reclaimed slot in the linked-list memory having at least one count.

8 more elements

Dependencies are inferred from the claim text.

Method and apparatus for generating a histogram

Life of this patent

Method and apparatus for generating a histogram

Life of this patent

Abstract

Claims20