SPARSE COLUMN-AWARE ENCODINGS FOR NUMERIC DATA TYPES
Methods and apparatus for sparse column-aware encodings for numeric data types, including integer data and floating-point data (float, double, etc.). The encoding schemes are tailored to take advantage of column addressable memories such as stochastic associative memories (SAM) to enable Stochastic Associative Search (SAS), which is a highly efficient and fast way of searching through a very large database of records (order of Billions) and finding similar records to a given query record (search key). Techniques are also disclosed for performing range searches for both integer and floating-point data types. The integer or float data is converted to Hexadecimal form and encoded using an m-of-n constant weight encoding. Only the columns with set bits in search keys need to be read, which significantly reduces the number of reads required for searches.
1 - 20 . (canceled)
21 . An apparatus, comprising:
one or more memories comprising a plurality of rows and a plurality of columns of memory cells to store a plurality of bit vectors; and
circuitry coupled to the one or more memories, wherein the circuitry is to:
generate, based on a query from a requesting entity, a search key in an encoded format, wherein the search key comprises a bit vector comprising a plurality of set bits;
identify one or more columns, of the plurality of columns, that are associated with a respective one of the plurality of set bits;
identify one or more rows, of the plurality of rows, that store respective set bits of the plurality of set bits at the one or more columns by performing a column-wise read of the one or more memories on each of the one or more columns, wherein the one or more rows are associated with respective bit vectors of the plurality of bit vectors;
determine, based on the respective set bits of the one or more rows, respective similarities between the respective bit vectors and the search key; and
based on determining the respective similarities between the respective bit vectors and the search key, return, to the requesting entity, one or more bit vectors of the respective bit vectors.
22 . The apparatus of claim 21 , wherein the query is indicative of an integer or a floating-point number, and wherein the circuitry is to generate the search key by:
converting the integer or floating-point number to a Hexadecimal (Hex) format;
for each of a plurality of Hex values in the Hex format, encoding the Hex value using an m-of-n constant weight encoding to generate encoded Hex values; and
concatenating the encoded Hex values to form the bit vector comprising the plurality of set bits.
23 . The apparatus of claim 22 , wherein the m-of-n constant weight encoding comprises one of a 2-of-7 encoding or a 3-of-7 encoding.
24 . The apparatus of claim 22 , wherein:
the query is indicative of a floating point number comprising a mantissa portion and an exponent portion; and
the encoded Hex values comprise a first number of encoded Hex values for the mantissa portion and a second number of encoded Hex values for the exponent portion.
25 . The apparatus of claim 24 , wherein the floating point number is one of a 32-bit floating point number or 64-bit floating point number.
26 . The apparatus of claim 22 , wherein the circuitry is to determine the respective similarities between the respective bit vectors and the search key by calculating a similarity score for a group of columns storing data corresponding to a single encoded Hex value.
27 . The apparatus of claim 21 , wherein the circuitry comprises a vector function unit (VFU), and wherein the VFU is to aggregate the respective set bits of the one or more rows for determining the respective similarities between the respective bit vectors and the search key.
28 . The apparatus of claim 21 , wherein the one or more memories comprise one or more of stochastic associative memory (SAM) media or three-dimensional cross-point memory.
29 . A computing system comprising:
a processor;
one or more memories comprising a plurality of rows and a plurality of columns of memory cells; and
circuitry coupled to the one or more memories and the processor, wherein the circuitry is to:
store, at respective rows of the one or more memories, a plurality of bit vectors;
generate, based on a query from a requesting entity, a search key in an encoded format, wherein the search key comprises a bit vector comprising a plurality of set bits;
identify one or more columns, of the plurality of columns, that are associated with a respective one of the plurality of set bits;
identify one or more rows, of the plurality of rows, that store respective set bits of the plurality of set bits at the one or more columns by performing a column-wise read of the one or more memories on each of the one or more columns, wherein the one or more rows are associated with respective bit vectors of the plurality of bit vectors;
determine, based on the respective set bits of the one or more rows, respective similarities between the respective bit vectors and the search key; and
based on determining the respective similarities between the respective bit vectors and the search key, return, to the requesting entity, one or more bit vectors of the respective bit vectors.
30 . The system of claim 29 , wherein the query is indicative of an integer or a floating-point number, and wherein the circuitry is to generate the search key by:
converting the integer or floating-point number to a Hexadecimal (Hex) format;
for each of a plurality of Hex values in the Hex format, encoding the Hex value using an m-of-n constant weight encoding to generate encoded Hex values; and
concatenating the encoded Hex values to form the bit vector comprising the plurality of set bits.
31 . The system of claim 30 , wherein the m-of-n constant weight encoding comprises one of a 2-of-7 encoding or a 3-of-7 encoding.
32 . The system of claim 30 , wherein:
the query is indicative of a floating point number comprising a mantissa portion and an exponent portion; and
the encoded Hex values comprise a first number of encoded Hex values for the mantissa portion and a second number of encoded Hex values for the exponent portion.
33 . The system of claim 30 , wherein the circuitry is to determine the respective similarities between the respective bit vectors and the search key by calculating a similarity score for a group of columns storing data corresponding to a single encoded Hex value.
34 . The system of claim 29 , wherein the circuitry comprises a vector function unit (VFU), and wherein the VFU is to aggregate the respective set bits of the one or more rows for determining the respective similarities between the respective bit vectors and the search key.
35 . The system of claim 29 , wherein the one or more memories comprise one or more of stochastic associative memory (SAM) media or three-dimensional cross-point memory.
36 . A method comprising:
generating, based on a query from a requesting entity, a search key in an encoded format for searching one or more memories, wherein the search key comprises a bit vector comprising a plurality of set bits, and wherein the one or more memories comprise a plurality of rows and a plurality of columns of memory cells to store a plurality of bit vectors;
identifying one or more columns, of the plurality of columns, that are associated with a respective one of the plurality of set bits;
identifying one or more rows, of the plurality of rows, that store respective set bits of the plurality of set bits at the one or more columns by performing a column-wise read of the one or more memories on each of the one or more columns, wherein the one or more rows are associated with respective bit vectors of the plurality of bit vectors;
determining, based on the respective set bits of the one or more rows, respective similarities between the respective bit vectors and the search key; and
based on determining the respective similarities between the respective bit vectors and the search key, returning, to the requesting entity, one or more bit vectors of the respective bit vectors.
37 . The method of claim 36 , wherein the query is indicative of an integer or a floating-point number, and wherein generating the search key comprises:
converting the integer or floating-point number to a Hexadecimal (Hex) format;
for each of a plurality of Hex values in the Hex format, encoding the Hex value using an m-of-n constant weight encoding to generate encoded Hex values; and
concatenating the encoded Hex values to form the bit vector comprising the plurality of set bits.
38 . The method of claim 37 , wherein the m-of-n constant weight encoding comprises one of a 2-of-7 encoding or a 3-of-7 encoding.
39 . The method of claim 37 , wherein:
the query is indicative of a floating point number comprising a mantissa portion and an exponent portion; and
the encoded Hex values comprise a first number of encoded Hex values for the mantissa portion and a second number of encoded Hex values for the exponent portion.
40 . The method of claim 37 , wherein determining the respective similarities between the respective bit vectors and the search key comprises calculating a similarity score for a group of columns storing data corresponding to a single encoded Hex value.