Back to results
US 11,106,657 B2Granted
Optimizing hash storage and memory during caching
AssigneeInternational Business Machines Corporation
InventorsAkshat Dixit, Annwesh Barik
Life of this patent
Estimating the term…
Abstract
Technique for adding new key values (that is, new strings of binary digits that can be obtained by concatenating node values of nodes on a path through a tree) to a tree where each node corresponds to an ordered string of binary digits. When integrating the new key value, an XOR function is used to find an appropriate insertion location node (sometimes called a “selected parent node”) by efficiently finding the node that represents a path value (that is, concatenated value) that includes the longest prefix and a dissimilar suffix. Once the parent node is selected, the child nodes of this selected parent node are added and/or re-arranged to accommodate the new key value.
Claims18
A computer implemented method (“CIM”) comprising:
- receiving an original version of a binary-node-value (BNV) tree data structure, with the BNV tree data structure including a plurality of nodes, with each node having a node value in the form of a string of binary digit(s) and hierarchical paths among and between the plurality of nodes such that each given leaf node in the BNV tree corresponds to a string of binary digits comprising the node value of the given leaf node concatenated with the node value of every intervening parent node between the leaf node and a root node;
- receiving a new key corresponding to one literal property value of an application properties file containing a plurality of literal property values;
- responsive to receiving the new key, converting the new key from the literal property value to a binary representation including a key value binary digit string corresponding to the literal property value;
- selecting an insertion location node of the plurality of nodes in the BNV tree data structure, with the insertion location node representing a path value that:
- (i) shares the largest number of common prefix bits with the key value binary digit string, and (ii) has dissimilar suffix(es) relative to the key value binary digit string;
- and
- determining a revised version of the BNV tree data structure, with the determination of the revised BNV data structure including:
- revising the insertion location node of the BNV tree data structure to eliminate from its node value any binary digits included in the dissimilar suffix(es), and
- creating a plurality of child nodes under the insertion location node in the revised BNV data structure so that the path values of the plurality of child nodes have path values representing all of the dissimilar suffix(es).
6 more elements
A computer program product (CPP) comprising:
- a machine readable storage device;
- and
- computer code stored on the machine readable storage device, with the computer code including instructions for causing a processor(s) set to perform operations including the following:
- receiving an original version of a binary-node-value (BNV) tree data structure, with the BNV tree data structure including a plurality of nodes, with each node having a node value in the form of a string of binary digit(s) and hierarchical paths among and between the plurality of nodes such that each given leaf node in the BNV tree corresponds to a string of binary digits comprising the node value of the given leaf node concatenated with the node value of every intervening parent node between the leaf node and a root node,
- receiving a new key corresponding to one literal property value of an application properties file containing a plurality of literal property values;
- responsive to receiving the new key, converting the new key from the literal property value to a binary representation including a key value binary digit string corresponding to the literal property value,
- selecting an insertion location node of the plurality of nodes in the BNV tree data structure, with the insertion location node representing a path value that:
- (i) shares the largest number of common prefix bits with the key value binary digit string, and (ii) has dissimilar suffix(es) relative to the key value binary digit string, and
- determining a revised version of the BNV tree data structure, with the determination of the revised BNV data structure including:
- revising the insertion location node of the BNV tree data structure to eliminate from its node value any binary digits included in the dissimilar suffix(es), and
- creating a plurality of child nodes under the insertion location node in the revised BNV data structure so that the path values of the plurality of child nodes have path values representing all of the dissimilar suffix(es).
8 more elements
A computer system (CS) comprising:
- a processor(s) set;
- a machine readable storage device;
- and
- computer code stored on the machine readable storage device, with the computer code including instructions for causing the processor(s) set to perform operations including the following:
- receiving an original version of a binary-node-value (BNV) tree data structure, with the BNV tree data structure including a plurality of nodes, with each node having a node value in the form of a string of binary digit(s) and hierarchical paths among and between the plurality of nodes such that each given leaf node in the BNV tree corresponds to a string of binary digits comprising the node value of the given leaf node concatenated with the node value of every intervening parent node between the leaf node and a root node,
- receiving a new key corresponding to one literal property value of an application properties file containing a plurality of literal property values;
- responsive to receiving the new key, converting the new key from the literal property value to a binary representation including a key value binary digit string corresponding to the literal property value,
- selecting an insertion location node of the plurality of nodes in the BNV tree data structure, with the insertion location node representing a path value that:
- (i) shares the largest number of common prefix bits with the key value binary digit string, and (ii) has dissimilar suffix(es) relative to the key value binary digit string, and
- determining a revised version of the BNV tree data structure, with the determination of the revised BNV data structure including:
- revising the insertion location node of the BNV tree data structure to eliminate from its node value any binary digits included in the dissimilar suffix(es), and
- creating a plurality of child nodes under the insertion location node in the revised BNV data structure so that the path values of the plurality of child nodes have path values representing all of the dissimilar suffix(es).
9 more elements
Dependencies are inferred from the claim text.