DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
CLAIM INTERPRETATION
Claims in this application are not interpreted under 35 U.S.C. §112(f).
Claim Objections
Claim 3 is objected to because of the following informalities:
Claim 3 recites, “of next data structure information”, which as best understood by the Examiner in light of the specification, should be amended to recite “of a next data structure information”.
Claim 11 recites, “receiving an invalidation command or a deletion command on at least one of the map data”, which as best understood by the Examiner in light of the specification, should be amended to recite “receiving an invalidation command or a deletion command [[on]]for at least one of the map data”.
Appropriate correction is required.
Claim Rejections - 35 USC § 112(b)
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 1-13 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor, or for pre-AIA the applicant regards as the invention.
Regarding claim 1:
Claim 1 recites “a controller configured to load a map data representing a mapping relationship between a mapping relationship between the physical address and a logical address”, which requires that a logical address is mapped to “the physical address”. However, the claim previously introduces “a plurality of storage areas, each of the plurality of storage areas indicated by a physical address”, which appears to require a plurality of physical addresses each of which are mapped to one of the corresponding storage areas (or else illogically requires that a single physical address corresponds to all of the storage areas). Therefore, it is unclear which of the plurality of physical addresses is indicated by the later recitation of “the physical address”. Accordingly, the scope of the claim cannot be determined and the claim is indefinite.
The Examiner suggests amending the claims to recite, “a memory including a plurality of storage areas, each of the plurality of storage areas indicated by a respective physical address; and a controller configured to load a map data representing a mapping relationship between [[the]] a physical address indicating a storage area among the plurality of storage areas and a logical address”.
Claim 1 also recites, “to search for the map data using the data structure information, which includes a validity field that has a value indicating whether the map data is valid”, which is subject to multiple distinct interpretations that are not resolved by the specification. For example, the limitation may be read as 1) indicating that the data structure contains the validity field or 2) indicating that the map data contains the validity field. For the purposes of examining the claim, the examiner will interpret the limitation as requiring the data structure to include the validity field.
Regarding claim 5:
Claim 5 recites, “at least one of the data structure information”, which appears to presuppose the existence of multiple data structure information. However, the claim only ever previously introduces a single data structure information. Accordingly, it is unclear which data structure information the claim is referring to as it appears to imply the existence of a plurality of data structure information when only one is previously recited.
Regarding claim 6:
Claim 6 recites, “the data structure information” after claim 1 introduces “data structure information” and claim 6 introduces “data structure information of the first child node”. Accordingly, the antecedent basis of the limitation is unclear and the scope of the claim cannot be determined and the claim is indefinite. The Examiner suggests amending the claim to introduce “first” data structure information and “second” data structure information or something similar to differentiate the multiple data structure information.
Regarding claim 7:
Claim 7 suffers from a similar defect to claim 6 for reciting “the data structure information” after introducing different data structure information which could be referred to by the limitation and making the antecedent basis of the limitation unclear. Claim 7 should be amended similarly to claim 6.
Regarding claim 11:
Claim 11 recites, “on at least one of the map data”, which appears to presuppose the existence of multiple map data. However, the claim only ever previously introduces a single map data. Accordingly, it is unclear which map data the claim is referring to as it appears to imply the existence of a plurality of map data when only one is previously recited.
Regarding claims 2-13:
Claims 2-13 are rejected for failing to cure the deficiencies of a base claim from which they depend.
Claim Rejections - 35 USC § 112(a)
The following is a quotation of the first paragraph of 35 U.S.C. 112(a):
(a) IN GENERAL.—The specification shall contain a written description of the invention, and of the manner and process of making and using it, in such full, clear, concise, and exact terms as to enable any person skilled in the art to which it pertains, or with which it is most nearly connected, to make and use the same, and shall set forth the best mode contemplated by the inventor or joint inventor of carrying out the invention.
The following is a quotation of the first paragraph of pre-AIA 35 U.S.C. 112:
The specification shall contain a written description of the invention, and of the manner and process of making and using it, in such full, clear, concise, and exact terms as to enable any person skilled in the art to which it pertains, or with which it is most nearly connected, to make and use the same, and shall set forth the best mode contemplated by the inventor of carrying out his invention.
Claims 13 and 20 are rejected under 35 U.S.C. 112(a) or 35 U.S.C. 112 (pre-AIA ), first paragraph, as failing to comply with the written description requirement. The claim(s) contains subject matter which was not described in the specification in such a way as to reasonably convey to one skilled in the relevant art that the inventor or a joint inventor, or for applications subject to pre-AIA 35 U.S.C. 112, the inventor(s), at the time the application was filed, had possession of the claimed invention.
Regarding claim 13:
Claim 13 recites, “searching… in a binary search mode using the data structure information, and… searching… in a linear search mode using the data structure information”. However, the specification appears to indicate that a linear search is only performed on the mapping table and not on the data structure information, which may be a binary tree [0107] [0113] [0133-0135] [see Fig. 7]. “An original claim may lack written description support when (1) the claim defines the invention in functional language specifying a desired result but the disclosure fails to sufficiently identify how the function is performed or the result is achieved”. [MPEP 2163.03(V)]. In this case, the claim defines the invention in functional language (a search is performed on data structure information using a linear method), however, there is no description of how a linear search method may be performed on data structure information. Instead, the specification only appears to contemplate a linear search being performed on a table/L2P map, which is contrasted with the binary search of binary tree information of data structure information, which therefore does not provide a description of how a linear search is performed on data structure information. Therefore, the claim lacks written description support. The Examiner suggests amending the claim to recite the linear search mode being used on a mapping table consistently with the specification.
Regarding claim 20:
Claim 20 recites limitations analogous to those rejected in claim 13 and is therefore rejected according to a similar analysis.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to a judicial exception (i.e. a law of nature, a natural phenomenon, or an abstract idea) without significantly more.
As an initial matter, under the Alice Framework Step 1 analysis, claims XXX fall within the four statutory categories of patentable subject matter: a process, machine, manufacture, and composition of matter as claims 1-20 claim a machine or article of manufacture.
Regarding claim 1 and analogous claims 14 and 18-19:
Under the Alice Framework Step 2A prong 1:
The claim recites a mental process type abstract idea by reciting “to search for the map data using the data structure information”, for which the broadest reasonably interpretation includes a person mentally searching through a list, array, red-black tree, or any other organizational structure for a needed logical-to-physical address mapping. The Examiner notes, “The courts consider a mental process (thinking) that "can be performed in the human mind, or by a human using a pen and paper" to be an abstract idea”. [MPEP 2106.04(a)(2)(III) ¶1], and any of the disclosed data structures could be sketched out on pen and paper and then a search through the data structure conducted mentally by a human with the aid of the pen and paper. Therefore the claims recite an abstract idea.
Under the Alice Framework Step 2A prong 2, the claim is evaluated for additional elements that integrate the judicial exception into a practical application.
The claim recites the additional elements of:
“A storage device comprising: a memory including a plurality of storage areas, each of the plurality of storage areas indicated by a physical address; and a controller”. However, these elements are recited at a high level of generality (i.e. memory devices that store data at addresses and a controller for that memory device) such that they amount to no more than mere instructions to apply the exception using generic computer components [MPEP §2106.05(f)]. Accordingly, these additional elements do not integrate the abstract idea into a practical application because they do not impose any meaningful limits on practicing the abstract idea.
“load a map data representing a mapping relationship between the physical address and a logical address provided by a host device and data structure information corresponding to the map data into a sub memory, [wherein the data structure information] includes a validity field that has a value indicating whether the map data is valid”. However, this limitation recites insignificant extra-solution activity as it amounts to necessary data gathering and data output for performing the judicial exception as it is analogous to other limitations found to be mere data gathering by the courts, such as: testing a system for a response, the response being used to determine system malfunction, In re Meyers, 688 F.2d 789, 794; 215 USPQ 193, 196-97 (CCPA 1982); obtaining information about transactions using the Internet to verify credit card transactions, CyberSource v. Retail Decisions, Inc., 654 F.3d 1366, 1375, 99 USPQ2d 1690, 1694 (Fed. Cir. 2011); and consulting and updating an activity log, Ultramercial, 772 F.3d at 715, 112 USPQ2d at 1754 and therefore only amounts to mere data gathering and does not integrate the judicial exception into a practical application [MPEP 2106.05(g)].
Under the Alice Framework Step 2B, for at least the reasons cited with respect to the Step 2A prong 2, the claim considered as a whole does not amount to significantly more than the abstract idea. As a whole, the claim merely recites the abstract idea with mere instructions to apply it by generic computer components (memory device with addresses and a controller configured to control it) to use computers as tools to implement the abstract idea. Mere instructions to apply an exception using generic computer components cannot provide an inventive concept. [See MPEP § 2106.05(f)]. Furthermore, the additional step of loading the data structure information and mapping information is insignificant extra solution activity recited at a high level of generality and amounts to activity recognized by the courts as well understood, routine, and conventional. For example, the limitation is analogous to: electronic recordkeeping, Alice Corp. Pty. Ltd. v. CLS Bank Int'l, 573 U.S. 208, 225, 110 USPQ2d 1984 (2014) (creating and maintaining "shadow accounts"); Ultramercial, 772 F.3d at 716, 112 USPQ2d at 1755 (updating an activity log) or storing and retrieving information in memory, Versata Dev. Group, Inc. v. SAP Am., Inc., 793 F.3d 1306, 1334, 115 USPQ2d 1681, 1701 (Fed. Cir. 2015); OIP Techs., 788 F.3d at 1363, 115 USPQ2d at 1092-93. Accordingly, including the well understood, routine, and conventional activity recited at a high level of generality with the abstract idea does not provide an inventive concept or significantly more than the abstract idea by itself [MPEP 2106.05(d)]. Therefore, the claim elements considered individually, in combination, and as a whole, do not provide significantly more than the abstract idea. For these reasons, claim 1 is not patent eligible.
Regarding claims 2-7 and 15-17:
Claims 2-7 and 15 recite further limitations that define the data structure that is loaded, which may influence how the data structure is searched (i.e., modify the performance of the abstract idea). However, the modifications to the data structure do not prevent the data structure from being able to be searched mentally with the aid of pen and paper. Furthermore, at most, the limitations may be interpreted as necessary data gathering and outputting through the selection of a particular source or type of data to be manipulated as they are analogous to other limitations found to be mere data gathering by the courts, such as: limiting a database index to XML tags, Intellectual Ventures I LLC v. Erie Indem. Co., 850 F.3d at 1328-29, 121 USPQ2d at 1937; or selecting information, based on types of information and availability of information in a power-grid environment, for collection, analysis and display, Electric Power Group, LLC v. Alstom S.A., 830 F.3d 1350, 1354-55, 119 USPQ2d 1739, 1742 (Fed. Cir. 2016) as they recite limitations that restrict the type of data structure to a red-black tree or other binary search tree. Accordingly, the claims are rejected according to a similar analysis as that performed above for claim 1.
Regarding claim 8:
Claim 8 recites “when performing a search using the data structure information, sequentially stores addresses of the sub memory indicating the data structure information in a… LIFO (last input first out) stack structure)”, which is a further modification to the abstract idea and does not prevent the abstract idea from being a process that may be performed mentally (with the aid of pen and paper) as the use of a stack structure to sequentially store addresses of visited nodes may be performed when performing a depth first search of a tree data structure to keep track of the progress of the search. Claim 8 also recites storing the sequential addresses in the LIFO stack structure in a data buffer .However, this limitation only recites an additional limitation that may be considered as insignificant extra-solution activity such as necessary data gathering and outputting for performing the abstract idea, which is analogous to other limitations found to be mere data gathering by the courts, such as testing a system for a response, the response being used to determine system malfunction, In re Meyers, 688 F.2d 789, 794; 215 USPQ 193, 196-97 (CCPA 1982); obtaining information about transactions using the Internet to verify credit card transactions, CyberSource v. Retail Decisions, Inc., 654 F.3d 1366, 1375, 99 USPQ2d 1690, 1694 (Fed. Cir. 2011); and consulting and updating an activity log, Ultramercial, 772 F.3d at 715, 112 USPQ2d at 1754 and therefore only amounts to mere data gathering and does not integrate the judicial exception into a practical application [MPEP 2106.05(g)]. Therefore, claim 8 is rejected according to a similar analysis as that performed for claim 1.
Regarding claims 9-12:
Claims 9-12 recite additional limitations that further recite insignificant extra-solution activity as necessary data gathering for performing the abstract idea and are analyzed analogously to other limitations found to be mere data gathering in claims 1 and 8.
Regarding claims 13 and 20:
Claims 13 and 20 only recite modifications to the performance of the abstract idea in a way that does not prevent it from being performed mentally. Accordingly, the claims are rejected according to a similar analysis as that performed for claim 1.
Claim Rejections – 35 USC § 102
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
(a)(2) the claimed invention was described in a patent issued under section 151, or in an application for patent published or deemed published under section 122(b), in which the patent or application, as the case may be, names another inventor and was effectively filed before the effective filing date of the claimed invention.
Claims 1-4, 9, 14-16 and 18-19 are rejected under 35 U.S.C. 102(a)(1) and 102(a)(2) as being anticipated by US Patent Application Publication US 2024/0370365 A1 (Palmer).
Regarding claim 1 and analogous claims 14 and 18-19:
Palmer discloses:
A storage device comprising: a memory including a plurality of storage areas, each of the plurality of storage areas indicated by a physical address (by disclosing a memory system (110) including memory devices (120-1 – 120-N), which include memory arrays (130-1 – 130-N), which include a die including a plurality of planes, which include a plurality of blocks, which include a plurality of pages, which are addressed with a physical address [Figs. 1-3] [0017] [0021] [0041-0049])
and a controller configured to (by disclosing the memory system controller (115) configured to manage the memory devices (120-1 – 120-N) and the mapping of addresses between the host’s LBAs and the memory devices’ PBAs [0025] [0034-0036]).
load a map data representing a mapping relationship between the physical address and a logical address provided by a host device and (by disclosing that the volatile memory (135) may be used to load a logical to physical (L2P) table from non-volatile memory [0066]. The volatile memory may be included in the memory system controller (115) [0031])
[load] data structure information corresponding to the map data into a sub memory (by disclosing that an exception list may be loaded into the volatile memory (135), where the exception list is a data structure that is used to map the non-sequential address mappings of the L2P table [0024] [0058-0061] [0066]. The data structure may include a plurality of nodes that are stored in the volatile memory at volatile memory addresses (i.e., the volatile memory used to store each node is interpreted as a sub memory) (first area), and the exception list is also stored at different addresses of the volatile memory (second area) as indicated by the exception list memory location stored within the node [Fig. 5] [0061])
and to search for the map data using the data structure information (by disclosing that the data structure may be used to perform a lookup of a logical address for a corresponding physical address (map data) [0024] [0037-0039] [0058] [0062] [0073]).
which includes a validity field that has a value indicating whether the map data is valid (by disclosing the validity bitmap as seen in [Fig. 5], (i.e., which includes a plurality of validity fields, such as 16). The validity bitmap indicates whether the map data stored in the node of the data structure includes a valid translation for a corresponding logical address [0060]).
Regarding claim 2 and analogous claim 15:
The storage device according to claim 1 is anticipated by Palmer.
Palmer further discloses:
wherein the data structure information includes a type field that has a value indicating a type of the data structure information (by disclosing the color field (type) that has a value indicating a color (type) of the node of the data structure (500) [Fig. 5] [0059])
a first pointer field that has a first pointer value associated with the data structure information (by disclosing the exception list memory location, parent node, left child node, and right child node fields, which store pointers (at least a first and second) which point to other nodes of the data structure or payload data of the list of addresses in the exception list stored in the volatile memory for the corresponding node [Fig. 5] [0024] [0063]).
a second pointer field that has a second pointer value associated with the data structure information (by disclosing the exception list memory location, parent node, left child node, and right child node fields, which store pointers (at least a first and second) which point to other nodes of the data structure or payload data of the list of addresses in the exception list stored in the volatile memory for the corresponding node [Fig. 5] [0024] [0063]).
Regarding claim 3 and analogous claim 16:
The storage device according to claim 2 is anticipated by Palmer.
Palmer further discloses:
wherein the first pointer value indicates an address of a sub memory of the data structure information including the first pointer field (by disclosing that the node (data structure information) may include a pointer to the exception list memory location, which is an array in the volatile memory storing the physical addresses corresponding to the logical addresses mapped by the node including the exception list memory location field [Fig. 5] [0024] [0038-0039] [0061-0062]).
and the second pointer value indicates an address of a sub memory of next data structure information (by disclosing the pointers to the parent node, left childe node, and right child nodes (address of a sub memory of next data structure information) [Fig. 5] [0024] [0063])
Regarding claim 4:
The storage device according to claim 2 is anticipated by Palmer.
Palmer further discloses:
wherein the first pointer value indicates an address of a sub memory of a first child node of the data structure information including the first pointer field (by disclosing the pointer to the left child node (address of a sub memory of a first child node) [Fig. 5] [0024] [0063]).
and the second pointer value indicates an address of a sub memory of a second child node of the data structure information including the second pointer field (by disclosing the pointer to the left child node (address of a sub memory of a first child node) [Fig. 5] [0024] [0063]).
Regarding claim 9:
The storage device according to claim 1 is anticipated by Palmer.
Palmer further discloses:
wherein the sub memory includes a first data area (by disclosing the pointer to the nodes indicates where in the volatile memory that the node is stored (first data area) [Fig. 5] [0061] [0066])
and a second data area (by disclosing the pointer to the memory location that stores the exception list in the volatile memory [Fig. 5] [0061] [0066])
the data structure information is stored in the first data area, and the map data is stored in the second data area (by disclosing the pointer to the nodes indicates where in the volatile memory that the node is stored (first data area) and the pointer to the memory location that stores the exception list in the volatile memory [Fig. 5] [0061]).
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 5-7 and 10 are rejected under 35 U.S.C. 103 as being unpatentable over US Patent Application Publication US 2024/0370365 A1 (Palmer) in view of the webpage by Dale Alleshouse, “Red Black Trees”, as preserved by the Internet Archive on 16 April 2024, from the website “Hideous Humpback Freak”, pgs. 1-16 (Alleshouse).
Regarding claim 5:
The storage device according to claim 4 is anticipated by Palmer.
Palmer discloses terminating leaf nodes 4, 5, 6, 8 and 9 [see Fig. 5].
Palmer does not explicitly disclose, but Alleshouse teaches:
wherein the first pointer value and the second pointer value included in at least one of the data structure information are the same (by teaching that typically, red-black trees terminate with a NULL pointer, but replacing them with a black node representing a NULL value simplifies the logic. Furthermore, an added optimization is to create a single global NULL node to avoid re-allocating every requisite NULL node. Regardless, the implementation involves every terminating leaf node to include either NULL pointers for the left and right child nodes or the left and right child nodes each pointing to the same global NULL node [pg. 10, §Implementation Details, ¶¶1-2 and the included Figure]. Also see the Pseudocode on pg. 9 where a new instantiated node includes left and right child nodes pointing to the NULL_NODE.
It would have been obvious for one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the terminating leaf nodes 4, 5, 6, 8 and 9 as taught by Palmer to include left and right child pointers to a global black NULL node as taught by Alleshouse.
One of ordinary skill in the art would have been motivated to make this modification because terminating leaf nodes with a black node representing a NULL value simplifies the implementation logic of a red-black tree, and a further optimization is to create a single global NULL node to avoid re-allocating every requisite NULL node as taught by Alleshouse in [pg. 10, §Implementation Details, ¶¶1-2 and the included Figure].
Regarding claim 6:
The storage device according to claim 4 is anticipated by Palmer.
Palmer discloses that the tree may be a red-black tree [0059] [Fig. 5], and furthermore, that node 7 may be a red node [Fig. 5] [0059]).
Palmer does not explicitly disclose, but Alleshouse teaches:
wherein when the type field included in the data structure information has a first value (by teaching that a node may be designated as red (first value) or black (second value) [pg. 2, §Red-Black Invariants, ¶1 and list #1]).
type fields included in data structure information of the first child node indicated by the first pointer value of the data structure information and the second child node indicated by the second pointer value have a second value (by teaching that a red node must have black (second value) children and parents, such that a red node’s left and right pointers (first pointer value and second pointer value) will point to black child nodes [pg. 2, §Red-Black Invariants, ¶1 and list #3])
It would have been obvious for one of ordinary skill in the art before the effective filing date of the claimed invention to have modified node 7 (the red node) and all other red nodes in the red-black tree data structure taught by Palmer to point to left and right children that are block nodes as taught by Alleshouse.
One of ordinary skill in the art would have been motivated to make this modification because it is an invariant of the red-black tree that allows the tree to remain approximately balanced and to approximately minimize the height of the tree as taught by Alleshouse in [pg. 1, ¶1-3] [pg. 2, §Red-Black Invariants], which allows for considerably more efficient insert and delete operations although slightly decreasing the efficiency of search operations [pg. 4, ¶1].
Regarding claim 7:
The storage device according to claim 4 is anticipated by Palmer.
Palmer discloses that the tree may be a red-black tree [0059] [Fig. 5], and furthermore, that node 7 may be a red node [Fig. 5] [0059]).
wherein when the type field included in the data structure information has a first value (by teaching that a node may be designated as red (first value) or black (second value) [pg. 2, §Red-Black Invariants, ¶1 and list #1]).
type fields included in data structure information of a parent node of the data structure information and a child node of the data structure information have a second value (by teaching that a red node must have black (second value) children and parents, such that a red node’s left and right pointers (first pointer value and second pointer value) will point to black child nodes [pg. 2, §Red-Black Invariants, ¶1 and list #3])
It would have been obvious for one of ordinary skill in the art before the effective filing date of the claimed invention to have modified node 7 (the red node) and all other red nodes in the red-black tree data structure taught by Palmer to point to left and right children that are block nodes as taught by Alleshouse.
One of ordinary skill in the art would have been motivated to make this modification because it is an invariant of the red-black tree that allows the tree to remain approximately balanced and to approximately minimize the height of the tree as taught by Alleshouse in [pg. 1, ¶1-3] [pg. 2, §Red-Black Invariants], which allows for considerably more efficient insert and delete operations although slightly decreasing the efficiency of search operations [pg. 4, ¶1].
Regarding claim 10:
The storage device according to claim 9 is anticipated by Palmer.
Palmer discloses that the tree performs insertions/deletions [0059].
Palmer does not explicitly disclose, but Alleshouse teaches,
wherein the controller updates at least a part of the data structure information by accessing the first data area (by teaching that when a node is inserted, the nodes needs to be updated to restore the tree so that none of the properties of a red-black tree are violated [pg. 2, last ¶]. This involves a series of recoloring and rotation operations, that therefore change the type of the nodes (red/black) as well as the pointers to the parents/children [pg. 4, last ¶] [pgs. 6-7] [see Example on pgs. 8-9]).
and the value stored by the node (i.e., the pointer to the map data as taught by Palmer and the underlying map data itself), corresponding to the updated data structure information and stored in the second data area, is maintained unchanged (by teaching that restoring the red-black invariant properties of the tree only involves re-coloring and rotation operations and does not change the values of the underlying nodes themselves [see pg. 2, last ¶] [pg. 4, last ¶] [pgs. 6-7] and the Example on [pgs. 8-9]. Also see [Algorithm 1 for recoloring and rotating that does not change the values of the nodes [pgs. 9-10]).
It would have been obvious for one of ordinary skill in the art before the effective filing date of the claimed invention to have modified red-black tree after an insertion as taught by Palmer to include implementing the pseudocode that recolors and rotates the nodes (without modifying the node’s values (i.e., pointer to mapping data and the underlying mapping data stored therein for other nodes not updated/inserted as taught by Palmer)) as taught by Alleshouse.
One of ordinary skill in the art would have been motivated to make this modification because it allows the red-black tree to remain a red-black tree and restore violations so that it meets the requirements of the red-black tree invariant and remains approximately balanced and approximately the same depth [pg. 1, ¶1-3] [pg. 2, §Red-Black Invariants], which allows for considerably more efficient insert and delete operations although slightly decreasing the efficiency of search operations [pg. 4, ¶1].
Claim 8 is rejected under 35 U.S.C. 103 as being unpatentable Palmer in view of the lecture notes by Tom Anastasio, titled “The Binary Tree ADT” from the Fall 1997 CSMC-202 class at University of Maryland, Baltimore County, pgs. 1-5 (Anastasio) as motivated by the Wikipedia page titled, “Depth-first search” from 31 January 2025, the old revision from 31 January 2025, pgs. 1-8.
Regarding claim 8:
The storage device according to claim 1 is anticipated by Palmer.
Palmer further discloses that the data structure storing the exception list of the L2P mapping table may be a tree [0065], which may be a red-black tree, but may also be other forms of search trees or binary trees [0073]).
Palmer does not explicitly disclose, but Anastasio teaches:
wherein the controller, when performing a search using the data structure information, sequentially stores addresses of the sub memory indicating the data structure information in a buffer memory, and the buffer memory has a LIFO (last input first out) stack structure (by teaching that to implement a search of a tree data structure, either a depth-first search or a breadth-first search may be performed [pg. 3, §Tree Search]. As seen in the pseudocode, the data type of a tree is a pointer to the data structure including the data value, and the left and right children [pg. 1, §Implementation of Binary Trees]. In the depth first search, a stack is created (which is a LIFO, as items are pushed and popped from the top of the stack (last-in-first-out (LIFO)). The stack is created in memory (buffer memory) [pgs. 3-4, §Depth-First Search]. The nodes are sequentially pushed onto the stack and then popped in a backtracking order in order to traverse the tree until the searched for item is either found or it is determined that the tree does not contain the requested item once the stack is empty [pgs. 3-4, §Depth-First Search].
It would have been obvious for one of ordinary skill in the art before the effective filing date of the claimed invention to have modified controller performing the search of the tree data structure for finding the LBA in the exception table of the L2P as taught by Palmer to include memory (buffer) for the depth first search of the tree data structure by using a stack (LIFO) of pointers to keep track of which nodes are yet to be examined as taught by Anastasio.
One of ordinary skill in the art would have been motivated to make this modification because the space complexity (i.e., memory requirements) of performing a depth first search is only proportional to the depth of a tree, and as a result is much smaller than the same space needed for searching to the same depth using a breadth-first search as taught by Depth_first_search in [pg. 2, ¶0].
Claim 11 is rejected under 35 U.S.C. 103 as being unpatentable over Palmer in view of US Patent Application Publication US 2014/0047210 A1 (Cohen).
Regarding claim 11:
The storage device according to claim 1 is anticipated by Palmer.
Palmer further discloses:
changes the value of the validity field from a first value to a second value (by teaching that a validity bitmap may indicate whether there is a valid translation associated with a corresponding LBA included within the exception list. For example, a bit value of “1” indicates a valid translation exists and a bit value of “0” indicates that no valid translation exists within the node [0078] [0080]. Updates may be performed directly to this compressed version of the L2P table in the data structure [0083])
Palmer does not explicitly disclose, but Cohen teaches:
wherein the controller, when receiving an invalidation command or a deletion command on at least one of the map data, changes the value of the validity field from a first value to a second value (by teaching that a controller may receive a trim or unmap command (invalidation) indicating that blocks of saved data are no longer needed and are therefore invalid [0028-0032]. Accordingly, during a garbage collection process, the storage device no longer needs to copy this data forward in the garbage collection process, which may improve performance of the storage device and free space to be made available to store new data [0008]. To indicate that the data is no longer valid, an indication may be stored in a LBA to PBA translation entry that encodes whether the corresponding entry is valid or invalid [0032]).
It would have been obvious for one of ordinary skill in the art before the effective filing date of the claimed invention to have modified valid bitmap as taught by Palmer to include changing the indication to indicate the translation is no longer valid when a trim or unmap command is received as taught by Cohen.
One of ordinary skill in the art would have been motivated to make this modification because during a garbage collection process, the storage device no longer needs to copy the data now marked as invalid forward in the garbage collection process, which may improve performance of the storage device and free space to be made available to store new data as taught by Cohen in [0008].
Claim 12 is rejected under 35 U.S.C. 103 as being unpatentable over Palmer in view of US Patent Application Publication US 2020/0218465 A1 (Klein).
Regarding claim 12:
The storage device according to claim 11 is made obvious by Palmer in view of Cohen.
Palmer in view of Cohen does not explicitly disclose, but Klein teaches:
wherein the controller updates the data structure information during a preset period (by teaching that the logical to physical entries for the invalidated data may be removed after the block containing the invalid data is erased (during a preset period (i.e., one that begins after the block containing the invalid data is erased [0035]).
and the data structure information in which the value of the validity field is the second value according to the update and the map data corresponding to the data structure information are removed (by teaching that the invalid mappings may be removed from a logical-to-physical table after the block containing the invalid data is erased [0035]. In this way, ephemeral data (data marked invalid in the mapping table, but which still exists in the storage device that is not yet deleted) may be deleted upon the reception of a selective erasure operation [0014] [0024] [0031]. In order to keep track of the invalid mappings, the invalid mappings are maintained in the L2P mapping table, but are marked as invalid, while new mappings are entered into the table corresponding to the new updated data with an indication that the mapping is valid [0024]).
It would have been obvious for one of ordinary skill in the art before the effective filing date of the claimed invention to have modified removal of the mapping entries marked as invalid from the compressed and uncompressed mapping tables as taught by Palmer to include removing the mapping entries marked as invalid only once the data corresponding to the invalid mapping entry was actually erased the physical blocks which were marked as invalid mappings in the mapping table once selective erasure request has been received and performed.
One of ordinary skill in the art would have been motivated to make this modification because data associated with invalidated pages may still remain in the memory device and therefore be accessed by unauthorized users causing privacy and security concerns, and so keeping track of the mappings to invalidated data so that it can be erased with a selective erasure operation before being removed may increase security and privacy as taught by Klein in [0006].
Claims 13 and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Palmer in view of US Patent Application Publication US 2018/0239547 A1 (Inbar).
Regarding claim 13 and analogous claim 20:
The storage device according to claim 1 is anticipated by Palmer.
Palmer further discloses:
wherein the controller performs, when searching for single map data, a search in a binary search mode using the data structure information (by disclosing that when a physical address lookup is performed for an LBA in the compressed portion of the L2P map and is a non-sequential physical address (single map data) (735 – No), the search is performed with the balanced binary search tree data structure (745), such as the red-black tree (binary search mode) [0037] [0039] [0062] [0073] [0080] [0107] [Fig. 7]).
and performs, when searching for map data included in a range of the map data, a search using the data structure information (by disclosing that when the LBA is determined to not be included within the compressed version (in a range of the map data), a search is performed in the uncompressed L2P table (730) (the data structure information) [Fig .7] [0088]).
Palmer does not explicitly disclose, but Inbar teaches,
searching the L2P table in a linear search mode (by teaching that instead of storing the entire L2P table as an unsorted list, which would require a linear-time search in order to search for a range of LBAs as a linear search would have to be performed over each of the L2P parts, the table may be divided up into different ranges based on a range of LBA’s associated with each portion. In this way, the linear search would only need to be performed over each of the ranges, which would decrease the linear search time of searching the parts of the L2P table [0174-0175]).
It would have been obvious for one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the L2P table as taught by Palmer to include breaking the L2P table up into different parts for different ranges of LBA’s, so that a search for a range of physical addresses corresponding to a range of LBAs would only need to perform a linear search over the corresponding part of the list.
One of ordinary skill in the art would have been motivated to make this modification because it would reduce the linear time required for the search over the entire L2P map to only the portion of the map that includes the requested range of LBAs as taught by Inbar in [0175].
Claim 17 is rejected under 35 U.S.C. 103 as being unpatentable over Palmer in view of US Patent Application Publication US 2016/0246530 A1 (Mylavarapu).
Regarding claim 17:
The storage device according to claim 14 is anticipated by Palmer.
Palmer does not explicitly disclose, but Mylavarapu teaches:
wherein the controller stores the data structure information, and the map data stored in the second memory, in a storage area designated from among the plurality of storage areas included in the first memory (by teaching that the L2P mapping table needs to be persistently stored to the NAND so that across power cycles, the mapping can be reconstructed [0038]. For a good L2P mapping, a fast reconstruction after power-up is required, typically under 1 second [0041-0042]. It is therefore important to have an optimized L2P data structure that minimizes L2P reconstruction time [0042]. To optimize for reliability and speed, all L2P data may be kept in a dedicated location on the memory device operated in the SLC mode with twice the size of the L2P data structure plus overprovisioning [0063]).
It would have been obvious for one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the compressed and uncompressed L2P data structures as taught by Palmer to be stored persistently in a dedicated portion of the NAND flash memory in the SLC mode as taught by Mylavarapu.
One of ordinary skill in the art would have been motivated to make this modification because it would optimize reliability and speed in reconstruction of the L2P data, which are important requirements for SSDs as taught by Mylavarapu in [0041-0042] [0063].
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to CURTIS JAMES KORTMAN whose telephone number is (303)297-4404. The examiner can normally be reached Monday through Friday 7:30 AM through 4:00 PM MT.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Reginald Bragdon can be reached at (571) 272-4204. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/CURTIS JAMES KORTMAN/Primary Examiner, Art Unit 2139
Prosecution Insights