# US 2014/0195720 A1 · High-Performance Indexing For Data-Intensive Systems > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2014/0195720 A1 - Document ID: US20140195720A1 - Status: Published application - Kind: A1 - Application number: 13/737,092 - Filed: 2013-01-09 - Published: 2014-07-10 - Earliest claimed: 2013-01-09 - Assignees: Wisconsin Alumni Research Foundation - Applicants: Wisconsin Alumni Research Foundation - Inventors: Srinivasa Akella; Ashok Anand; Aaron Gember - Web page: https://patentgrep.com/patent/US20140195720A1 ## CPC - G06F 12/0246: {in block erasable memory, e.g. flash memory} - G06F 16/10: File systems; File servers - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Aspects of the present invention provide high-performance indexing for data-intensive systems in which “slicing” is used to organize indexing data on an SSD such that related entries are located together. Slicing enables combining multiple reads into a single “slice read” of related items, offering high read performance. Small in-memory indexes, such as hash tables, bloom filters or LSH tables, may be used as buffers for insert operations to resolve slow random writes on the SSD. When full, these buffers are written to the SSD. The internal architecture of the SSD may also be leveraged to achieve higher performance via parallelism. Such parallelism may occur at the channel-level, the package-level, the die-level and/or the plane-level. Consequently, memory and compute resources are freed for use by higher layer applications, and better performance may be achieved. ## Claims ### Claim 1 A method for indexing data in a storage system comprising: (a) receiving a data element for storage in a storage system at a storage address; (b) determining a slot address in an index in a first memory as a function of a key value of the data element for storage; (c) storing the data element for storage linked to the storage address as an index pair at the slot address; and (d) transferring at an interval the index pair from the first memory to an index in a second memory being a flash memory larger in capacity than the first memory to be preferentially combined with previously transferred index pairs having the same slot address. ### Claim 2 (depends on 1) The method of claim 1, further comprising: (e) receiving a key value of a data element for retrieval from the storage system; (f) determining a slot address in the index of the second flash memory as a function of a value of the data element for retrieval; (g) reading the preferentially combined index pairs having the same slot address from the second flash memory in a single read cycle; and (h) identifying the data element for retrieval and obtaining a linked storage address. ### Claim 3 (depends on 2) The method of claim 2, including multiple first memories and wherein step (d) moves the contents of common slot addresses of each of the first memories into a corresponding slot memory of the second memory. ### Claim 4 (depends on 3) The method of claim 3 wherein the common slot addresses of the first memories are less than all slot addresses of the first memories and wherein an interval occurs when the common slot addresses of the all the first memories have been filled. ### Claim 5 (depends on 4) The method of claim 4 wherein the transferred index pairs from the first memories are combined to be concentrated in a page of the second memory, wherein a page represents a unit of data readout of the second memory. ### Claim 6 (depends on 2) The method of claim 2, further comprising reordering a plurality of read requests to allow a plurality of read cycles to occur at the same time within the second flash memory. ### Claim 7 (depends on 6) The method of claim 6, wherein a plurality of read cycles occurs on channels leading to different flash memory packages within the second flash memory at the same time. ### Claim 8 (depends on 1) The method of claim 1, wherein an interval occurs after a predetermined number of index pairs have been stored at slot addresses. ### Claim 9 (depends on 1) The method of claim 1, further comprising a plurality of indexes in the first memory, wherein determining the same slot address based on different data elements results in storing the different data elements linked to their respective storage addresses as index pairs in different indexes using the same slot address. ### Claim 10 (depends on 1) The method of claim 1, wherein each index comprises a hash table. ### Claim 11 (depends on 10) The method of claim 10, wherein each hash table is a locality sensitive hash table. ### Claim 12 (depends on 1) The method of claim 1, further comprising: (e) determining if a key value for another data element may be in the storage system by using a bloom filter in the first memory; and (f) transferring at an interval the bloom filter from the first memory to a bloom filter in the second memory to be preferentially combined with previously transferred bloom filters using the same hash function. ### Claim 13 (depends on 1) The method of claim 1, wherein the first memory is DRAM. ### Claim 14 A method for indexing data in a storage system using flash memory comprising: (a) determining the mapping between a first logical page and a first plurality of memories coupled to a first channel within a flash memory; (b) determining the mapping between a second logical page and a second plurality of memories coupled to a second channel within the flash memory; and (c) reordering a plurality of read requests to the flash memory to allow a plurality of read cycles to occur at the same time within the flash memory. ### Claim 15 (depends on 14) The method of claim 14, wherein the plurality of read cycles occurs on channels leading to different flash memory packages within the flash memory at the same time. ### Claim 16 (depends on 14) The method of claim 14, further comprising: (d) receiving a data element for storage in a storage system at a storage address; (e) determining a slot address in an index in a first memory smaller in capacity than the flash memory as a function of a value of the data element for storage; (f) storing the data element for storage linked to the storage address as an index pair at the slot address; and (g) transferring at an interval the index pair from the first memory to an index in the flash memory to be preferentially combined with previously transferred index pairs having the same slot address. ### Claim 17 (depends on 16) The method of claim 16, wherein an interval occurs after a predetermined number of index pairs have been stored at slot addresses. ### Claim 18 (depends on 16) The method of claim 16, further comprising a plurality of indexes in the first memory, wherein determining the same slot address based on different data elements results in storing the different data elements linked to their respective storage addresses as index pairs in different indexes using the same slot address. ### Claim 19 (depends on 16) The method of claim 16, wherein each index is a random hash-based index. ### Claim 20 (depends on 16) The method of claim 16, further comprising: (h) receiving a data element for retrieval from the storage system; (i) determining a slot address in the index of the flash memory as a function of a value of the data element for retrieval; (j) reading the preferentially combined index pairs having the same slot address from the flash memory in a single read cycle; and (k) identifying the data element for retrieval and obtaining a linked storage address.