Back to results
US 8,806,174 B2Granted
Method and system for hash key memory footprint reduction
AssigneeSTEC, Inc.
InventorsMohammad Reza Sadri, Saied Kazemi, Siddharth Choudhuri
Life of this patent
Estimating the term…
Abstract
A system and method are disclosed for storing data in a hash table. The method includes receiving data, determining a location identifier for the data wherein the location identifier identifies a location in the hash table for storing the data and the location identifier is derived from the data, compressing the data by extracting the location identifier; and storing the compressed data in the identified location of the hash table.
Claims11
A method for storing data in a hash table, the method comprising:
- receiving data;
- determining a location identifier for the data, wherein the location identifier identifies a location in the hash table for storing the data, wherein the location identifier is determined based on the data, wherein the location identifier comprises a set number, and wherein the determining the location identifier for the data includes determining a number of bits to extract from the data, based on (i) a block size of the hash table and (ii) a total number of sets in the hash table;
- compressing the data by extracting the location identifier from the data, wherein the compressing includes:
- extracting a plurality of middle bits from the data, based on the number of bits to extract;
- calculating a decimal value of the plurality of middle bits;
- if the decimal value is greater than the total number of sets;
- determining the set number by subtracting the total number of sets from the decimal value;
- and
- setting a wrapped bit to 1;
- otherwise,
- determining the set number as the decimal value;
- and
- setting the wrapped bit to 0;
- and
- storing the compressed data in the identified location of the hash table.
12 more elements
A storage device for storing data in a hash table, the storage device comprising:
- a host interface for communicating with a host device;
- a memory for storing data;
- a memory controller comprising logic stored in a computer readable medium, the logic configured to:
- receive data;
- determine a location identifier for the data, wherein the location identifier identifies a location in the hash table for storing the data, wherein the location identifier is derived from the data, wherein the location identifier includes a set number, and wherein the logic configured to determine the location identifier for the data includes logic configured to determine a number of bits to extract from the data, based on (i) a block size of the hash table and (ii) a total number of sets in the hash table;
- compress the data by extracting the location identifier, wherein the logic configured to compress the data includes logic configured to:
- extract a plurality of middle bits from the data, based on the number of bits to extract;
- calculate a decimal value of the plurality of middle bits;
- if the decimal value is greater than the total number of sets;
- determine the set number by subtracting the total number of sets from the decimal value;
- and
- set a wrapped bit to 1;
- otherwise,
- determine the set number as the decimal value;
- and
- set the wrapped bit to 0;
- and
- store the compressed data in the identified location of the hash table.
15 more elements
A transitory computer program product, tangibly embodied in a non-transitory computer-readable medium, the computer program product including instructions operable to cause a data processing apparatus to:
- receive data;
- determine a location identifier for the data, wherein the location identifier identifies a location in the hash table for storing the data, wherein the location identifier is derived from the data, wherein the location identifier includes a set number, and wherein the instructions operable to cause the data processing apparatus to determine the location identifier for the data comprise instructions operable to cause the data processing apparatus to determine a number of bits to extract from the data, based on (i) a block size of the hash table and (ii) a total number of sets in the hash table;
- compress the data by extracting the location identifier, wherein the instructions operable to cause the data processing apparatus to compress the data include instructions operable to cause the data processing apparatus to:
- extract a plurality of middle bits from the data, based on the number of bits to extract;
- calculate a decimal value of the plurality of middle bits;
- if the decimal value is greater than the total number of sets;
- determine the set number by subtracting the total number of sets from the decimal value;
- and
- set a wrapped bit to 1;
- otherwise;
- determine the set number as the decimal value;
- and
- set the wrapped bit to 0;
- and
- store the compressed data in the identified location of the hash table.
12 more elements
Dependencies are inferred from the claim text.