Data search using bloom filters and NAND based content addressable memory
A NAND Flash based content addressable memory (CAM) is used for a key-value addressed storage drive. A host writes a key-value pair to the drive, where the drive writes the keys along bit lines of a CAM NAND portion of the drive and stores the value in the drive. The drive then maintains a table linking the keys to location of the value. In a read process, the host provides a key to drive, which then broadcasts down the word lines of blocks storing the keys. Based on any matching bit lines, the tables can then be used to retrieve and supply the corresponding data to the host. This arrangement can be applied to data search operations using bloom filters stored along bit lines of search matrix, where the search matrix can extend across large numbers of arrays. In the example of an internet search, the bloom filters are formed from key words associated with a website are stored along bit lines of the matrix and corresponding URLs are stored in primary storage. In response to search word based query, any matching URLs are returned.
1. A method of operating a non-volatile memory system, comprising:
storing a plurality of bloom filters, each generated from a corresponding set of search elements, on a search matrix formed of one or more non-volatile memory arrays of the memory system, wherein the memory arrays are of a NAND type architecture and the bloom filters are stored therein oriented along the arrays' bit lines;
for each of the bloom filters, storing a corresponding data element in a first non-volatile memory section of the memory system; and
maintaining by the control circuitry of the memory system of a correspondence between the location of the bit lines of the search matrix upon which the bloom filters are stored and the location at which the corresponding data elements are store in the first non-volatile memory section.
2. The method of claim 1 , wherein the data elements are sets of data with which the corresponding search terms are associated.
3. The method of claim 1 , wherein the data elements derived from sets of data with which the corresponding search terms are associated.
4. The method of claim 1 , wherein the data elements are a pointer from which the sets of data with which the corresponding search terms are associated can be located.
5. The method of claim 4 , wherein the data elements are URLs.
6. The method of claim 5 , wherein the corresponding search terms are key words associated with web page of the corresponding URL.
7. The method of claim 1 , further comprising:
prior to storing the bloom filters and the corresponding data elements, receiving the bloom filters and the corresponding data elements at the memory system; and
prior to storing the received bloom filters, in circuitry on the memory system transposing the bloom filters from a horizontal to vertical orientation.
8. The method of claim 1 , further comprising:
prior to storing the bloom filters and the corresponding data elements, receiving the search elements and the corresponding data elements at the memory system; and
prior to storing the bloom filters, in circuitry on the memory system generating the bloom filters from the corresponding search elements.
9. The method of claim 1 , further comprising:
prior to storing the bloom filters and the corresponding data elements, receiving hash values generated from the search elements and the corresponding data elements at the memory system; and
prior to storing the bloom filters, in circuitry on the memory system generating the bloom filters from the hash values generated from the corresponding search elements.
10. The method of claim 1 , wherein the search elements from which a bloom filter is generated include elements extracted from a data set associated with the corresponding data element.
11. The method of claim 1 , wherein the search elements from which a bloom filter is generated include descriptive data for a data set associated with the corresponding data element.
12. The method of claim 1 , wherein the control circuitry maintains the correspond as a mapping.
13. The method of claim 12 , wherein the maintaining of a correspondence includes maintaining a copy of the mapping as meta-data in non-volatile memory of the memory system.
14. The method of claim 1 , wherein the control circuitry maintains the correspond through a formula.
15. The method of claim 1 , wherein the memory arrays are flash memory arrays having a block structure and the individual bloom filters are stored spanning multiple blocks.
16. The method of claim 1 , wherein the search matrix is formed of in excess of a thousand arrays.
17. The method of claim 1 , further comprising:
subsequently receiving a query based on one or more search elements;
biasing the arrays of the search matrix according to a query bloom filter generated from the search elements on which the query is based;
determining bloom filters stored in the search matrix that provide positive matches for query bloom filter; and
providing the corresponding data elements for the bloom filter that provide positive matches.
18. The method of claim 17 , wherein the query includes the query bloom filter.
19. The method of claim 17 , wherein the query includes the search element upon which the query is based, the method further comprising:
in circuitry on the memory system, generating the query bloom filter from the search elements upon which the query is based.
20. The method of claim 17 , wherein the query includes hashes of the search elements upon which the query is based, the method further comprising:
in circuitry on the memory system, generating the query bloom filter from the hashes of the search elements upon which the query is based.
21. The method of claim 17 , wherein the memory arrays are flash memory arrays having a block structure and the individual bloom filters are stored spanning multiple blocks and wherein said biasing and determining are performed for multiple blocks in parallel.
22. The method of claim 17 , wherein said biasing and determining are performed for multiple arrays in parallel.